Why "No parts of b should be checked" for Applicative?

[TheLudd]

Why is it important for the Applicative of function to not check it's input?

My question arises because I have seen two different types of implementations for Maybe, one that pretty much looks like this where the check to see if the value is null is done in the map function:

function Maybe(val) {
  this.val = val;
};
Maybe.prototype.map = function(f) {
  return this.val == null ? this : new Maybe(f(this.val));
};

and another one which has 2 sub types Just and Nothing.

function Maybe(val) {
  return this.val == null ? new Nothing() : new Just(val);
};

function Just(val) {
  this.val = val;
};

Just.prototype.map = function(f) {
  return new Maybe(f(this.val));
};

function Nothing() {};

Nothing.prototype.map = function(f) {
  return this;
};

My point here is that the second implementation does a check in the constructor, and because of this it would break the fantasy land specification if it implemented of = function(val) return Maybe(val) but this is not true for the first implementation since it does the checking in the map method.

In the second case, Maybe.of can never return something that will not apply the input function in map.

This leads to the situation that because of internal design decisions Maybe.of may be forced to be inconsistent with other implementations in order to fulfill this specification. I find this strange and wonder if I have misunderstood something.

[SimonRichardson]

That's because you're Maybe.of is wrong. It should only return Just and not a possibility of both. Checking for null isn't covered in the specification, because this is in a fantasy-land and not to mention the million dollar mistake.

All values should not be null by there very nature when interacting with fantasy-land specification. If you do want to have a null checking part of your Maybe may I suggest Maybe.from (or similar named). There for your of can follow the correct specification.

Maybe.from = function(x) {
    return x == null ? new Nothing() : new Just(x);
}

[TheLudd]

@SimonRichardson Is the first implementation of Maybe also wrong?

Perhaps I don't understand the use case for of. If all it does is wrap the value in a Just why wrap it at all?
I'd be grateful for an explanation of how/when to use of.

[michaelficarra]

Wrapping puts the value in a context so that you know which map to apply.

[SimonRichardson]

To answer your question, is the first implementation wrong also, that depends if it fulfils the laws or not. And by laws, I mean the following Applicative and Functor (of and map respectfully).

The point of of is to give you a pure value. The of function will always evaluate the same result value given the same argument value. Which could or could not be the case with of also return Nothing.

[puffnfresh]

@TheLudd it's useful for abstraction. With of, we can derive map:

function map(a, f) {
  return a.constructor.of(f).ap(a);
}

Note that this works with anything that has an Applicative. Maybe is just one example!

[puffnfresh]

A more useful example is probably:

function liftA2(f, a, b) {
  return a.constructor.of(f).ap(a).ap(b);
}

We can do something like:

liftA2(function(a) { return function(b) { return a * b; }; }, Maybe.Nothing, Maybe.Nothing);
// Maybe.Nothing

liftA2(function(a) { return function(b) { return a * b; }; }, Maybe.Nothing, Maybe.Just(10));
// Maybe.Nothing

liftA2(function(a) { return function(b) { return a * b; }; }, Maybe.Just(30), Maybe.Just(10));
// Maybe.Just(300)

But again, this works for much more than just Maybe:

liftA2(function(a) { return function(b) { return a * b; }; }, Either.Left("Bad"), Either.Left("Error message"));
// Either.Left("Bad")

liftA2(function(a) { return function(b) { return a * b; }; }, Either.Left("Bad"), Either.Right(10));
// Either.Left("Bad")

liftA2(function(a) { return function(b) { return a * b; }; }, Either.Right(30), Either.Right(10));
// Either.Right(300)

[buzzdecafe]

unless i'm mistaken then, a Maybe constructor doesn't make sense as something that can be called directly. It's always either Just | Nothing, much as an Either is Left | Right -- have I got that right?

[puffnfresh]

@buzzdecafe yep, that's right!

[TheLudd]

