## Title

Maybe and Either: optional container types

## Author

John Cowan (text), Wolfgang Corcoran-Mathe (sample implementation)

## Status

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to `srfi-189@nospamsrfi.schemers.org`. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

- Received: 2020-03-29
- Draft #1 published: 2020-03-29
- Draft #2 published: 2020-03-31
- Draft #3 published: 2020-04-20
- Draft #4 published: 2020-05-12
- Draft #5 published: 2020-06-02
- Draft #6 published: 2020-06-05
- Draft #7 published: 2020-06-14
- Draft #8 published: 2020-07-01
- Finalized: 2020-07-14
- Revised to fix errata:
  - 2020-12-02 (Fix typo in specification of `either-ref/default`.)

## Abstract

This SRFI defines two disjoint immutable container types known as Maybe and Either, both of which can contain objects collectively known as their payload. A Maybe object is either a Just object or the unique object Nothing (which has no payload); an Either object is either a Right object or a Left object. Maybe represents the concept of optional values; Either represents the concept of values which are either correct (Right) or errors (Left).

Note that the terms Maybe, Just, Nothing, Either, Right, and Left are capitalized in this SRFI so as not to be confused with their ordinary use as English words. Thus "returns Nothing" means "returns the unique Nothing object"; "returns nothing" could be interpreted as "returns no values" or "returns an unspecified value".

## Rationale

It is common for Scheme procedures that can either succeed or fail to return a true value on success and `#f` on failure. However, if the procedure is able to return any value on success, there is no way to distinguish between a successful return of `#f` and failure. For example, the SRFI 1 procedure `find` returns `#f` when it fails, but that makes using it to search for `#f` in a list impossible. What is more, it is easy for the programmer to write code in which success is assumed and the special case of `#f` is not handled correctly; thus when using a procedure which returns a number or `#f`, like `string->number`, the programmer may assume it will always return a number, thus causing a dynamic type error when it does not.

By returning a Maybe instead, a procedure can unambiguously distinguish between success, which returns a Just object, and failure, which returns Nothing. Furthermore, the returned value cannot be further processed without removing it from its Just container except by procedures that are Maybe-aware; a number wrapped in a Just is not a number and has to be unwrapped to be used as a number.

Either is closely related to Maybe, and Right is closely related to Just. However, a Left is a container for an object which indicates why a procedure returning an Either failed, whereas Nothing indicates only a failure. Some of the Either-accepting procedures in this SRFI treat Left and Right asymmetrically; specifically, a Left is considered empty by the join, bind, and sequence procedures, and the `either-ref` procedure by default unwraps a Right but raises the payload of a Left as an exception. It is also possible to use Left and Right simply as two distinguishable types of container for a single value, or to interchange the roles of Left and Right with the special constructor `either-swap`.

Because the procedures of Scheme, unlike the functions of ML and Haskell, accept multiple arguments and return multiple values, this SRFI allows a Just, Left, or Right container to hold more than one object, or indeed no objects at all. In particular, a Just containing no objects is not the same as a Nothing: it represents success when there are no actual values to return, as in a procedure called solely for effect. The specification presented here, therefore, differs in several ways from its analogues in other languages.

## Specification

The four types Just, Nothing, Left, and Right are disjoint from each other and from all other Scheme types.

We speak of unwrapping a container when we extract its payload, and wrapping values in a container when we create the container with the values as its payload.

The following names are used for the arguments:

obj, default: Any Scheme object.

maybe: A Maybe object.

either: An Either object.

failure: A procedure that accepts zero arguments (unless specified otherwise).

success: A procedure that accepts one or more arguments.

pred: A predicate that accepts zero or more arguments.

equal: A predicate that accepts two arguments and returns a boolean value. It is not necessarily an equivalence relation.

proc: A procedure that accepts zero or more arguments and returns zero or more values.

mproc: A procedure that accepts zero or more arguments and returns zero or more values wrapped in a single Maybe or Either container.

list: A Scheme list.

producer: A procedure that accepts no arguments and returns some number of values.

It is an error (unless otherwise noted) if the procedures are passed arguments that do not have the type implied by the argument names.

### Constructors

`(just` obj ...`)`

Monadic pure. Returns the objs wrapped in a Just.

`(nothing)`

Returns the unique Nothing object.

`(right` obj ...`)`

Monadic pure. Returns the objs wrapped in a Right.

`(left` obj ...`)`

Returns the objs wrapped in a Left.

`(list->just` list`)`
`(list->left` list`)`
`(list->right` list`)`

