# Monads Today we will practice with monads, implement a few, learn about fmap and join, and practice proving satisfaction of the Monad Laws. ## Maybe One of the simplest monads is the Maybe monad, which you might also know as the Option monad. Recall the definition of bind and return for the Maybe monad you saw in lecture:  module Maybe = struct type 'a t = None | Some of 'a let return x = Some x let bind m f = match m with | Some x -> f x | None -> None let (>>=) = bind end  return takes a value and creates a trivial option out of it, while bind takes an option and a function, and applies the function to the contents of that option, creating a new optional value. ##### Exercise: add [&#10029;] Complete the definition of add according to its specification using >>= and return:  (* * Computes the sum of two optional values. * If both x and y are of the form Some p, [add x y] should be Some(px + py) * If either x or y are None, [add x y] should be None *) let add (x: int option) (y : int option) = (*Your implementation here*)  &square; ##### Exercise: cleanup [&#10029;&#10029;] The following code uses some functions that produce optional values, but whoever wrote it clearly missed last week's lecture on Monads. Rewrite it more elegantly with bind and return.  val foo : unit -> int option val bar : int -> string option val zardoz : unit -> string option val print_option : string option -> unit let a = foo () in let b = match a with | Some x -> bar x | None -> None in let c = zardoz () in let d = match (b, c) with | Some x, Some y -> print_option (Some (x^y)) | _ -> ()  &square; ## fmap and join bind and return are not the only two useful functions for working with monads. Although bind makes it easy to build computation pipelines as you saw in the previous exercises, sometimes we only want to apply a single pre-existing function to a monad, and don't want to have to worry about upgrading it as seen in lecture. The function fmap makes this possible:  fmap : 'a t -> ('a -> 'b) -> 'b t  Notice the similarity in type to bind. The key difference to is that the function does not return a monad type, where as it does in bind. fmap also has an infix operator (>>|). If you wish, you can think of the | as denoting the end of a computation chain. We can also reverse the order of the arguments to fmap as so:  fmap' : ('a -> 'b) -> 'a t -> 'b t  This is equivalent to:  fmap' : ('a -> 'b) -> ('a t -> 'b t)  Written this way, it becomes clear that when fully applied, fmap' will take a function and apply it to the contents of its second, monadic argument. However, when partially applied, it becomes a function that will take an non-monadic function and 'upgrade' it to a monadic one. Written this way fmap' is more commonly called lift. ##### Exercise: fmap [&#10029;] Implement fmap for the Maybe monad. &square; Another useful function is join, called such because it has the effect of 'joining' a doubly 'nested' monad. To use the burrito analogy, join takes a burrito wrapped in two tortillas and returns a new burrito with the same contents, but with only one tortilla wrapper.  join : 'a t t -> 'a t  ##### Exercise: join [&#10029;] Implement join for the Maybe monad. join should be None if either of the two 'layers' of the input option are None. &square; ##### Exercise: bind 2.0 [&#10029;&#10029;] Part of what makes fmap and join such useful functions for formulating monads is that bind can be implemented for all monads using only these two functions. Do so for the Maybe monad. The Some and None constructors should not appear in your solution. &square; ## Lists and Nondeterminism Imagine, for a moment, that you had a function with a random effect. Given an input, it could return a variety of possible outputs, with no indication of what they would be based solely on the input. Examples include rolling a die, or reading a value from a network. In statistics, we often formalize the concept of multiple outcomes using a set, called a *sample space*. The sample space is the set of all possible outcomes of an action. For example, when flipping a coin, the sample space is {head, tails}. When rolling a 4-sided die, the sample space is {1, 2, 3, 4}. Sample spaces for sequential actions are simply combined into one set: the sample space for flipping two coins is {(head, tails), (head, head), (tails, head), (tails, tails)}, while the sample space for the sum of two 4-sided die rolls would be {2, 3, 4, 5, 6, 7, 8}. Since there is no native representation for sets in OCaml, we often choose to represent sets as lists, so a function to get the sample space of rolling a die might have the type:  val roll : unit -> int list  The List monad makes it convenient to work with non-deterministic functions by treating this list as a monadic value. return trivially makes a singleton list from its argument, while bind can be thought of as performing a non-deterministic computation on each element of its input set. As an example:  # let l1 = roll() in (*[1; 2; 3; 4]*) # let l2 = roll() in (*[1; 2; 3; 4]*) # l1 >>= fun x -> # l2 >>= fun y -> # return (x + y);; - : int list [2; 3; 4; 5; 3; 4; 5; 6; 4; 5; 6; 7; 5; 6; 7; 8]  This computes the result of adding two 4-sided dice rolls. Note that the list representation of the sample space has duplicates, something that its set counterpart does not. ##### Exercise: list [&#10029;&#10029;&#10029;] Implement return and bind for the List monad. *Hint: List.map and List.concat might be helpful.* &square; ## The Monad Laws We use the monad laws to help guide implementation and usage of monadic types in code, as all monads should satisfy the laws. As a refresher, they are:  LAW 1: return x >>= f ~ f x LAW 2: m >>= return ~ m LAW 3: (m >>= f) >>= g ~ m >>= (fun x -> f x >>= g)  ##### Exercise: maybe-sat [&#10029;&#10029;] Prove that the monad laws hold for our implementation of the Maybe monad. &square; ## Additional Exercises ##### Exercise: list again [&#10029;&#10029;] Implement fmap and join for the List monad. &square; ##### Exercise: fmap 2.0 [&#10029;&#10029;] Implement fmap and join using only bind and return. Your solution should work for any monad. &square; ##### Exercise: list-sat [&#10029;&#10029;&#10029;&#10029;] Prove that the monad laws hold for our implementation of the List monad. &square; ##### Exercise: state monad [&#10029;&#10029;&#10029;] Not all functional languages have imperative features like OCaml does. In pure languages like Haskell, computations that affect a state are modeled using the State monad. Complete the following definition for the State monad. Notice how it is a functor: how state is represented changes based on the use case, so we allow it to take the module representing State as an argument.  module type State = sig type t val empty : t end module StateMonad (S : State) = struct type 'a m = S.t -> ('a * S.t) let return a = fun (s : S.t) -> (a, s) let get_state m = snd (m S.empty) let join m = (*Your implementation here*) let fmap m f = (*Your implementation here*) let bind m f = (*Your implementation here*) let (>>=) = bind end  &square; ##### Exercise: More Monad Laws [&#10029;&#10029;&#10029;&#10029;] Prove that your implementation of the State monad satisfies the Monad Laws. &square; ##### Exercise: Backtrack [&#10029;&#10029;&#10029;&#10029;&#10029;] Recall A2, in which you implemented a text-based adventure game. A large part of the difficulty of this assignment was grappling with representing a state, and state-affecting computations, without using imperative features. Most likely you solved this problem by representing the state as an immutable data structure that you reconstructed during successive calls to do', which took it as an argument. With your newfound mastery of the State monad, rewrite your A2 to make use of its features. &square;