Monads
In functional programming, the Monad pattern is a general solution to the problem of nesting (or 'composing') functions when the data to which they apply is enclosed in some kind of useful wrapping. It involves implementing two higher-order functions which, between them, can take care of ensuring that the nested (data-transforming) functions are not choked by being called on unexpected types of data. (Wrapped data, when they were expecting something raw and unwrapped).
The two higher-order functions which make up the monad pattern handle the details of: 1. wrapping and unwrapping data, and 2. Providing other functions with direct access to the unwrapped data contents. Delegating the mechanics to these two meta-functions allows the programmer to work with a simple and well-understood generic model, and to nest functions transparently.
The two monad functions are sometimes named as follows:
- 'Return' which wraps a piece of raw data, returning the wrapped 'monadic' form
- 'Bind' which applies some other function directly to the contents of a monadic wrapper, obtains a result, and returns a wrapped form of that result.
Commonly used monads include the Maybe monad, (in which the wrapper encodes whether or not the raw content is a legal value for a particular type of function), and the List monad, in which raw data is simply contained in a list. When lists are used to represent a range of possible values for a variable name, nesting functions which act on these lists allows a convenenient encoding of cartesian products and set comprehensions. In this context, the two higher order monad functions ensure that each data-transforming function (in a nest or composition of such functions) gets the right kind of argument (Raw atomic values versus one or more values 'wrapped in' a list).
(Other frequently used monads are the IO monad and the State monad)
Demonstrate in your programming language the following:
- Construct a Monad (preferably the Option/Maybe Monad or the List Monad) by making bind and unit 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
andInt -> Maybe String
- Compose the two functions with bind
Clojure
Maybe Monad
<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>
List Monad
<lang clojure> (defn bind [coll f] (apply vector (mapcat f coll))) (defn unit [val] (vector val))
(defn doubler [n] [(* 2 n)]) ; takes a number and returns a List number (def vecstr (comp vector str)) ; takes a number and returns a List string
(bind (bind (vector 3 4 5) doubler) vecstr) ; evaluates to ["6" "8" "10"] (-> [3 4 5]
(bind doubler) (bind vecstr)) ; also evaluates to ["6" "8" "10"]
</lang>
J
Note that J documentation mentions "monad" but that is an older (much older) use of the term from what is intended here. J documentation uses "box" <
to describe the operation mentioned here.
That said, here is an implementation which might be adequate for the current task description:
<lang J>bind=: S:0 unit=: boxopen
m_num=: unit m_str=: unit@":</lang>
Task example:
<lang J> m_str bind m_num 5 ┌─┐ │5│ └─┘</lang>
Ruby
List Monad
<lang ruby> class Array
def bind(f) map(&f).reduce(:concat) end def self.unit(*args) args end
end
inc = -> e { Array.unit(e + 1) } str = -> e { Array.unit(e.to_s) }
Array.unit(3,4,5).bind(inc).bind(str) #=> ["4", "5", "6"]
- Note that inc and str cannot be composed directly,
- as they don't have compatible type signature.
- Due to duck typing (Ruby will happily turn arrays into strings),
- in order to show this, a new function will have to be used:
doub = -> n {[2*n]} [3,4,5].bind(inc).bind(doub) #=> [8, 10, 12]
- Direct composition will cause a TypeError, as Ruby cannot evaluate 2*[4, 5, 6]
comp = -> f, g {-> x {f[g[x]]}} [3,4,5].bind(comp[doub, inc]) #=> TypeError: Array can't be coerced into Fixnum
- Composition needs to be defined in terms of bind
class Array
def bind_comp(f, g) bind(g).bind(f) end
end
[3,4,5].bind_comp(doub, inc) #=> [8, 10, 12] </lang>
zkl
While I'm unsure of the utility of Monads in a dynamic type-less language, it can be done.
Maybe Monad
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
List Monad
Here we create a class to do Monad like things. Unlike Ruby, we can't augment the baked in List/Array object so this more verbose. Also unlike Ruby, we can directly compose as we are applying the composition to each element (vs the list-as-object). <lang zkl>class MList{
fcn init(xs){ var list=vm.arglist } fcn bind(f) { list=list.apply(f); self } fcn toString{ list.toString() }
}</lang> <lang zkl>inc:=Op("+",1); // '+(1) str:="toString"; MList(3,4,5).bind(inc).bind(str).println(" == (4,5,6)");
doub:=Op("*",2); MList(3,4,5).bind(inc).bind(doub).println(" == (8,10,12)");
comp:=Utils.Helpers.fcomp; // comp(f,g) == f.g == f(g(x)) MList(3,4,5).bind(comp(doub,inc)).println(" == (8,10,12)");</lang>
- Output:
L("4","5","6") == (4,5,6) L(8,10,12) == (8,10,12) L(8,10,12) == (8,10,12)