Returns a Just / Left / Right whose values are the elements of list. Note that these procedures are not monadic; they are equivalent to `just/left/right` but accept a list rather than multiple arguments. There is no need for `list->nothing` distinct from `nothing`.

`(maybe->either` maybe obj ...`)`

If maybe is a Just, returns a Right with the same payload objects in the sense of `eqv?`; otherwise returns a Left of objs.

`(either->maybe` either`)`

If either is a Right, returns a Just with the same payload objects in the sense of `eqv?`; otherwise returns Nothing.

`(either-swap` either`)`

If either is a Left, return a Right with the same payload objects (in the sense of `eqv?`), and vice versa.

### Predicates

`(just?` obj`)`
`(nothing?` obj`)`
`(right?` obj`)`
`(left?` obj`)`

Returns `#t` if obj is a Just, Nothing, Left, or Right respectively, and `#f` otherwise.

`(maybe?` obj`)`

Returns `#t` if obj is a Maybe (that is, either a Just or Nothing) and `#f` otherwise.

`(either?` obj`)`

Returns `#t` if obj is an Either (that is, either a Right or a Left) and `#f` otherwise.

`(maybe=` equal maybe1 maybe2 ...`)`

Returns `#t` if all maybes are Nothing, or if they all are Justs and their respective payload objects are the same in the sense of equal, and `#f` otherwise.

`(either=` equal either1 either2 ...`)`

Returns `#t` if all eithers are all Lefts or all Rights and their respective payload objects are the same in the sense of equal, and `#f` otherwise.

### Accessors

`(maybe-ref` maybe failure [success]`)`

If maybe is a Just, tail-calls the procedure success on the values of its payload and returns the result. Otherwise, it tail-calls the procedure failure on no arguments and returns the result. The default value of success is `values`.

`(either-ref` either failure [success]`)`

If either is a Right, tail-calls the procedure success on the values of its payload and returns the result. Otherwise, it tail-calls the procedure failure on the values of its payload and returns the result. The default value of success is values.

`(maybe-ref/default` maybe default ...`)`
`(either-ref/default` either default ...`)`

If maybe/either is a Just/Right, returns the values of its payload; otherwise returns the defaults as multiple values.

### Join and bind

`(maybe-join` maybe`)`
`(either-join` either`)`

Monadic join. If maybe/either is a Just/Right whose single payload object is a Maybe/Either, returns that payload; if it is a Nothing/Left, returns maybe/either. In all other cases (including a Just/Right with multiple values) it is an error. Thus `(maybe-join (just (just` x`))` returns Just x and `(maybe-join (just (nothing))` returns Nothing, and similarly for `either-join`.

`(maybe-compose` mproc1 mproc2 ...`)`
`(either-compose` mproc1 mproc2 ...`)`

Returns an mproc that accepts zero or more arguments and applies the following iterative algorithm to each mproc:

The mproc is applied to the arguments and returns a Maybe/Either interim result. If the result is Nothing / a Left, it is returned as the final result. If it is a Just/Right, the next mproc is applied to the values of its payload, returning the next interim result. When no more mprocs are available, the interim result is returned as the final result.

It is an error if one of the mprocs does not accept as arguments the number of values wrapped in the Just/Right produced by its predecessor.

`(maybe-bind` maybe mproc1 mproc2 ...`)`
`(either-bind` either mproc1 mproc2 ...`)`

Monadic bind. If maybe/either is a Just/Right, it behaves as if `maybe-compose/either-compose` were applied to mprocs, and the resulting mproc applied to the payload of maybe/either. But if maybe/either is a Nothing/Left, it is immediately returned.

### Sequence operations

These procedures treat Maybes (and in some cases Eithers) as sequences of length 0 or 1. This length depends only on the type of the container and not on the number of objects it contains.

`(maybe-length` maybe`)`
`(either-length` either`)`

Return 1 if maybe/either is a Just/Right, and 0 otherwise.

`(maybe-filter` pred maybe`)`
`(maybe-remove` pred maybe`)`
`(either-filter` pred either obj ...`)`
`(either-remove` pred either obj ...`)`

If maybe/either is a Just/Right and the values of its payload satisfy / do not satisfy pred, then return maybe; otherwise, returns Nothing / a Left of objs.

`(maybe-sequence` mappable map [aggregator]`)`
`(either-sequence` mappable map [aggregator]`)`

The purpose of these procedures is to transform a collection of Maybes/Eithers of some particular type into a Maybe/Either of a collection, often of the same type.