@puffnfresh @buzzdecafe
Just to clarify further:
The decision to wrap a value in either a Just or a Nothing must not be made in any of the functions specified in the fantasy land specification. It needs to be in a separate function, unique for Maybe.

Is this correct?

[joneshf]

Is the first implementation of Maybe also wrong?

I'd think it is wrong for the traditional semantics of Maybe. How do you represent a value: Just(null)? From the implementation, I'm not sure if you can.

It could still be a valid data type, or these abstractions could still apply. It just has different meaning from the traditional Maybe.

[joneshf]

Just to clarify further:
The decision to wrap a value in either a Just or a Nothing must not be made in any of the functions specified in the fantasy land specification. It needs to be in a separate function, unique for Maybe.

Is this correct?

I don't believe that's true. Look at ap. The outcome of it depends entirely on what the inputs are. The semantics of Maybe come through in the some of the functions, but not all. It just depends on each function.

[puffnfresh]

@TheLudd to implement map, you need to know whether the input is a Just or a Nothing. There are some functions which are meant to be universally quantified, but that's pretty hard to talk about when dealing with JavaScript.

An easy example of this quantification is Maybe's of. In type theory it be instantiated to:

Maybe.of : forall a. a => Maybe<a>

The forall is really important. It really means for ALL. It can not have any knowledge about the value. There are no operations it should be able to use. Not comparisons, not toString, nothing.

Please let me know if you know a way we can more easily talk about this.

[buzzdecafe]

Please let me know if you know a way we can more easily talk about this.

i'm also very interested in this discussion -- do you have, or have any interest in, a gitter chatroom for fantasy-land? see e.g. https://gitter.im/ramda/ramda

[CrossEye]

I'm wondering if I"m missing something basic here. Maybe is a type that wraps up the need for null/empty checking at multiple steps of a process. In the strongly-typed Haskell, this means it must be implemented with the Just(a)/Nothing semantics. But those could be thought of more as implementation details than the key idea, no?

The first implementation in the OP, was, I believe the one from Ramda's (still early) attempt at implementing the FantasyLand spec. In this implementation, there didn't seem to be any good reason to introduce Just and Nothing. Javascript is dynamically typed, and already has a mechanism for reporting missing values: the null value. So this implementation used that as its null/empty value, and didn't try to mimic Haskell's stricter types.

In other words, this implementation would not allow you to do any non-trivial algebra on Maybe(null), in the same way you can do no non-trivial algebra on Nothing. Is this really far off the mark?

[puffnfresh]

Yes, null is a value. If we're going to take the idea of parametricity idea seriously (i.e. forall really means for ALL) then we must be able to represent Just(null).

The Fantasy Land spec is an attempt to take the idea of parametricity seriously. Some tooling to help ensure parametricity would be awesome.

[joneshf]

I'm wondering if I"m missing something basic here. Maybe is a type that wraps up the need for null/empty checking at multiple steps of a process. In the strongly-typed Haskell, this means it must be implemented with the Just(a)/Nothing semantics. But those could be thought of more as implementation details than the key idea, no?

No, it's not just an implementation detail. The semantics of the data type are encoded in those two values. You might also think of Maybe a as the type of a computation that might fail. If a computation succeeds you get a Just a. If a computation fails you get a Nothing. In this light, would you view Just null the same as Nothing. The former states, "The computation succeeded, the value of that computation was null." The latter states, "The computation failed." These two values have different meanings. Similarly an empty list: [] and a singleton list with null: [null] have different meanings.

[CrossEye]

The semantics of the data type are encoded in those two values. You might also think of Maybe a as the type of a computation that might fail.

In idiomatic Javascript, if I were to try to encapsulate a a computation that might fail, my usual return value from the failure case would be null. While we can say "null is a value" if we're trying to define a rigorous type system for JS, we must also recognize that its semantics are specifically that of reporting that the reference/return in question in fact has no value.

I guess my question would be how one would expect Just(null) to behave differently than Nothing. We can assume, I would imagine, that

