# 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 [✭] 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*) ``` □ ##### Exercise: cleanup [✭✭] 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)) | _ -> () ``` □ ## 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 [✭] Implement `fmap` for the Maybe monad. □ 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 [✭] Implement `join` for the Maybe monad. `join` should be `None` if either of the two 'layers' of the input `option` are `None`. □ ##### Exercise: bind 2.0 [✭✭] 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. □ ## 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 [✭✭✭] Implement `return` and `bind` for the List monad. *Hint: List.map and List.concat might be helpful.* □ ## 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 [✭✭] Prove that the monad laws hold for our implementation of the Maybe monad. □ ## Additional Exercises ##### Exercise: list again [✭✭] Implement `fmap` and `join` for the List monad. □ ##### Exercise: fmap 2.0 [✭✭] Implement `fmap` and `join` using only `bind` and `return`. Your solution should work for any monad. □ ##### Exercise: list-sat [✭✭✭✭] Prove that the monad laws hold for our implementation of the List monad. □ ##### Exercise: state monad [✭✭✭] 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 ``` □ ##### Exercise: More Monad Laws [✭✭✭✭] Prove that your implementation of the State monad satisfies the Monad Laws. □ ##### Exercise: Backtrack [✭✭✭✭✭] 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. □