The mappable argument is the collection to be transformed, and the map argument is the appropriate procedure that can transform it, one element at a time. The signature of map is `(`map proc mappable`)`, where proc is supplied by the implementation. Typical mappables are lists and vectors, and `map` and `vector-map` are useful map functions, though not the only possible ones.

Each element is processed as follows: If it is a Just/Right, its values are unwrapped and the aggregator function (which defaults to `list`) is applied to them. But if it is a Left/Nothing, that object is immediately returned as the value of `maybe-sequence/either-sequence`.

Assuming there are no Lefts/Nothings, the map function is then responsible for constructing the new mappable out of the results of the calls on aggregator.

For example, a list of Justs becomes a Just list of lists if the map procedure is `map` and the aggregator is `list`. In the same way, a vector of Rights containing one value each becomes a Right vector if the map procedure is `vector-map` and the aggregator is `(lambda (x) x)`.

### Protocol Conversion

The use of `->` in a Scheme procedure name generally indicates that the procedure converts, sometimes lossily, between one type of object and another. For example, `list->vector` accepts a list and returns a vector containing the same elements (in the sense of `eqv?`) in the same order.

In this section, however, `->` is used in an extended sense. As noted in the Rationale, the purpose of Maybe and Either is to provide first-class objects representing the distinction between success and failure in such a way that any number of success values (and, in the case of Either, any number of failure values) can be packaged up in a single object without reserving any values to indicate success or failure. A variety of protocols are already in use in Scheme and other Lisps to more or less perfectly represent the distinction. Some reserve a value to represent failure which cannot be returned as a success value; some handle only one success value; some are not first-class.

In order to facilitate communication between code using Maybe/Either and code using another protocol, these procedures convert between Maybe/Either objects and some of the most usual protocols. Conversion in either direction is frequently lossy.

☞ The following procedures interface between the Maybe protocol and the list protocol, which uses an empty list to represent failure and a non-empty list to represent success.

`(maybe->list` maybe`)`
`(either->list` either`)`

Returns a list whose elements are the payload of maybe/either; if maybe/either is Nothing/Left, returns the empty list. It is an error to mutate the result of this procedure.

`(list->maybe` list`)`
`(list->either` list obj ...`)`

If list is empty, returns Nothing / wraps objs in a Left and returns it; otherwise, wraps the list elements in a Just/Right and returns that.

☞ The following procedures interface between the Maybe and Either protocols and the truth protocol, which uses `#f` to represent failure and a single true value to represent success.

`(maybe->truth` maybe`)`
`(either->truth` either`)`

If maybe/either is a Just/Right, returns its payload; otherwise returns `#f`. It is an error if the Just/Right does not have exactly one value.

`(truth->maybe` obj`)`
`(truth->either` obj fail-obj ...`)`

If obj is `#f`, return Nothing / a Left of fail-objs; otherwise, return a Just/Right whose payload is obj.

☞ The following procedures interface between the Maybe protocol and the list-truth protocol, which uses `#f` to represent failure and a list to represent success.

`(maybe->list-truth` maybe`)`
`(either->list-truth` either`)`

If maybe/either is a Just/Right, returns a list whose elements are the payload; otherwise, returns `#f`. It is an error to mutate the result of this procedure.

`(list-truth->maybe` list-or-false`)`
`(list-truth->either` list-or-false obj ...`)`

If list-or-false is `#f`, returns Nothing / a Left of objs; otherwise, wraps the list elements in a Just/Right and returns it.

☞ The following procedures interface between the Maybe and Either protocols and the generation protocol, which uses an end-of-file object to represent failure and any other value to represent success.

`(maybe->generation` maybe`)`
`(either->generation` either`)`

If maybe/either is a Just/Right, then its payload is returned. It is an error if the Just/Right does not have exactly one value. If maybe/either is Nothing / a Left, then an end-of-file object is returned.

`(generation->maybe` obj`)`
`(generation->either` obj fail-objs ...`)`

If obj is an end-of-file object, return Nothing / a Left of fail-objs. Otherwise, return obj wrapped in a Just/Right.

☞ The following procedures interface between the Maybe and Either protocols and the values protocol, which returns one or more values to represent success and zero values to represent failure.

`(maybe->values` maybe`)`
`(either->values` either`)`

If maybe/either is a Just/Right, returns the values of its payload; otherwise returns no values.

`(values->maybe` producer`)`
`(values->either` producer fail-obj ...`)`