lift(add)(Just(3), Just(5)); //=> Just(8)
lift(add)(Just(3), Nothing); //=> Nothing

But would not

lift(add)(Just(3), Just(null)); //=> Just(null)

or would you expect to define some new value for that (Just(NaN))?

That it seems to me to act exactly as Nothing should makes me think that they should be one and the same, and hence that we can get away with not defining the subtypes in JS. But, as I said, I'm still new to this.

[michaelficarra]

@CrossEye lift(add)(Just(3), Just(null)) is Just(3) because in JS, 3 + null is 3.

[CrossEye]

@michaelficarra: Yes, unless you buy my argument that null is the signal for "computation failed". 😄

[michaelficarra]

I don't. 😏

[joneshf]

In idiomatic Javascript, if I were to try to encapsulate a a computation that might fail, my usual return value from the failure case would be null. While we can say "null is a value" if we're trying to define a rigorous type system for JS, we must also recognize that its semantics are specifically that of reporting that the reference/return in question in fact has no value.

Before we go too deep down this metaphor, we should realize that this is not the only interpretation. It is merely another way of looking at the semantics of the data type. Also, there's no real attempt to define a rigorous type system here. We're specifying an api with laws for it.

That said, suggesting there is no difference here is less composable than realizing these are separate values. What happens when you have a computation that might fail returning another computation that might fail? The type of something like this would be Maybe (Maybe a). What possible values can be returned here:

1. Just (Just a) The inner computation succeeded with a value, and the outer computation succeeded as well.
2. Just Nothing The inner computation failed, but the outer computation succeeded.
3. Nothing The outer computation failed.

If you assume Just null is equivalent to Nothing how would you distinguish between case 1 and 2 when the first case returns a Just (Just null)?

Suggesting that Just null is equivalent to Nothing is the same as suggesting that [null] is equivalent to []. That's jquery-esque logic and leads to bugs. If the singleton list example is still too wishy washy, how about [null, null, null]? This could be seen as saying, you had three computations and they all failed. This is hopefully not seen as equivalent to [], which can be seen as saying, you had no computations. If you distinguish these cases for lists, you should distinguish them for Maybe.

Maybe a is like a data type representing two possible values:

1. The empty list: [] is equivalent to Nothing
2. A singleton list: [a] is equivalent to Just a, for all values a.

[CrossEye]

I think I'm just having a hard time giving up on how I wanted to use these algebraic types with Ramda. (For those who haven't seen it, Ramda is a JS utility library with pre-curried functions, sane parameter order, easy composability, and no mutation of user data.) Although its functions are more strongly-typed than much of JS (no variadic functions, single types for most parameters) we don't go as far as trying to introduce such constructs as the FantasyLand algebraic types. But we would like to offer them as an adjunct for users who want to use them. I'm starting to think that perhaps this simply cannot be done.

R.head([]); //=> null

(Actually it's undefined; I was a bit confused, but let's ignore that issue for the moment.)

This is our failure case. We can't get the head of an empty list. we signal that issue with null/undefined. My goal was in introducing the algebraic types to make them a layer atop the existing code. But if somehow I really need to distinguish between head([]) and head([undefined]) in order to have a reasonable version of Maybe, then I can't build it on top of the existing code, and integrating these types is going to become a lot more intrusive.

That's a real bummer.

[joneshf]

Well, as mentioned before, it might not fit the semantics of the conventional Maybe a data type, but what you have might still be a useful data type just with slightly different semantics.

That's the whole point of fantasy land. You're not restricted by which data type you want or can use. If you make something and suspect it's a Functor, then see if it satisfies the laws. If so, you're golden and you can use the other things derivable from that. If it can't properly implement Applicative, but it can implement Apply, then good on you! Not every data type can implement all of these abstractions lawfully. Just go with the ones you can, so that others can use them.

[TheLudd]

@puffnfresh Regarding this rule:

