2015 002 Addition of Either module

Proposal 2015-002

Addition of Either module

Author: John Reppy
Last revised: August 17, 2015
Status: proposed
Discussion: issue #2

---

Synopsis

signature EITHER
structure Either :> EITHER

The Either structure provides a polymorphic disjoint-sum type with associated operations.

Interface

datatype ('left, 'right) either = INL of 'left | INR of 'right

val isLeft  : ('left, 'right) either -> bool
val isRight : ('left, 'right) either -> bool

val asLeft  : ('left, 'right) either -> 'left option
val asRight : ('left, 'right) either -> 'right option

val map : ('ldom -> 'lrng) * ('rdom -> 'rrng)
	  -> ('ldom, 'rdom) either
	    -> ('lrng, 'rrng) either

val mapLeft  : ('ldom -> 'lrng) -> ('ldom, 'rdom) either -> ('lrng, 'rdom) either
val mapRight : ('rdom -> 'rrng) -> ('ldom, 'rdom) either -> ('ldom, 'rrng) either

val app : ('left -> unit) * ('right -> unit)
	  -> ('left, 'right) either
	    -> unit

val appLeft  : ('left -> unit) -> ('left, 'right) either -> unit
val appRight : ('right -> unit) -> ('left, 'right) either -> unit

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

val proj : ('a, 'a) either -> 'a

val partition : (('left, 'right) either) list -> ('left list * 'right list)

Description

• datatype ('left, 'right) either = INL of 'left | INR of 'right
  defines a generic union type. We say that a value INL(x) is a left value with x as its contents. Likewise, INR(x) is a right value.

• isLeft sm
  returns true if sm is a left value.

• isRight sm
  returns true if sm is a right value.

• asLeft sm
  returns SOME(x) if sm is a left value with contents x, otherwise it returns NONE.

• asRight sm
  returns SOME(x) if sm is a right value with contents x, otherwise it returns NONE.

• map (fl, fr) sm
  maps fl over the contents of left values and fr over the contents of right values.

• mapLeft f sm
  maps the function f over the contents of left values and acts as the identity on right values.

• mapRight f sm
  maps the function f over the contents of right values and acts as the identity on left values.

• app (fl, fr) sm
  applies fl to the contents of left values and fr to the contents of right values.

• appLeft f sm
  applies f to the contents of left values and ignores right values.

• appRight f sm
  applies f to the contents of right values and ignores left values.

• fold (fl, fr) init sm
  computes fx (v, init), where v is the contents of sm and fx is either fl (if sm is a left value) or fr (if sm is a right value).

• proj sm
  projects out the contents of sm.

• partition sms
  partitions the list of sum values into a list of left values and a list of right values.

Discussion

There are a number of possible names for this type and its constructors. We have selected either for the type name (as opposed to sum), since that matches the name in Haskell. On the other hand, we use the shorter constructor names INL and INR (instead of Left and Right), because we believe that it will make patterns easier to read.

As with the list and option datatypes, it may also be useful to promote the either datatype to the pervasive environment, but we should allow experience to inform that decision.

Impact

Adopting this proposal should not affect existing programs.

Rationale

This module is a natural candidate for inclusion in the Basis Library. Similar structures have been found to be useful in other functional languages.

---

History

• [2016-08-10] Added mapLeft, mapRight, appLeft, and appRight functions, which were suggested by Andreas Rossberg.

• [2015-08-17] Added fold and proj functions, which were suggested by Matthew Fluet.

• [2015-08-03] Proposed

---