These procedures invoke producer with no arguments. If no values are returned, Nothing / Left of fail-objs is returned. Otherwise the values are wrapped in a Just/Right and returned.

☞ The following procedures interface between the Maybe protocol and the two-values protocol, which returns `#f` and `#f` to represent failure and a single value and `#t` to represent success. (This protocol is more often used in Common Lisp, where additional values are automatically discarded if the continuation expects only one.)

`(maybe->two-values` maybe`)`

If maybe is a Just, returns the value of its payload and the additional value `#t`; otherwise returns two values, both `#f`. It is an error if maybe does not have exactly one value.

`(two-values->maybe` producer`)`

This procedure is the inverse of `maybe->two-values`. It invokes producer with no arguments. If the second value is true, the first value is wrapped in a Just and returned; otherwise, Nothing is returned.

`(exception->either` pred thunk`)`

This procedure is in a sense the inverse of `maybe-ref`. A call to thunk is made, wrapped in an exception handler that examines any exception signaled during thunk's execution. If the condition object satisfies pred, it is wrapped in a Left which is then returned; if it does not, the exception is reraised. But if no exception is raised, the values returned by `thunk` are wrapped in a Right and the Right is returned.

### Map, fold and unfold

`(maybe-map` proc maybe`)`
`(either-map` proc either`)`

Monadic map. If maybe/either is a Just/Right, applies proc to the payload values and wraps the returned values as a Just/Right; otherwise returns maybe/either.

`(maybe-for-each` proc maybe`)`
`(either-for-each` proc either`)`

If maybe/either is a Just/Right, applies proc to the payload values and discards the result; otherwise does nothing. Returns an unspecified result.

`(maybe-fold` kons nil maybe`)`
`(either-fold` kons nil either`)`

If maybe/either is a Just/Right, kons is invoked on the values of its payload and the additional value nil and the result is returned; otherwise, nil is returned.

`(maybe-unfold` stop? mapper successor seed ...`)`
`(either-unfold` stop? mapper successor seed ...`)`

If stop? returns true on seeds, a Nothing / a Left of seeds is returned. Otherwise, successor is applied to seeds. If stop? returns false on the results of successor, it is an error. But if the second call to stop? returns true, mapper is applied to seeds and the results are wrapped in a Just/Right and returned.

### Syntax

`(maybe-if` maybe-expr just-expr nothing-expr`)` [syntax]

Equivalent to `(if (just?` maybe-expr`)` just-expr nothing-expr`)`, except that an error satisfying `error-object` is signaled if maybe-expr does not evaluate to a Maybe.

`(maybe-and` expr ...`)` [syntax]
`(either-and` expr ...`)` [syntax]

The exprs are evaluated in order. If an expr evaluates to a Nothing / Left, it is returned without evaluating any more expressions. Otherwise, the last Just / Right is returned. If there are no exprs, then a Just/Right of an unspecified value is returned. If an expr does not evaluate to a Maybe/Either, an error satisfying `error-object` is signaled.

`(maybe-or` expr ...`)` [syntax]
`(either-or` expr ...`)` [syntax]

The exprs are evaluated in order. If an expr evaluates to a Just/Right, it is returned without evaluating any more expressions. Otherwise, the last Nothing/Left is returned. If there are no exprs, then Nothing / a Left of an unspecified value is returned. If an expr does not evaluate to a Maybe/Either, an error satisfying `error-object` is signaled.

`(maybe-let* (` claw ... `) .` body`)` [syntax]
`(either-let* (` claw ... `) .` body`)` [syntax]

The Maybe/Either equivalent of `and-let*` from SRFI 2. However, instead of testing whether a claw is true or false, it tests whether it is Just/Right or Nothing/Left. If a claw does not evaluate to a Maybe/Either, an error satisfying `error-object` is signaled. The same is true if a claw evaluates to a Just or Right that wraps zero values or more than one value.

A claw is either a bound identifier, or a list of length 1, in which case it is an expression, or a list of length 2, in which case it is a variable and an expression. In either case, the value of the claw is the value of the bound variable or expression. If the value of a claw is Nothing / a Left, the expression immediately returns that value. But if the value of a claw is a Just/Right, then the variable (if any) is bound to its unwrapped value; the scope of this binding is any remaining claws and the body.

If the values of all the claws are Just/Right, then the body is evaluated as if it were in a `(let () ...)`, and its values are wrapped in a Just/Right and returned.

`(maybe-let*-values (` claw ... `) .` body`)` [syntax]
`(either-let*-values (` claw ... `) .` body`)` [syntax]

