Fantasy-land: Apply ?= Applicative, Chain ?= Monad

[ccorcos]

I'm a little confused here.

Is there any Functor that doesn't have a .of function? Isn't that just a constructor?

Just.prototype.of = function(x) {
  return new Just(x)
}

By this logic, an Apply is an Applicative and a Chain is a Monad.

Are there any good examples of data structures that are particularly only some of these categories, but not all of them?

[puffnfresh]

Tuples need a monoid on the left hand side to become an Applicative or Monad.

[puffnfresh]

Key-value maps

[ccorcos]

I'm sorry but I don't understand your comment. Monoids are entirely disconnected from Functors:

And I don't follow what you're saying with key-value maps either. There needs to be some way of constructing them, right?

[puffnfresh]

A tuple would need to look like:

Tuple.of = function(x) {
  return new Tuple(Monoid.empty, x);
};

A map needs a key as well as a value. The key means it can not be an Applicative.

[joneshf]

There needs to be some way of constructing them, right?

You can still use other functions that a key value map provides. You aren't restricted to only using functions from this specification.

[CrossEye]

If generic Tuples aren't clear enough, think of a Pair(x) type like this:

// map:: (a -> b) -> Pair(x, a) -> Pair(x, b)

If x represents, say, three-character strings, then map(square, Pair('foo', 7)); //=> Pair('foo', 49) without issue, but there is no way to create an arbitrary Pair.of(3). Where would it get the string? That's the fundamental problem.

[ccorcos]

Where would it get the string? That's the fundamental problem.

I see. So .of can take only a single parameter. And that parameter must be a basic type? Well what is a basic type? For example, what if you passed an array of two items in Pair.of(['foo', 7])?

What I'm really struggling with is discriminative examples. I finally understand how all this stuff works in regards to Maybes and Arrays, but thats because they work for just about all of them. But what are some examples that discriminate between these categories well?

• whats a semigroup that isn't also a monoid?
• whats a foldable that isn't also a traversable?
• whats an functor that isn't also an apply?
• whats an apply that isn't also an applicative?

A pair is an Apply (you can bias map and ap to the right value), but it is not an Applicative because you can only pass one value (and any value) into .of and even if its just the right value, it will not pass the interchange law.

• whats an apply that isn't also a chain?
• whats a chain that isn't also a monad?
• what an applicative that isn't also a monad?

I've been trying to find answers to these all damn week! Any ideas?

[joneshf]

And that parameter must be a basic type?

No. Any type at all. If it doesn't work for any type, it's not Applicative.

For example, what if you passed an array of two items in Pair.of(['foo', 7])?

Your pair still needs some Monoid on the left. Otherwise, it doesn't matter what you pass. You can't lawfully implement Applicative. Array is not special in any way in this context.

[ccorcos]

No. Any type at all. If it doesn't work for any type, it's not Applicative.

Damnit, you're right! Touché.

Well we can still bias everything towards the right value, right?

x = new Pair(1, 2)
x.map(inc) // Pair 1 3
y = new Pair(null, inc)
y.ap(x) // Pair null 3
Pair.of(99) // Pair null 99

Now all the applicative laws work.

[joneshf]

If you bias towards the right, it fails the interchange law.

[ccorcos]

Ah yes! So a Pair is a an example of of an Apply that isn't also an Applicative. :+1: I updated my comment above. Any other ideas for those?

[CrossEye]

whats a semigroup that isn't also a monoid?

Mathematically, the set of positive numbers, with concat representing addition is a semigroup but not a monoid. Build a type to model this, and you will have an example.

And in general, remember that your types are defined by you. If you have a function that defines a map method but no ap one, then it might be a Functor, but it cannot, according to this spec, be an Apply. This does not mean that no one could define one, but there are examples of each of these as well; there really are reasons to draw the boundaries where they are.

[ccorcos]

Mathematically, the set of positive numbers, with concat representing addition is a semigroup but not a monoid.

Interesting. That makes sense.

there really are reasons to draw the boundaries where they are.

So your point is that, although you can define a .ap for Pair, it likely serves no purpose.

[CrossEye]

there really are reasons to draw the boundaries where they are.

So your point is that, although you can define a .ap for Pair, it likely serves no purpose.

No, I was just waving my hands here. I'm not one who knows this stuff well, and I didn't have any simple concrete examples for you. I should probably have just shut up. But there were two points.

First, when you define your types, you decide on their interfaces. If you choose to define a map function that is able to pass the Functor laws, then your type is a Functor. If you don't define an ap one, then there is no way your type will be an Apply, _even if_ there is some logical choice of how one might define ap for your type.

But second, these types were defined by some very smart people, in a number of languages, and the established types have been well-vetted. They cannot be derived from one another. It's not simply that you could define a type and not include, say, ap, but that there are Functors for which no lawful ap can be defined.

[ccorcos]

It's not simply that you could define a type and not include, say, ap, but that there are Functors for which no lawful ap can be defined.

This is what I'm interested in -- examples that help discriminate between these categories -- for the purpose of better understanding...

[puffnfresh]

Tuples are Bind but not Monad.

NonEmptyList is Semigroup but not Monoid.

Sets are Foldable but not Traversable.

[puffnfresh]

I just remembered that there's a blog post with some examples, too: http://blog.functorial.com/posts/2015-12-06-Counterexamples.html

[ccorcos]

Yes! Thanks @puffnfresh

[rpominov]

@puffnfresh Could you clarify why Set can't be Traversable? In JS we can represent a set using array and we can define sequence for arrays.

[ccorcos]

@rpominov but a set must always have a unique "set" of values.

I'm not entirely sure, but suppose you have a set (and I'll use [] to denote a set).

set = [Maybe.of(1), Maybe.of(1)]
set.sequence(Maybe.of) // Maybe([1, 1])

So in the first line, if Maybe is a Setoid and has an equals, then it wouldn't be a set since there are to values with the same value. But if its not a Setoid, then those are two unique values in the set. And when you traverse, you'll end up with a Maybe or a Set of 1's. And 1 === 1 so therefore its no longer a set.

That said, I'm pretty sure you could "append" to the set just as you'd append to an array but checking for uniqueness. So... I guess I stand corrected. Idk why it cant be traversable... @puffnfresh?

[SimonRichardson]

Although this is a great discussion I'm not sure what the output of the issue should be?
I'm closing it now and open it you think otherwise.