Discussion for proposal 2015-002

[JohnReppy]

This issue is for discussion of proposal 2015-002 (Addition of Either module).

[MatthewFluet]

A fold and a projection function might be useful:

val fold : ('left * 'b -> 'b) * ('right * 'b -> 'b) -> 'b -> ('left, 'right) either -> 'b
fun fold (fl, fr) init sum = (case sum
       of INL x => fl (x, init)
        | INR x => fr (x, init)
      (* end case *))

val proj : ('a, 'a) either -> 'a
fun proj sum = fold (fn (x,_) => x, fn (x,_) => x) () sum

[JohnReppy]

The fold and proj operations seem useful, so I've added them to the proposal.

[MatthewFluet]

My implementation of proj doesn't type check; I guess it would need a direct implementation:

fun proj sum = case sum of INL x => x | INR x => x

[JohnReppy]

I used the following code for the reference implementation:

fun proj (INL x) = x
  | proj (INR x) = x

[rossberg-old]

In Alice ML we had this under the name of ('a, 'b) alt. Besides fold, a set of additional functions that turned out useful was:

val appLeft :  ('a -> unit) -> ('a,'b) either -> unit
val appRight : ('b -> unit) -> ('a,'b) either -> unit
val mapLeft :  ('a -> 'c) -> ('a,'b) either -> ('c,'b) either
val mapRight : ('b -> 'c) -> ('a,'b) either -> ('a,'c) either

[MatthewFluet]

+1 for appLeft and friends; I was going to make the same suggestion.

[JohnReppy]

I've updated the proposal with these additional functions

[igstan]

I'm a bit late to this, but... why does Either.fold also take a 'b as argument? I think it should be just:

val fold : ('left -> 'b) * ('right -> 'b) -> ('left, 'right) either -> 'b

The "accumulator" argument makes sense for list and option, which both exhibit an empty variant, but not so much for Either.

[igstan]

Additionally, another useful function might be:

val swap : ('a, 'b) either -> ('b, 'a) either

Though probably less so if both mapLeft and mapRight are present.

[JohnReppy]

The type that you propose for fold1 looks more like a map to me. I think that there is some advantage in keeping the "accumulator" argument to fold, since it might be used in a fold over a sequence, but perhaps the type should be

val fold : ('left * 'b -> 'b) * ('right * 'b -> 'b) -> ('left, 'right) either * 'b -> 'b

to make such usage easier (although that breaks the common shape of fold functions in the Basis Library). The swap function seems like a useful addition.

[igstan]

I have gotten used to see fold as the catamorphism (or Church encoding, maybe) of a data structure, where each of the function arguments mimics one of the data structure's constructors — an alternative to pattern matching. This is the only reason it seemed weird at first sight.

Regardless of the big words, how would someone use fold as currently implemented when they don't have that "accumulator" available?

[igstan]

Actually, disregard my last question. If they don't have it, they will not use it, but this will probably limit fold's applicability.

[tjark]

The type that you propose for fold1 looks more like a map to me.

Well, that's just because either isn't a recursive data type.

[pclayton]

The type that you propose for fold1 looks more like a map to me.

Well, that's just because either isn't a recursive data type.

The proposed type for fold1 suggests the definition
fun fold1 f = proj o map f
so it's not surprising it looks like a map.