The same as `maybe/either-let*`, except that the first element of a two-element claw is a <formals> from `lambda`, and the variables mentioned in it (if any) are bound to the values that result from unpacking a Just/Right. Note that a claw with a single variable in `maybe/either-let*` is bound to the sole value contained in the Just/Right, whereas in `maybe/either-let*-values`, it is bound to a list of all the values, just as in a `lambda` expression, a <formals> consisting of a single variable is bound to a list of all the procedure arguments.

`(either-guard` pred-expr `.` body`)` [syntax]

The syntactic analogue of `exception->either`. The body is evaluated, and the values it produces are wrapped in a Right and returned, unless an exception occurs. If the condition object that is raised satisfies the predicate that is the value of pred-expr, the condition object is wrapped in a Left and returned; otherwise the condition is reraised as if by `raise-continuable`.

### Trivalent logic

These procedures provide trivalent logic in the style of SQL on Maybe objects containing a single value. For the purposes of this section, an object counts as false if it is Just `#f`, true if it is Just anything else. It is an error if any argument is not a Maybe.

Unlike `and` and `or`, `tri-and` and `tri-or` are procedures and not syntax, because determining their value requires that all the arguments be evaluated in order to provide correct SQL-style semantics. For example, `(and #f (nothing))` will return `#f` immediately without evaluating its second argument, but `(tri-and (just #f) (nothing))` will return Nothing.

`(tri-not` maybe`)`

Returns Just `#t` if maybe is false, Just `#f` if maybe is true, and Nothing if maybe is Nothing.

`(tri=?` maybe1 maybe2 ...`)`

Similar to `boolean=?`, returning Just `#t` if all the maybes are true or if all are false. Otherwise, if any maybe is Nothing or any two maybes have different (trivalent) truth values, returns Just `#f`.

Note: this function is not transitive and therefore is not an equivalence relation.

`(tri-and` maybe ...`)`

If all maybes are true, Just `#t` is returned. If any maybe is false or Nothing, then the first such maybe is returned. If there are no arguments, Just `#t` is returned.

`(tri-or` maybe ...`)`

If all maybes are false, Just `#f` is returned. If any maybe is true or Nothing, then the first such maybe is returned. If there are no arguments, Just `#f` is returned.

`(tri-merge` maybe ...`)`

If any maybes are true or false, then the first such maybe is returned. If all maybes are Nothing, then Nothing is returned. If there are no arguments, Nothing is returned.

## Examples

Here is a variant of SRFI 1 `find` that returns a Maybe, and so can be safely used to search for `#f` in a list, just like any other value:

    (define (maybe-find pred list)
      (cond
        ((null? list) (nothing))
        ((pred (car list)) (just (car list)))
        (else (maybe-find pred (cdr list)))))

The following examples show how `find` and `maybe-find` differ in their results:

    (define (atom? obj) (not (pair? obj)))
    (define with-t '((1) #t (3) 4 5))
    (define with-f '((1) #f (3) 4 5))
    (define without '((1) (2) (3) (4) (5)))

    (find atom? with-t) => #t
    (find atom? with-f) => #f
    (find atom? without) => #f

    (maybe-find atom? with-t) => Just #t
    (maybe-find atom? with-f) => Just #f
    (maybe-find atom? without) => Nothing

And here is `head`, which is more general than `car` because it lets the caller figure out what happens if its argument is not a pair and can handle an argument that is either an actual pair or Just a pair.

    (define (head x)
      (cond
        ((pair? x) (just (car x)))
        ((and (just? x) (pair? (maybe-ref x))) (just (car (maybe-ref x))))
        (else (nothing))))

In other words, if the argument to `head` is a pair, whether wrapped in a Just or not, the result is the car of that pair wrapped in a Just; in all other cases, the result is Nothing. (There are simpler ways to do this using more advanced procedures.)

## Implementation

The sample implementation is found in the repository of this SRFI.

## Acknowledgements

The Maybe and Either types and their procedures are based on Scala's Option and Either types, though the name "Maybe" comes from Haskell. (I think "Maybe" is catchier than "Option", which ultimately comes from ML.) The trivalent logic is loosely based on Chicken's `sql-null` egg.

Great thanks to Marc Nieper-Wißkirchen, whose insistence that Scheme's multiple arguments and multiple values required an extension of this SRFI to handle them correctly. Thanks also to Shiro Kawai and the other participants on the SRFI 189 mailing list.

## Copyright

Copyright © John Cowan, Wolfgang Corcoran-Mathe (2020).

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.