Monads/Maybe monad
Demonstrate in your programming language the following:
- Construct a Maybe Monad by writing the 'bind' function and the 'unit' (sometimes known as 'return') function for that Monad (or just use what the language already has implemented)
- Make two functions, each which take a number and return a monadic number, e.g. Int -> Maybe Int and Int -> Maybe String
- Compose the two functions with bind
AppleScript
Algebraically-reasoned defence against invalid arguments for partial functions buried deep in function nests is probably more than a light-weight scripting language will really need on an average weekday, but we can usually do most things in most languages, and stretching a language a little bit can be revealing.
What AppleScript mostly lacks here is a coherent first class function type which allows for anonymous functions. Nevertheless there is enough here to emulate first-class functions (using script objects), and we can set up a working Maybe monad without too much trouble.
It does, at least, spare us from having to structure things around try … on error … end try etc
<lang AppleScript>property e : 2.71828182846
on run {}
-- Derive safe versions of three simple functions set sfReciprocal to safeVersion(reciprocal, notZero) set sfRoot to safeVersion(root, isPositive) set sfLog to safeVersion(ln, aboveZero) -- Test a composition of these function with a range of invalid and valid arguments -- (The safe composition returns missing value (without error) for invalid arguments) map([-2, -1, -0.5, 0, 1 / e, 1, 2, e, 3, 4, 5], safeLogRootReciprocal)
end run
-- START WITH SOME SIMPLE (UNSAFE) PARTIAL FUNCTIONS:
-- Returns ERROR 'Script Error: Can’t divide 1.0 by zero.' if n = 0 on reciprocal(n)
1 / n
end reciprocal
-- Returns ERROR 'error "The result of a numeric operation was too large." number -2702' -- for all values below 0 on root(n)
n ^ (1 / 2)
end root
-- Returns -1.0E+20 for all values of zero and below on ln(n)
(do shell script ("echo 'l(" & (n as string) & ")' | bc -l")) as real
end ln
-- DERIVE A SAFE VERSION OF EACH FUNCTION -- (SEE on Run() handler)
on safeVersion(f, fnSafetyCheck)
script on call(x) if sReturn(fnSafetyCheck)'s call(x) then sReturn(f)'s call(x) else missing value end if end call end script
end safeVersion
on notZero(n)
n is not 0
end notZero
on isPositive(n)
n ≥ 0
end isPositive
on aboveZero(n)
n > 0
end aboveZero
-- DEFINE A FUNCTION WHICH CALLS A COMPOSITION OF THE SAFE VERSIONS
on safeLogRootReciprocal(x)
value of mbCompose([my sfLog, my sfRoot, my sfReciprocal], x)
end safeLogRootReciprocal
-- UNIT/RETURN and BIND functions for the Maybe monad
-- Unit / Return for maybe on maybe(n)
{isValid:n is not missing value, value:n}
end maybe
-- BIND maybe on mbBind(recMaybe, mfSafe)
if isValid of recMaybe then maybe(mfSafe's call(value of recMaybe)) else recMaybe end if
end mbBind
-- lift 2nd class function into 1st class wrapper -- handler function --> first class script object on sReturn(f)
script property call : f end script
end sReturn
-- return a new script in which function g is composed -- with the f (call()) of the Mf script -- Mf -> (f -> Mg) -> Mg on sBind(mf, g)
script on call(x) sReturn(g)'s call(mf's call(x)) end call end script
end sBind
on mbCompose(lstFunctions, value)
reduceRight(lstFunctions, mbBind, maybe(value))
end mbCompose
-- xs: list, f: function, a: initial accumulator value -- the arguments available to the function f(a, x, i, l) are -- v: current accumulator value -- x: current item in list -- i: [ 1-based index in list ] optional -- l: [ a reference to the list itself ] optional on reduceRight(xs, f, a)
set mf to sReturn(f) repeat with i from length of xs to 1 by -1 set a to mf's call(a, item i of xs, i, xs) end repeat
end reduceRight
-- [a] -> (a -> b) -> [b] on map(xs, f)
set mf to sReturn(f) set lst to {} set lng to length of xs repeat with i from 1 to lng set end of lst to mf's call(item i of xs, i, xs) end repeat return lst
end map </lang>
- Output:
{missing value, missing value, missing value, missing value, 0.5, 0.0, -0.346573590279, -0.499999999999, -0.549306144333, -0.69314718056, -0.804718956217}
Clojure
<lang clojure> (defn bind [val f] (if (nil? (:value val)) val (f (:value val)))) (defn unit [val] {:value val})
(defn opt_add_3 [n] (unit (+ 3 n))) ; takes a number and returns a Maybe number (defn opt_str [n] (unit (str n))) ; takes a number and returns a Maybe string
(bind (unit 4) opt_add_3) ; evaluates to {:value 7} (bind (unit nil) opt_add_3) ; evaluates to {:value nil} (bind (bind (unit 8) opt_add_3) opt_str) ; evaluates to {:value "11"} (bind (bind (unit nil) opt_add_3) opt_str) ; evaluates to {:value nil} </lang>
EchoLisp
Our monadic Maybe elements will be pairs (boolean . value), where value is in Maybe.domain. Functions which return something not in Maybe.domain are unsafe and return (#f . input-value), If a function is given as input a (#f . value) element, it will return this element.
<lang scheme> (define (Maybe.domain? x) (or (number? x) (string? x))) (define (Maybe.unit elem (bool #t)) (cons bool elem))
- f is a safe or unsafe function
- (Maybe.lift f) returns a safe Maybe function which returns a Maybe element
(define (Maybe.lift f) (lambda(x)
(let [(u (f x))] (if (Maybe.domain? u) (Maybe.unit u) (Maybe.unit x #f))))) ;; return offending x
- elem = Maybe element
- f is safe or unsafe (lisp) function
- return Maybe element
(define (Maybe.bind f elem) (if (first elem) ((Maybe.lift f) (rest elem)) elem))
- pretty-print
(define (Maybe.print elem) (if (first elem) (writeln elem ) (writeln '❌ elem)))
- unsafe functions
(define (u-log x) (if (> x 0) (log x) #f)) (define (u-inv x) (if (zero? x) 'zero-div (/ x)))
- (print (number->string (exp (log 3))))
(->> 3 Maybe.unit (Maybe.bind u-log) (Maybe.bind exp) (Maybe.bind number->string) Maybe.print)
→ (#t . "3.0000000000000004")
- (print (number->string (exp (log -666))))
(->> -666 Maybe.unit (Maybe.bind u-log) (Maybe.bind exp) (Maybe.bind number->string) Maybe.print)
→ ❌ (#f . -666)
- ;; (print (number->string (inverse (log 1))))
(->> 1 Maybe.unit (Maybe.bind u-log) (Maybe.bind u-inv) (Maybe.bind number->string) Maybe.print)
→ ❌ (#f . 0)
</lang>
Hoon
<lang hoon>
- - %say
|= [^ [[txt=(unit ,@tas) ~] ~]]
- - %noun
|^
%+ biff txt ;~ biff m-parse m-double == ++ m-parse |= a=@tas ^- (unit ,@ud) (rust (trip a) dem) :: ++ m-double |= a=@ud ^- (unit ,@ud) (some (mul a 2)) --
</lang>
Hoon has a built-in rune, %smsg (;~) that binds gates under a monad.
++unit is Hoon's Maybe: it is either ~ (None) or [~ u=val] (Some)
++biff is the monadic bind, which %smsg uses to wire the gates together. It's defined in the standard library here. m-parse is @tas -> (unit ,@ud), so I use biff a second time in order for the program to be called with (unit ,@tas).
++rust is one of the parser combinator runners: it parses the string `a` with the rule `dem`, returning a unit with the returned value if it success or ~ if it fails. Note that Hoon's type system is complex enough to get a strongly typed result of the parsing rule, in this case an unsigned decimal (@ud)
> +monad (some '2') [~ 4] > +monad (some 'a') ~ > +monad ~ ~
J
It's difficult to find a useful and illustrative (but simple) example of this task in J. So we shall not try to be useful.
<lang J> NB. monad implementation: unit=: < bind=: (@>)( :: ])
NB. monad utility safeVersion=: (<@) ( ::((<_.)"_)) safeCompose=:dyad define
dyad def 'x`:6 bind y'/x,unit y
)
NB. unsafe functions (fail with infinite arguments) subtractFromSelf=: -~ divideBySelf=: %~
NB. wrapped functions: safeSubtractFromSelf=: subtractFromSelf safeVersion safeDivideBySelf=: divideBySelf safeVersion
NB. task example:
safeSubtractFromSelf bind safeDivideBySelf 1
┌─┐ │0│ └─┘
safeSubtractFromSelf bind safeDivideBySelf _
┌──┐ │_.│ └──┘</lang>
JavaScript
ES5
Example: deriving and composing safe versions of reciprocal, square root and log functions.
<lang JavaScript>(function () {
'use strict';
// START WITH SOME SIMPLE (UNSAFE) PARTIAL FUNCTIONS:
// Returns Infinity if n === 0 function reciprocal(n) { return 1 / n; }
// Returns NaN if n < 0 function root(n) { return Math.sqrt(n); }
// Returns -Infinity if n === 0 // Returns NaN if n < 0 function log(n) { return Math.log(n); }
// NOW DERIVE SAFE VERSIONS OF THESE SIMPLE FUNCTIONS: // These versions use a validity test, and return a wrapped value // with a boolean .isValid property as well as a .value property
function safeVersion(f, fnSafetyCheck) { return function (v) { return maybe(fnSafetyCheck(v) ? f(v) : undefined); } }
var safe_reciprocal = safeVersion(reciprocal, function (n) { return n !== 0; });
var safe_root = safeVersion(root, function (n) { return n >= 0; });
var safe_log = safeVersion(log, function (n) { return n > 0; });
// THE DERIVATION OF THE SAFE VERSIONS USED THE 'UNIT' OR 'RETURN' // FUNCTION OF THE MAYBE MONAD
// Named maybe() here, the unit function of the Maybe monad wraps a raw value // in a datatype with two elements: .isValid (Bool) and .value (Number)
// a -> Ma function maybe(n) { return { isValid: (typeof n !== 'undefined'), value: n }; }
// THE PROBLEM FOR FUNCTION NESTING (COMPOSITION) OF THE SAFE FUNCTIONS // IS THAT THEIR INPUT AND OUTPUT TYPES ARE DIFFERENT
// Our safe versions of the functions take simple numeric arguments, but return // wrapped results. If we feed a wrapped result as an input to another safe function, // it will choke on the unexpected type. The solution is to write a higher order // function (sometimes called 'bind' or 'chain') which handles composition, taking a // a safe function and a wrapped value as arguments,
// The 'bind' function of the Maybe monad: // 1. Applies a 'safe' function directly to the raw unwrapped value, and // 2. returns the wrapped result.
// Ma -> (a -> Mb) -> Mb function bind(maybeN, mf) { return (maybeN.isValid ? mf(maybeN.value) : maybeN); }
// Using the bind function, we can nest applications of safe_ functions, // without their choking on unexpectedly wrapped values returned from // other functions of the same kind. var rootOneOverFour = bind( bind(maybe(4), safe_reciprocal), safe_root ).value;
// -> 0.5
// We can compose a chain of safe functions (of any length) with a simple foldr/reduceRight // which starts by 'lifting' the numeric argument into a Maybe wrapping, // and then nests function applications (working from right to left) function safeCompose(lstFunctions, value) { return lstFunctions .reduceRight(function (a, f) { return bind(a, f); }, maybe(value)); }
// TEST INPUT VALUES WITH A SAFELY COMPOSED VERSION OF LOG(SQRT(1/X))
var safe_log_root_reciprocal = function (n) { return safeCompose([safe_log, safe_root, safe_reciprocal], n).value; }
return [-2, -1, -0.5, 0, 1 / Math.E, 1, 2, Math.E, 3, 4, 5].map( safe_log_root_reciprocal );
})();</lang>
- Output:
[undefined, undefined, undefined, undefined, 0.5, 0, -0.3465735902799726, -0.5, -0.5493061443340549, -0.6931471805599453, -0.8047189562170503]
Ruby
OOP version using Ruby's block syntax
<lang ruby>class Maybe
def initialize(value) @value = value end
def map if @value.nil? self else Maybe.new(yield @value) end end
end
Maybe.new(3).map { |n| 2*n }.map { |n| n+1 }
- => #<Maybe @value=7>
Maybe.new(nil).map { |n| 2*n }.map { |n| n+1 }
- => #<Maybe @value=nil>
Maybe.new(3).map { |n| nil }.map { |n| n+1 }
- => #<Maybe @value=nil>
- alias Maybe#new and write bind to be in line with task
class Maybe
class << self alias :unit :new end
def bind if @value.nil? self else yield @value end end
end
Maybe.unit(3).bind { |n| Maybe.unit(2*n) }.bind { |n| Maybe.unit(n+1) }
- => #<Maybe @value=7>
Maybe.unit(nil).bind { |n| Maybe.unit(2*n) }.bind { |n| Maybe.unit(n+1) }
- => #<Maybe @value=nil>
</lang>
zkl
While I'm unsure of the utility of Monads in a dynamic type-less language, it can be done.
From the Wikipedia
Here we use the Void object as Nothing and define some functions. Sine zkl is type-less, we can consider Maybe as a native type and don't need to define it. <lang zkl>fcn bind(a,type,b){ if(type.isType(a)) b else Void } fcn just(x){ if(Deferred.isType(x)) x() else x } // force lazy evaluation fcn rtn(x) { just(x) }</lang> Since zkl is eager, add needs to gyrate a bit by creating a lazy result and evaluating that after the binds have done their bizness. <lang zkl>fcn add(mx,my){
bind(mx,Int, bind(my,Int, '+.fp(mx,my))) : rtn(_) // create a lazy mx+my to avoid eager eval
} add(1,2).println(); // two ints add(1,2.0).println(); // int and float add(self,2).println(); // class and int</lang>
- Output:
3 Void Void