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

signature EITHERstructure Either :> EITHER

TheEither structure provides a polymorphic disjoint-sum type with associatedoperations.

datatype ('left, 'right) either = INLof 'left | INRof 'rightval isLeft  : ('left, 'right) either -> boolval isRight : ('left, 'right) either -> boolval asLeft  : ('left, 'right) either -> 'left optionval asRight : ('left, 'right) either -> 'right optionval map : ('ldom -> 'lrng) * ('rdom -> 'rrng)  -> ('ldom, 'rdom) either    -> ('lrng, 'rrng) eitherval mapLeft  : ('ldom -> 'lrng) -> ('ldom, 'rdom) either -> ('lrng, 'rdom) eitherval mapRight : ('rdom -> 'rrng) -> ('ldom, 'rdom) either -> ('ldom, 'rrng) eitherval app : ('left -> unit) * ('right -> unit)  -> ('left, 'right) either    -> unitval appLeft  : ('left -> unit) -> ('left, 'right) either -> unitval appRight : ('right -> unit) -> ('left, 'right) either -> unitval fold : ('left * 'b -> 'b) * ('right * 'b -> 'b)   -> 'b -> ('left, 'right) either -> 'bval proj : ('a, 'a) either -> 'aval partition : (('left, 'right) either) list -> ('left list * 'right list)

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

• isLeft sm
  returns true ifsm is a left value.

• isRight sm
  returns true ifsm is a right value.

• asLeft sm
  returnsSOME(x) ifsm is a left value with contentsx, otherwise it returnsNONE.

• asRight sm
  returnsSOME(x) ifsm is a right value with contentsx, otherwise it returnsNONE.

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

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

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

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

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

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

• fold (fl, fr) init sm
  computesfx (v, init), wherev is the contents ofsm andfx is eitherfl(ifsm is a left value) orfr (ifsm is a right value).

• proj sm
  projects out the contents ofsm.

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

There are a number of possible names for this type and its constructors. We have selectedeither for the type name (as opposed tosum), since that matches the name in Haskell.On the other hand, we use the shorter constructor namesINL andINR (instead ofLeftandRight), because we believe that it will make patterns easier to read.

As with thelist andoption datatypes, it may also be useful to promote theeitherdatatype to the pervasive environment, but we should allow experience to informthat decision.

Adopting this proposal should not affect existing programs.

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

• [2016-08-10] AddedmapLeft,mapRight,appLeft, andappRight functions, which weresuggested byAndreas Rossberg.

• [2015-08-17] Addedfold andproj functions, which were suggested byMatthew Fluet.

• [2015-08-03] Proposed