Code review: is this the right way to implement Option?

[bcherny]

Hey guys, first time Fantasyland implementer here.

I recently implemented an Option type for TypeScript, and took a shot at adding Fantasyland support to it. As a Haskell and category theory newbie, I'm not totally confident in my implementation. It would be really nice if someone could take a look at tsoption#fantasyland and give some feedback (in this issue tracker, or via issue or PR in its tracker).

If this is the wrong place for this, feel free to close this issue and I'll reach out to FL contributors directly.

Thanks!

[davidchambers]

I spotted a couple of problems:

• it seems you provide map/chain/… rather than fantasy-land/map/fantasy-land/chain/…; and
• mapping _ => null over Some(42) must produce Some(null) rather than None.

Rather than creating yet another Maybe/Option implementation I would love to see you add TypeScript support to a mature implementation such as those of Folktale and Sanctuary.

[joneshf]

Rather than creating yet another Maybe/Option implementation I would love to see you add TypeScript support to a mature implementation such as those of Folktale and Sanctuary.

100% this

[gabejohnson]

mapping _ => null over Some(42) must produce Some(null) rather than None.

You could certainly implement something like Option.fromNullable for this purpose.

I think that implementing a type like Option yourself is a good learning exercise, but agree with the other two comments. Adding TS support for an existing library would be more beneficial for the community in the long run.

[gabejohnson]

https://github.com/sanctuary-js/sanctuary-maybe/tree/svozza/everything would be a good place to look.

[safareli]

Those functor laws :d

[bcherny]

Thanks for the feedback everyone - it's very helpful.

@davidchambers

it seems you provide map/chain/… rather than fantasy-land/map/fantasy-land/chain/…

Looking here the methods seem to be directly on the promise prototype. But in @gabejohnson's example methods are namespaced. Which convention should be used where?

mapping _ => null over Some(42) must produce Some(null) rather than None.

At least in Scala, this behavior is an unfortunate consequence of running on the JVM. I changed that behavior is tsoption, since None<number> seems to be the more correct result (the whole point of Options is to avoid NPEs in Scala). At a high level, Some can become None, but once None it can't become Some again. Can you help me understand why it should give Some<number>(null), rather than None<number>?

[gabejohnson]

@bcherny there's nothing about the FL spec preventing you from providing non-namespaced methods on the prototype. The example code you linked to is following the pre-1.0 spec which didn't have prefixing.

[davidchambers]

Can you help me understand why it should give Some<number>(null), rather than None<number>?

It's forbidden by the spec:

iii. No parts of f's return value should be checked.

This doesn't prevent authors from supporting null in other ways. Sanctuary provides toMaybe, fromMaybe, and toNullable for getting from Nullable a to Maybe a and back again. A lawful fantasy-land/map method, though, must treat all values in exactly the same way.

[bcherny]

@gabejohnson Branch is updated - how does that look?

@davidchambers A couple of points:

1. It seems that checking map's return value is necessary if you also want to obey Functor composition ("u.map(a => a) is equivalent to u (identity)"). Unless "equivalent" doesn't mean equivalent in the a === b JavaScript sense, but in the "equal if you use a custom .equals method as specified in Setoid" sense.
2. It's not actually map that converts Some<T>(null) to None<T>, but it's the Option constructor (ie. Option[of]). Though looking at the spec, it looks like of also shouldn't check the return value. What I don't understand is if you don't check of's return value, then how do you implement Option semantics? Again going back to Scala, Option(Null) = None and Option(1) = Some(1), so it must care about the return value. Maybe (heh) a way to get around this conundrum is if we say "Some and None are monads complying with the Fantasyland spec, but Option is not strictly speaking compliant". Unless you say this, Option isn't very useful because if anything in its chain of computation introduces a null then the rest of the chain should be aborted; I'm not sure how to abort the chain unless you inspect return values in of.

---

On another note, a few thoughts as a first time user:

1. FantasyLand is a very cool idea!
2. The docs and examples could be more clear on V1 vs. pre-V1, and on authoring types in general. And more examples (preferably linked inline from the spec) would make it much easier for first time authors (or at least for me!).
3. I'm sure there was good reasoning behind it, but the "fantasyland/of" syntax to access methods is very clunky, and requires bringing in fantasy-land as an NPM dependency. It's not very nice to use, even if it avoids naming collisions.
4. A TypeScript-first approach could be very valuable, because then there's a static way to verify that something complies with the spec.
5. That said, any sort of FL compliance suite I could use for the types I wrote would be great, even if it's not static.

Edit: Added more thoughts.

[davidchambers]

Unless "equivalent" doesn't mean equivalent in the a === b JavaScript sense, but in the "equal if you use a custom .equals method as specified in Setoid" sense.

Equivalent, in this case, doesn't actually mean either of these. See #259.

Though looking at the spec, it looks like of also shouldn't check the return value.

Correct. Option['fantasy-land/of'](x) must evaluate to Some(x) even if x is null.