Maybe.of : forall a. a => Maybe<a>

Is it ok to return a Just<a> since Just is a subtype of Maybe? (correct?)
But Nothing is not ok because even though it is a subtypte of Maybe (correct?), what would be returned would be a Nothing and not a Nothing<a>?

Also: I realize that there are relations between the different types in the specification and that some functions can be derived as combinations of others. Is there an example where the expectations break if of had the possibility of returning a Nothing?

[SimonRichardson]

chain, map (etc) would break as it won't not satisfy the laws.

[buzzdecafe]

The only thing I will miss is:

compose(map(f_2), Maybe, f_1)

... since I won't be able to call Maybe directly. Instead I'll have to do e.g.:

compose(map(f_2), Maybe.from, f_1)

which is a little less sweet.

[SimonRichardson]

That's looks really nice to me!

[CrossEye]

@buzzdecafe If I understand what's being said here though, since R.head([]) returns the same as R.head([undefined]), this sort of composition wouldn't work for f_1 = R.head, regardless of whether we used the Maybe constructor or Maybe.from. We would have to rewrite R.head to return a Maybe(a). That's the path I don't want to go down, as I want the types as an optional extension to Ramda, not a core feature. And the same would be true anywhere else we would want a Maybe return.

[buzzdecafe]

if:

Maybe.from = function(x) {
    return x == null ? Nothing() : Just(x);
};

then:

R.compose(map(inc), Maybe.from, head)([1,10,100]) //=> Just(2)
R.compose(map(inc), Maybe.from, head)([]) //=> Nothing
R.compose(map(inc), Maybe.from, head)([undefined]) //=> Nothing

that seems reasonable to me.

[TheLudd]

@SimonRichardson

chain, map (etc) would break as it won't not satisfy the laws.

I realize that it won't satisfy the laws since this question is about an implementation that does go against the laws. What I did't understand was the reason for this particular law and why it needs to be in place for all the types to be consistent. I was hoping for an example (a certain value put into a Maybe) that would break this consistency if Maybe were to do the null check in the of function.

[puffnfresh]

@TheLudd of looks fine, map and chain are very broken:

Maybe.of(null).map(function(a) { return 1; })
Maybe.of(null).chain(function(a) { return Maybe.of(1); })

Both expressions should result in Just(1).

[joneshf]

It doesn't lawfully implement Applicative because it breaks homomorphism and interchange.

You can think of the specification as being another law. So Applicative has four "laws"

1. a.of(b) must provide a value of the same Applicative and no parts of b should be checked. (type)
2. a.of(function(a) { return a; }).ap(v) is equivalent to v (identity)
3. a.of(f).ap(a.of(x)) is equivalent to a.of(f(x)) (homomorphism)
4. u.ap(a.of(y)) is equivalent to a.of(function(f) { return f(y); }).ap(u) (interchange)

So it holds for the type and identity laws, but fails for homomorphism and interchange laws. And all laws must hold in order to be lawful.

This happens, even though the Functor and Apply instances are lawful.

EDIT: Nope, this data type is not even a Functor

// `Apply` composition
a.map(function(f) { return function(g) { return function(x) { return f(g(x))}; }; }).ap(u).ap(v) is equivalent to a.ap(u.ap(v))

// Left side
Maybe({value: null}).map(function(f) { return function(g) { return function(x) { return f(g(x))}; }; }).ap(u).ap(v)
    = Maybe({value: null}).ap(u).ap(v)
    = Maybe({value: null}).ap(v)
    = Maybe({value: null})

// Right side
Maybe({value: null}).ap(u.ap(v))
    = Maybe({value: null})

// `Functor` identity
a.map(function(x) {return x;}) == a

Maybe({value: null}).map(function(x) {return x;})
    == Maybe({value: null})

// `Functor` composition
a.map(f).map(g) == a.map(function (x) {return g(f(x));})

