Make Option and List structures more consistent with each other

[eduardoleon]

The option and list datatypes have a lot in common of each other. Both support the following operations:

(* functor *)
val map : ('a -> 'b) -> ('a t -> 'b t)

(* monoidal functor *)
val unit : 'a -> 'a t
val pair : 'a t * 'b t -> ('a * 'b) t

(* pointed functor *)
val empty : 'a t
val null : 'a t -> bool

(* monad *)
val join : 'a t t -> 'a t

The above list of operations is far from exhaustive.

Unfortunately, the API exposed by the Basis Library introduces unnecessary discrepancies:

• Option has Option.isSome, but List has List.null
• Option has Option.join, but List has List.concat
• For some weird reason, List has List.mapPartial, rather than List.concatMap
• Many of the functions in List also make sense for options, but Option doesn't provide them

Would it be possible to fix these discrepancies?

[JohnReppy]

Some of these discrepancies are historical. mapPartial have a different signature from concatMap. Fortunately, renaming allows one to work around these discrepancies when applying functors.

BTW, which List functions do you think should be added to Option?

[eduardoleon]

List.mapPartial is a special case of List.concatMap, so nothing (other than backwards compatibility) is lost by replacing List.mapPartial with List.concatMap. Then Option.mapPartial should be renamed to Option.concatMap to be compatible.

List.all, List.exists, List.foldl, List.foldr and List.collate should have Option counterparts. Of course, Option.foldl and Option.foldr would be two different names for the same function.

Option.filter should have type ('a -> bool) -> 'a option -> 'a option, to be analogous to List.filter.

Option.null would also be nicer than Option.isSome.

[MatthewFluet]

I don't understand how List.mapPartial is a special case of List.concatMap:

- List.mapPartial;
val it = fn : ('a -> 'b option) -> 'a list -> 'b list
- List.concatMap;
val it = fn : ('a -> 'b list) -> 'a list -> 'b list

They have different types.

[jonsterling]

@MatthewFluet What about mapPartial f = concatMap (fn x => case f x of SOME y => [y] | NONE => [])?

[MatthewFluet]

@jonsterling Sure, mapPartial can be implemented in terms of concatMap, but @eduardoleon suggested "replacing List.mapPartial with List.concatMap"; I don't understand that argument unless the type of List.mapPartial were a specialization of the type of List.concatMap. In any case, the Basis Library (especially structure List) is concerned with convenience, not minimality; I use mapPartial as often as concatMap and I wouldn't want to see mapPartial removed (even if I can implement it at each use site in terms of concatMap).

[jonsterling]

@MatthewFluet Ah, I see what you mean—I think the sense in which @eduardoleon meant "special case" was "factors through".

My personal view is, I would caution against going too deep down the rabbit hole of trying to define basis library structures in terms of a collection of algebraic and categorical signatures, like monad, etc. As was learned the hard way in Haskell, this style eventually force arbitrary decisions which rely on a unicity of structure which simply is not justified (e.g. what is the relation between the units of the monad and the lax monoidal / applicative structure?).

My preference would be to keep that stuff out of the basic List, Option modules etc., and allow people to separately define whatever modules they want that abstract over these—basically, how it already is. Otherwise, we just privilege one possible instance of a signature by "including" it in the main module—for instance, there are multiple distinct monoid structures that one can define for Option, so it makes no sense to include monoid-related operators in the Option structure itself.

[eduardoleon]

As was learned the hard way in Haskell, this style eventually force arbitrary decisions which rely on a unicity of structure which simply is not justified

I don't think that would be a problem in SML, since you can always define a separate structure that reuses the same types.

(e.g. what is the relation between the units of the monad and the lax monoidal / applicative structure?).

Inside the same structure, the units should agree. (Or, in fact, there should only be one unit common to both.) In different structures, they might be different.

[jonsterling]

I don't think that would be a problem in SML, since you can always define a separate structure that reuses the same types.

Sure—my point was not about problems with coherence; I was suggesting that we don't want to privilege one over the other by embedding it in the basis structure.

[YawarRaza7349]

Presumably the purpose of aligning these modules with each other is so you can write code (functors) that are generic over both via treating option as a list with zero or one elements (which Haskell and Scala also support). IMO, the List names are less natural for option than the existing Option names when writing code monomorphic to option (which is vastly more common than viewing option as a list).

What should be done instead (though probably not in the Basis Library) is having a separate adapter module structure OptionAsList :> (* most of the LIST signature *) where type 'a list = 'a option that basically serves as a typeclass instance that can be passed to functors working generically on lists/collections.

Aside from that, some situations require flexibility that typeclasses can't provide and instead need option values to be converted into list values, so a Basis Library function Option.toList : 'a option -> 'a list could be useful for these situations.