Unless you say this, Option isn't very useful because if anything in its chain of computation introduces a null then the rest of the chain should be aborted; I'm not sure how to abort the chain unless you inspect return values in of.

The functions in the chain should have types such as a -> Option b, not a -> Option (Nullable b). If you have a function of type a -> Nullable b you'd like to use in a chain, the best approach is to define a higher-order function which takes such a function and returns a function of type a -> Option b.

Think about getting rid of all the null values and null-returning functions at the outset rather than having special null handling sprinkled throughout the program. It seems Scala sets a bad example, unfortunately.

The docs and examples could be more clear on V1 vs. pre-V1

I agree. I think we should use the fantasy-land/ prefix everywhere. It's noisy, but I don't like the current approach of relying on a note somewhere in the document to provide context for all the unprefixed method names.

I'm sure there was good reasoning behind it, but the "fantasyland/of" syntax to access methods is very clunky, and requires bringing in fantasy-land as an NPM dependency. It's not very nice to use, even if it avoids naming collisions.

It's not necessary to depend on fantasy-land. One can simply use the appropriate string literals. This is the approach taken for many projects, including Fluture and Sanctuary.

For users, I agree that Option['fantasy-land/of'](42) is inconvenient. This problem is neatly solved, though, by sanctuary-type-classes, the unofficial standard library for Fantasy Land. One can write Z.of(Option, 42), which is much less noisy.

A TypeScript-first approach could be very valuable, because then there's a static way to verify that something complies with the spec.

Unfortunately such proofs are not possible even with Haskell's type system (which is much more powerful than that of TypeScript). Instead we must rely on property-based testing and good old-fashioned reasoning.

That said, any sort of FL compliance suite I could use for the types I wrote would be great, even if it's not static.

I completed the remaining tasks on fantasyland/fantasy-laws#1 this weekend. That project should be available via npm within the next couple of weeks. :)

[paldepind]

@bcherny

A TypeScript-first approach could be very valuable, because then there's a static way to verify that something complies with the spec.

You may want to look at Jabz which is exactly that. But, as @davidchambers rightly sais TypeScript cannot verify the laws.

@davidchambers

I think we should use the fantasy-land/ prefix everywhere.

Or even better: Remove the prefixes altogether 😄 They give nothing but problems, inconvenience and added complexity.

[davidchambers]

[Prefixes] give nothing but problems, inconvenience and added complexity.

Really? Based on ramda/ramda#2223 I must disagree.

[xgbuils]

Or even better: Remove the prefixes altogether 😄 They give nothing but problems, inconvenience and added complexity.

I don't agree. It give interoperability of APIs preventing duck typing conflicts.

[bcherny]

Thanks for the detailed answer @davidchambers. I'm still not sure I totally get it.

flatMap complies with FL because a function passed to it must return a lifted value, ie. a value wrapped in either Some or None (both of which are data constructors in Option):

flatMap<U>(f: (value: T) => Some<U>): Some<U>
flatMap<U>(f: (value: T) => None<U>): None<T>

But you're saying map doesn't comply because the Option function matches on the type of value, returning either a Some or None depending on the value:

map<U>(f: (value: T) => null): None<U>
map<U>(f: (value: T) => U): Some<U>

Let me know if I got that right. What I don't understand is how fromNullable would solve this: there must be some sentinel value indicating a lack of value, and in JS that is null. If we don't check whether map returns a value or null, we might get Some<null>, which is nonsense because it defeats the whole purpose of Some.

Are you saying that a function passed to map should only be able to return non-null values, and functions that may return null should be lifted with fromNullable first, and then be used with flatMap instead of map? So the signature would become:

map<U>(f: (value: T) => U): Some<U>

If so, that seems to be sacrificing usability for perfection: it puts the burden on the user to lift every nullable function to an Option-giving function first, which in JavaScript is nearly every function. Since TypeScript handles nulls well (a nullable's type is A | null), there's no safety gained from this lifting, and it is simply necessary to placate the FL specification. Additionally, in TS it is difficult to express a negation type; the closest thing would be:

map<U>(f: (value: T) => null): never
map<U>(f: (value: T) => U): Some<U>

But that code suffers from nonlocality: a nullable function passed to map would throw an error on the line where its result is consumed, not on the line where it's passed to map. This is a TypeScriptism, but it prevents me from statically verifying in a clean way that a nullable function wasn't passed to map. So allowing null is a way to ensure safety, and you won't have that safety if you disallow passing nullables to map. Since map is such a common operation for Options, I think safety is really important here.

I'm curious what you think, and if I understood you correctly so far.

[joneshf]

tl;dr; The long and short is, we've defined the spec to be a certain way, null is not a special value, so you cannot treat it as special and adhere to the spec. You're free to not adhere to the spec, but if you treat null specially, you're telling your users a lie.

---

We've discussed this pretty in depth in the past: #85 I mention this not to dissuade you from asking questions, but in order to show you some of the past discussions we've had. There's a good chance the reasoning is down in that issue. There's also a really good chance that any other algebra you try to adhere to are broken if Functor is broken for your data type.

Here are some highlights:

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.

#85 (comment)

@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).

