189: Maybe and Either: optional container types189: Maybe and Either: optional container typesThis 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.
either-ref/default.)error-object?.)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".
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.
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.
(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.
(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.
(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.
(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.
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).
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 ...)
☞ 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.
(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.
(maybe-if maybe-expr just-expr nothing-expr) [syntax]
(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]
error-object? is signaled.
(maybe-or expr ...) [syntax]
(either-or expr ...) [syntax]
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.
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.
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.)
The sample implementation is found in the repository of this SRFI.
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.
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.