As we discussed in class, there are clear patterns shared between lists and option types and trees, so perhaps you can see why people want to figure out the general structures. But it probably isn't obvious yet why it would be useful to do so. To a large extent, this will only emerge over the next few classes. But we'll begin to demonstrate the usefulness of these patterns by talking through a simple example, that uses the monadic functions of the Option/Maybe box type. OCaml's `/` operator expresses integer division, which throws away any remainder, thus: # 11/3;; - : int = 3 Integer division presupposes that its second argument (the divisor) is not zero, upon pain of presupposition failure. Here's what my OCaml interpreter says: # 11/0;; Exception: Division_by_zero. Say we want to explicitly allow for the possibility that division will return something other than a number. To do that, we'll use OCaml's `option` type, which works like this: # type 'a option = None | Some of 'a;; # None;; - : 'a option = None # Some 3;; - : int option = Some 3 So if a division is normal, we return some number, but if the divisor is zero, we return `None`. As a mnemonic aid, we'll prepend a `safe_` to the start of our new divide function.
```let safe_div (x : int) (y : int) =
match y with
| 0 -> None
| _ -> Some (x / y);;

(* an Ocaml session could continue with OCaml's response:
val safe_div : int -> int -> int option = fun
# safe_div 12 2;;
- : int option = Some 6
# safe_div 12 0;;
- : int option = None
# safe_div (safe_div 12 2) 3;;
~~~~~~~~~~~~~
Error: This expression has type int option
but an expression was expected of type int
*)
```
This starts off well: dividing `12` by `2`, no problem; dividing `12` by `0`, just the behavior we were hoping for. But we want to be able to use the output of the safe-division function as input for further division operations. So we have to jack up the types of the inputs:
```let safe_div2 (u : int option) (v : int option) =
match u with
| None -> None
| Some x ->
(match v with
| None -> None
| Some 0 -> None
| Some y -> Some (x / y));;

(* an Ocaml session could continue with OCaml's response:
val safe_div2 : int option -> int option -> int option =
# safe_div2 (Some 12) (Some 2);;
- : int option = Some 6
# safe_div2 (Some 12) (Some 0);;
- : int option = None
# safe_div2 (safe_div2 (Some 12) (Some 0)) (Some 3);;
- : int option = None
*)
```
Calling the function now involves some extra verbosity, but it gives us what we need: now we can try to divide by anything we want, without fear that we're going to trigger system errors. I prefer to line up the `match` alternatives by using OCaml's built-in tuple type:
```let safe_div2 (u : int option) (v : int option) =
match (u, v) with
| (None, _) -> None
| (_, None) -> None
| (_, Some 0) -> None
| (Some x, Some y) -> Some (x / y);;
```
So far so good. But what if we want to combine division with other arithmetic operations? We need to make those other operations aware of the possibility that one of their arguments has already triggered a presupposition failure:
```let safe_add (u:int option) (v:int option) =
match (u, v) with
| (None, _) -> None
| (_, None) -> None
| (Some x, Some y) -> Some (x + y);;

(* an Ocaml session could continue with OCaml's response:
val safe_add : int option -> int option -> int option =
# safe_add (Some 12) (Some 4);;
- : int option = Some 16
# safe_add (safe_div (Some 12) (Some 0)) (Some 4);;
- : int option = None
*)
```
```let (>>=) (u : 'a option) (j : 'a -> 'b option) : 'b option =
match u with
| None -> None
| Some x -> j x;;

let map2 (f : 'a -> 'b -> 'c) (u : 'a option) (v : 'b option) : 'c option =
u >>= (fun x -> v >>= (fun y -> Some (f x y)));;

let safe_add3 = map2 (+);;    (* that was easy *)

let safe_div3 (u: int option) (v: int option) =
u >>= (fun x -> v >>= (fun y -> if 0 = y then None else Some (x / y)));;
```
Haskell has an even more user-friendly notation for defining `safe_div3`, namely: safe_div3 :: Maybe Int -> Maybe Int -> Maybe Int safe_div3 u v = do {x <- u; y <- v; if 0 == y then Nothing else Just (x `div` y)} You can read more about that here: * [Haskell wikibook on do-notation](http://en.wikibooks.org/wiki/Haskell/do_Notation) * [Yet Another Haskell Tutorial on do-notation](http://en.wikibooks.org/wiki/Haskell/YAHT/Monads#Do_Notation) Let's see our new functions in action:
```(* an Ocaml session could continue with OCaml's response:
# safe_div3 (safe_div3 (Some 12) (Some 2)) (Some 3);;
- : int option = Some 2
#  safe_div3 (safe_div3 (Some 12) (Some 0)) (Some 3);;
- : int option = None
# safe_add3 (safe_div3 (Some 12) (Some 0)) (Some 3);;
- : int option = None
*)
```