// Left side
Maybe({value: null}).map(f).map(g)
    == Maybe({value: null}).map(g)
    == Maybe({value: null})

// Right side
Maybe({value: null}).map(function (x) {return g(f(x));})
    == Maybe({value: null})

The semantics of the data type are what cause it to fail to hold for algebras stronger than Apply. This is why the semantics of Maybe/Option from ML languages separates out the two values.

[puffnfresh]

@joneshf functor composition is absolutely broken.

function f(a) {
  return null;
}
function g(b) {
  return 10;
}

Maybe.of(1).map(f).map(g)
Maybe.of(1).map(function(a) { return g(f(a)); })

The first one will give you Maybe.of(null). The second will give you Maybe.of(10).

[joneshf]

@TheLudd of looks fine, map and chain are very broken:

Maybe.of(null).map(function(a) { return 1; })
Maybe.of(null).chain(function(a) { return Maybe.of(1); })
Both expressions should result in Just(1).

These examples look funky because of the semantics of the data type and because it's not an Applicative. It is a Chain, interestingly.

To construct the intended values you'd have to already have the nested Maybe. Something like:

Maybe({value: Maybe({value: null})}).map(function(a) { return 1; })
    == Maybe({value: (function(a) { return 1; })(Maybe({value: null}))})
    == Maybe({value: 1})

and

Maybe({value: Maybe({value: null})})).chain(function(a) { return Maybe({value: 1}); })
    == (function(a) { return Maybe({value: 1}); })(Maybe({value: null}))
    == Maybe({value: 1})

[joneshf]

@joneshf functor composition is absolutely broken.

Oh, right. I was looking at too simple of a case. Yeah, I guess this whole data type is not even a Functor.

[TheLudd]

Thanks everyone for your input, closing this now.

I feel a little bit wiser even though I don't grasp this fully. I understand that these laws works together and need to be consistent no matter what type implements them.

I think that my confusion is due to the fact that I don't understand what a Just wrapping a null is good for. Or what a Maybe that applies the map function to a null value is good for. But I am new at this and I am sure I'll learn along the way.

[SimonRichardson]

There probably isn't a good reason for a Just(null), but to get the laws to work for JavaScript, it has to be like that.

It is never going to be 100% clean when you bring something that doesn't have the concept of null to a something that does.

To be honest you end up working around it using things like Maybe.from and this does give you what you want.

[SimonRichardson]

Really good discussion as well, thanks

[davidchambers]

I think that my confusion is due to the fact that I don't understand what a Just wrapping a null is good for.

It's unlikely to be good for much at all. You've highlighted the disconnect in this thread: some of us are thinking of use cases while others are thinking of the underlying (mathematical?) laws. The underlying laws know nothing of usefulness, so there may be times when a law disallows behaviour programmers find useful. As several in the thread have said, that's fine, write useful code. The laws simply provide a way to answer questions such as Is this a functor?

[puffnfresh]

The underlying laws know nothing of usefulness...

This statement seems misleading. These laws allow useful abstraction and refactoring. For example, it's extremely useful to know that we can always rewrite a.map(f).map(g) to a.map(compose(g, f)). The laws also allow us to derive functions, which we can reuse.

Always being able to do refactorings and derive these functions requires Just(null) to be possible. I'd say Just(null) is very useful, through transitivity of the laws.

[davidchambers]

Well put, @puffnfresh.

It's more accurate to say that the laws know nothing of the usefulness of any particular value. @TheLudd and @CrossEye were asking themselves when one would ever want Just(null). @joneshf addressed this question directly. But the more important point is the one made by @puffnfresh above which as that for the laws to be useful at all there can be no exceptions, so Just(null) must be a value regardless of whether we deem it useful.

[joneshf]

I think that my confusion is due to the fact that I don't understand what a Just wrapping a null is good for. Or what a Maybe that applies the map function to a null value is good for. But I am new at this and I am sure I'll learn along the way.

