Terminology for possible things inside a Functor/Applicative/Monad

Learn
#1

Is there widely-accepted terminology for the possible things you could see from the inside of a given Functor, Applicative, or Monad? Examples of what I mean for some different ones:

  • Identity: The _______ of Identity "abc" is ["abc"]
  • Writer: The _______ of (["log entry one", "log entry two"], 42) is [42]
  • Maybe: The _______ of Nothing is []
  • Maybe: The _______ of Just True is [True]
  • ZipList: The _______ of ZipList [1,2,3] is [1,2,3]
  • Non-determinism: The _______ of [1,2,3] is [1,2,3]
  • Reader: The ________ of \x -> if x then 123 else 456 is [123,456]
  • IO: The ________ of getContents is all Strings

Semi-formally, I mean the smallest xs for some given m for which ((`elem` xs) <$> m) == (True <$ m).

Here’s the actual context I want to use the word in:

The ________ of traverse (\x -> ZipList [x+10, x+20]) [1,2,3] is just [[11,12,13],[21,22,23]], but the ________ of traverse (\x -> [x+10, x+20]) [1,2,3] also contains [11,22,13] and several other lists that don’t preserve monotonicity.

4 Likes
#2

This is a very interesting concept! Perhaps “range”. After all, the “range” of a function a -> b is the smallest subset of b, call it bs, such that (`elem` bs) . f == const True . f. This translates into your setting by considering the (a ->) monad.

2 Likes
#3

I usually think of a monadic value m a as a computation. I’d call the contained type a the “value”, or possibly “return value” to make it explicit that this value comes from a computation context.

1 Like
#4

It appears you are treating functors as set-like containers, which is arguably a helpful mental model for many data structures. A mathematician would use the word support for your examples, which is common terminology for some mathematical monads [*].

However, the design space of functors, or even monads is vast, and it is not hard to come up with examples that look nothing like a set. What would you say should be the support of a continuation monad, the store comonad, …

Your semi-formal definition actually makes sense for affine applicative functors, which are functors f where for any m :: f x and any y the semantic equality (const y) <$> m = pure y holds. You can then talk about predicates p :: x -> Bool for which p <$> m = pure True and call the smallest such predicate the support.

[*] The support of a Borel measure is the complement of the largest open set with measure zero. The mapping from measure to support is actually a monad morphism.

3 Likes
#5

What would you say should be the support of a continuation monad

Whatever it calls the function with. E.g., for cont (\c -> c 123 ++ "\n" ++ c 456), it would be [123,456].

the store comonad

The range of whatever the accessor function is. E.g., for store show EQ, it would be ["LT", "EQ", "GT"].

Your semi-formal definition actually makes sense for affine applicative functors, which are functors f where for any m :: f x and any y the semantic equality (const y) <$> m = pure y holds. You can then talk about predicates p :: x -> Bool for which p <$> m = pure True and call the smallest such predicate the support.

I like the idea of generalizing to other predicates, but not of restricting to affine applicative functors, so p <$> m = True <$ m.

#6

Except IO, all of these are also Traversals. So you could borrow terminology from optics and call each such value a focus.

Alternatively, since all your examples except IO are container functors, or polynomial functors, what you’re asking for is related to the concept of a position in a container functor. (There are some naming clashes here, I’m not talking about the container library on hackage, but the mathematical construction: https://people.cs.nott.ac.uk/pszgmh/appsem-papers/abbott.pdf Also, newer literature unfortunately started to confuse positions and shapes.) Container functors have “all” and “any” modalities which are close to what you want. But note: For the reader functor you are really relying on the environment to be finite. And for IO, none of this works, but I find it a stretch to generalise it to IO.

All that said, in your case I’d just say values or results.

2 Likes
#7

Topologically, one can regard Cont () x as the double powerdomain of x whose elements are compact sets of closed set of x. Here, we regard () = {⊥, ()} as Sierpinski space. A more concrete example:

doublepower :: Eq a => [[a]] -> Cont Bool a
doublepower xss = Cont (\c -> all (any c) xss)

So what would you say is the support or range of doublepower ["foo","bar","baz"] :: Cont Bool Char?

I like that interpretation. But isn’t a position tied to the concrete shape and not so much to the value? Like one can replace all elements in a Traversable container by consecutive numbers, thus enumerating the position of the elements.

#8

That’s right. For example for the list functor, the shapes are the natural numbers 0, 1, 2, 3, 4, ... corresponding to the length of the list, and the positions for any specific length n are the natural numbers 0, 1, 2, ... n-1. They are the possible indices of a list. The “values” or “possible results” (I’m not aware of an established nomenclature) are the values that are assigned to the positions.

By the way, two examples of functors that aren’t containers are:

  • The continuation monad, it is not strictly positive.
  • IO, because it is builtin.
#9

In the sense that they are not bilimits of coproducts of products, I presume?

#10

In the sense of the article I linked. Also known as polynomial functors or strictly positive functors. I guess this might be the same thing as what you wrote.

#11

I’d say it’s "fobarz". More generally, for any doublepower xss, I’d say it’s either nub (concat xss) or some subset of that. E.g., for doublepower ["a", "ab", "aa"], it’d just be "a", because for any given c, if c 'a' is True, then it moves on from the second list before it gets to 'b', and if it’s False, then the whole thing returns False before it gets to the second list.

#12

How about the following?

member :: Eq a => a -> Cont Bool a -> Bool
x `member` m = runCont f (x==)

In that respect, no element is a member of doublepower ["foo","bar","baz"] and 'a' is the only member of doublepower ["a", "ab", "aa"].
What I wanted to convey with the doublepower example: Not all functors can sensibly be mapped to a list of elements. Perhaps do it like in the Abbott paper and define your notion recursively, from the ground up, deriving your notion of more complex functors given the notion of their constituents.

1 Like