#85 (comment)

There are more, hopefully with better explanations. Again, please feel free to ask questions, but there's also past discussions that might answer your questions.

[davidchambers]

Thanks for explaining the incentive TypeScript is providing to work with Nullable a rather than Maybe a/Option a. 😢

As Hardy stated above you're free to treat null specially if you wish to do so, but you cannot claim that your Option type is a Fantasy Land -compliant Functor if it does not provide a lawful fantasy-land/map method.

As for interoperability, it cuts both ways. If your Option type is not lawful you cannot leverage useful functions such as these:

$ cd github.com/sanctuary-js/sanctuary

$ grep -E '//# [^#]* :: .*(Alt|Alternative|Applicative|Apply|Bifunctor|Chain|ChainRec|Comonad|Extend|Functor|Monad|Plus|Profunctor|Traversable)' index.js
  //# map :: Functor f => (a -> b) -> f a -> f b
  //# bimap :: Bifunctor f => (a -> b) -> (c -> d) -> f a c -> f b d
  //# promap :: Profunctor p => (a -> b) -> (c -> d) -> p b c -> p a d
  //# alt :: Alt f => f a -> f a -> f a
  //# zero :: Plus f => TypeRep f -> f a
  //# traverse :: (Applicative f, Traversable t) => TypeRep f -> (a -> f b) -> t a -> f (t b)
  //# sequence :: (Applicative f, Traversable t) => TypeRep f -> t (f a) -> f (t a)
  //# ap :: Apply f => f (a -> b) -> f a -> f b
  //# lift2 :: Apply f => (a -> b -> c) -> f a -> f b -> f c
  //# lift3 :: Apply f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
  //# apFirst :: Apply f => f a -> f b -> f a
  //# apSecond :: Apply f => f a -> f b -> f b
  //# of :: Applicative f => TypeRep f -> a -> f a
  //# chain :: Chain m => (a -> m b) -> m a -> m b
  //# join :: Chain m => m (m a) -> m a
  //# chainRec :: ChainRec m => TypeRep m -> (a -> m (Either a b)) -> a -> m b
  //# extend :: Extend w => (w a -> b) -> w a -> w b
  //# extract :: Comonad w => w a -> a
  //# filter :: (Applicative f, Foldable f, Monoid (f a)) => (a -> Boolean) -> f a -> f a
  //# filterM :: (Alternative m, Monad m) => (a -> Boolean) -> m a -> m a
  //# takeWhile :: (Foldable f, Alternative f) => (a -> Boolean) -> f a -> f a
  //# dropWhile :: (Foldable f, Alternative f) => (a -> Boolean) -> f a -> f a
  //# append :: (Applicative f, Semigroup (f a)) => a -> f a -> f a
  //# prepend :: (Applicative f, Semigroup (f a)) => a -> f a -> f a
  //# pluck :: (Accessible a, Functor f) => String -> f a -> f b
  //# reverse :: (Applicative f, Foldable f, Monoid (f a)) => f a -> f a
  //# sort :: (Ord a, Applicative m, Foldable m, Monoid (m a)) => m a -> m a
  //# sortBy :: (Ord b, Applicative m, Foldable m, Monoid (m a)) => (a -> b) -> m a -> m a

So, you have a choice:

• write a decorator so you can write returningOption(uglyFunc); or
• implement Option-specific versions of all the functions above.

[ivenmarquardt]

@bcherny It is a popular misconception that the Option type is a suitable replacement for conditionals like x === null ? "" : "foo". As a matter of fact it is a substitute value for functions/expressions that may not produce one, that is to say it is significant while a value (or no value at all) is being produced, not afterwards.

undefined on the other hand indicates a type error and I see no reason not to check for such type errors within your constructors. Who takes parametricity too seriously in an dynamically and even weakly typed language should switch to a proper typed one.

[bcherny]

Branch is updated - how does that look to you guys?

@ivenmarquardt That seems pretty controversial. null and undefined are used interchangeably in JS.

[bcherny]

Closing. Thanks for the feedback everyone, and feel free to file an issue in https://github.com/bcherny/tsoption if something still isn't right.

[masaeedu]

@bcherny The disconnect is that TypeScript has ad-hoc untagged unions, and it must interoperate with JS code that will just be producing T | undefined willy nilly, without bothering to wrap things in Option. So in TS/JS, our equivalent of newtype Option a = Nothing | Some a is really: type Option<A> = A | undefined.

I think if you instead claim static-land compatibility, you could implement instances of all the relevant typeclasses for a non-reified "virtual" type like type Option<A> = A | undefined, and then simply be able to map or chain or whatnot over regular non-wrapped values that the type system tells you are A | undefined.

As an example:

const Option = {
  // ...
  map: (f, a) => a === undefined ? undefined : f(a)
}

And then somewhere else...

import { map as optMap } from "my/option"

optMap(x => x * 2, undefined); // undefined
optMap(x => x * 2, 10); // 20