It's useful because you're not stopping the flow of information. If you build a library that someone else uses as one step in a chain of things to do, you don't want to mess up their flow of information. If you feel that Just(null) is equivalent to Nothing, then you should also say Just(Just(null)) is equivalent to Nothing, and so on. But if someone is working with a data type that is nested like this, they might want to handle these as separate cases.

A concrete example might help here. Let's say you were writing a simple repl for js. You have separate functions for each part of it, looking at just read and evaluate

read :: String -> Maybe Program
evaluate :: Program -> Maybe a

where you might imagine that Program is something like this:

function Program() {}

function Null() {}
Null.prototype = new Program()

function String(s) { this.value = s; }
String.prototype = new Program()
... 

What semantics can read have? Well, if you try to read in a String, and it's not syntactically valid, it should return Nothing. If you read in something and it's syntactically valid, it should return Just(Program) for whatever program you read in.

What semantics can evaluate have? If you try to run a Program and it's not a semantically valid program, it should return Nothing. If you try to run a valid Program it should return Just(a) for whatever Program evaluates to.

You might compose these together with Chain:

read(line).chain(evaluate)

What's the behavior of this if the line you're reading is "null"? "null" should be a valid program, so it should be read fine and evaluated fine:

read("null").chain(evaluate)
  == Just(Null).chain(evaluate)
  == evaluate(Null)
  == Just(null)

At the next step (print) you should be able to print that value and continue on to loop no problem. This seems like acceptable semantics.

However, if you view Just(null) as equivalent to Nothing, then you don't print the value that was perfectly valid. You instead print an error. This does not seem like acceptable semantics. There are ways around it, but then each function becomes way more complex than it actually need to be.

Of course, this example is contrived. You'd generally want a more complex data type so you'd know how and when the repl failed. The point is, when you as the library writer arbitrarily decide that some input has different meaning than everything else in the language, you are making things less composable than they could be. It might be a good abstraction for certain situations, but you limit library users to the mindset you were in when you made the library, as @davidchambers and @puffnfresh mentioned. And for composability and reuse, this limitation is generally a bad thing. It's jquery-esque:

jQuery.map([null, null, null], function(x) { return [x]; })
  == [null, null, null]

Libraries become much more reusable and composable if you don't care what data people store in your data types.

[5outh]

It may be worth noting that a close analogue of Just(null) is Just(Nothing), and Just(Nothing) is certainly different than Nothing!

[davidchambers]

If you'd like to review the pull request above, please do so. 😀

[SimonRichardson]

fyi: scalaz has a similarly to Maybe.from

[puffnfresh]

Note that from is already taken by comonad: https://github.com/fantasyland/fantasy-land#from-method (and Maybe can not have a comonad)

[SimonRichardson]

Good spot!
Maybe.fromNullable it is :(

[robotlolita]

@TheLudd

Maybe.of : forall a. a => Maybe<a>

Is it ok to return a Just since Just is a subtype of Maybe? (correct?)
But Nothing is not ok because even though it is a subtypte of Maybe (correct?), what would be returned > would be a Nothing and not a Nothing?

Just and Nothing aren't really subtypes, they're just tags. The type is always Maybe<a>. It helps if you view types as the following logical relationship:

Maybe(a) = Just(a) ∨ Nothing

Which basically means that you can replace what's on the left by any of the terms that are on the right (as long as a maintains the same shape). From this type alone, the following implementation of Maybe.of is completely valid (as in, it type checks -- you can try it in Haskell for example):

Maybe.of :: forall a. a -> Maybe<a>
Maybe.of = function(a){ return Nothing }

What doesn't let you implement Maybe.of like that are the laws surrounding these algebras. For example, the Identity law for applicatives states:

a.of(function(a) { return a; }).ap(v)

So, if you take the implementation of Maybe.of above, that law is most likely broken:

Maybe.of(function(a){ return a }).ap(v) = v
= Nothing.ap(v) = v
= Nothing = v
= false