Monads

6.S050

Jack Feser

Created: 2023-05-11 Thu 11:06

Debuggable Functions

let plusone x = x + 1
let square x = x * x

produce debug output in addition computation

Debuggable Functions

let plusone' x = (x + 1, "added one")
let square' x = (x * x, "squared")

Composing Debuggable Functions

plusone (square 5) => 26
plusone' (square' 5) => Type error

Composing Debuggable Functions

let (x, msg1) = square' 5 in
let (y, msg2) = plusone' x in
(y, msg1 ^ " " ^ msg2)

Composing Debuggable Functions with a Helper

val bind : (int * string) ->
	   (int -> (int * string)) ->
	   (int * string)
let bind (x, s) f = let (y, s') = f x in (y, s ^ s')

bind (bind (5, "") square') plusone' => (26, "plusone' square'")

Composing Debuggable Functions with a Helper

val bind : (int * string) ->
	   (int -> (int * string)) ->
	   (int * string)
let bind (x, s) f = let (y, s') = f x in (y, s ^ s')

val return : int -> (int * string)
let return x = (x, "")

bind (bind (return 5) square') plusone' => (26, "plusone' square'")

Random Numbers

val random : state -> (int * state)

Random Numbers

let add_rand x state =
  let (state, y) = random state in
  (x + y, state)

Composing Random Functions

let add_rand_twice x state =
  let (x', state') = add_rand x state in
    add_rand x' state'

Composing Random Functions with a Helper

val bind : (state -> 'a * state) ->
	   ('a -> (state -> 'b * state)) ->
	   (state -> 'b * state)
let bind r f state = let (x, state') = r in f x state'

val return : 'a -> (state -> 'a * state)
let return x state = (x, state)

let add_rand_twice x state =
  bind (bind (return x) add_rand) add_rand

Extracting the Common Pattern

(* debug info *)
val bind : (int * string) ->
	   (int -> (int * string)) ->
	   (int * string)
val return : int -> (int * string)

(* random numbers *)
val bind : (state -> 'a * state) ->
	   ('a -> (state -> 'b * state)) ->
	   (state -> 'b * state)
val return : 'a -> (state -> 'a * state)

(* general purpose *)
val bind : ? -> ? -> ?
val return : ? -> ?

Extracting the Common Pattern

(* debug info *)
val bind : ('a * string) ->
	   ('a -> ('b * string)) ->
	   ('b * string)
val return : 'a -> ('a * string)

(* random numbers *)
val bind : (state -> 'a * state) ->
	   ('a -> (state -> 'b * state)) ->
	   (state -> 'b * state)
val return : 'a -> (state -> 'a * state)

val bind : ? -> ? -> ?
val return : ? -> ?

Extracting the Common Pattern

(* debug info *)
type 'a m = 'a * string
val bind : 'a m -> ('a -> 'b m) -> 'b m
val return : 'a -> 'a m

(* random numbers *)
type 'a m = state -> 'a * state
val bind : 'a m -> ('a -> 'b m) -> 'b m
val return : 'a -> 'a m

Monads

this pattern turns out to be very common
- maybe not surprising; it's quite general

type 'a m
val bind : 'a m -> ('a -> 'b m) -> 'b m
val return : 'a -> 'a m

in the examples, 'a m is the "data we care about" + "some extra stuff"
- integer result + debug info
- random output + state of rng

A bit of Notation

val bind : 'a m -> ('a -> 'b m) -> 'b m
val (>>=) : 'a m -> ('a -> 'b m) -> 'b m

bind (return 5) plusone' == (return 5) >>= plusone'

pipeline notation: value >>= consumer

Ok, but why?

So far we've seen:

Functions that pass around state

Does that really justify the hype? No, not really.

More generally, we can use these operators to compose functions that produce a value & an effect:

Generating a new debug message
Advancing the state of the RNG
Failing (with/without error message)
Performing IO

Maybe

val divide : int -> int -> int
let divide x y = x / y

divide 4 0 ==> ?

Maybe

val divide : int -> int -> int
let divide x y = if y = 0 then failwith "divide by zero!" else x / y

loses referential transparency

Maybe

divide is really a partial function
- divide x 0 isn't defined
return a value that indicates whether divide is defined or not

(* a maybe type *)
type 'a m = Some of 'a | None

val divide : int -> int -> int m
let divide x y = if y = 0 then None else Some (x / y)

Maybe

How do we compose functions that return Maybe?

Maybe

type 'a m = Some of 'a | None

val divide : int -> int -> int m
val add : int -> int -> int

val divide_and_add : int -> int -> int -> int m
let divide_and_add x y z =
  match divide x y with
  | None -> None
  | Some q -> Some (add z q)

divide_and_add 6 2 1 ==> Some 4
divide_and_add 7 0 2 ==> None

Maybe

val bind : 'a m -> ('a -> 'b m) -> 'b m
val return : 'a -> 'a m

val divide_and_add : int -> int -> int -> int m
let divide_and_add x y z =
  bind (divide x y) (fun q -> return (add z q))

Maybe

val bind : 'a m -> ('a -> 'b m) -> 'b m
val return : 'a -> 'a m

val divide_and_add : int -> int -> int -> int m
let divide_and_add x y z =
  divide x y >>= fun q -> return (add z q)

Maybe

val bind : 'a m -> ('a -> 'b m) -> 'b m
let bind x f = ??

val return : 'a -> 'a m
let return x = ??

Maybe

val bind : 'a m -> ('a -> 'b m) -> 'b m
let bind x f = ??

val return : 'a -> 'a m
let return x = Some x

Maybe

val bind : 'a m -> ('a -> 'b m) -> 'b m
let bind x f = match x with
  | Some y -> f y
  | None -> None

val return : 'a -> 'a m
let return x = Some x

Maybe

val bind : 'a m -> ('a -> 'b m) -> 'b m
val return : 'a -> 'a m

val divide_and_add : int -> int -> int -> int m
let divide_and_add x y z =
  divide x y >>= fun q -> return (add z q)

can we make this a little cleaner?
- add doesn't take or return a maybe, so we have to wrap it up with a return

Maybe

val bind : 'a m -> ('a -> 'b m) -> 'b m
val return : 'a -> 'a m

(* one more combinator! *)
val map : 'a m -> ('a -> 'b) -> 'b m

val divide_and_add : int -> int -> int -> int m
let divide_and_add x y z =
  map (divide x y) (add z)

Maybe

val bind : 'a m -> ('a -> 'b m) -> 'b m
val return : 'a -> 'a m

(* one more combinator! *)
val map : 'a m -> ('a -> 'b) -> 'b m
val (>>|) : 'a m -> ('a -> 'b) -> 'b m

val divide_and_add : int -> int -> int -> int m
let divide_and_add x y z =
  divide x y >>| add z

Maybe

val map : 'a m -> ('a -> 'b) -> 'b m
let map x f = ??

Maybe

val map : 'a m -> ('a -> 'b) -> 'b m
let map x f = match x with
  | Some y -> Some (f y)
  | None -> None

Maybe

val map : 'a m -> ('a -> 'b) -> 'b m
let map x f = match x with
  | Some y -> return (f y)
  | None -> None

Maybe

val map : 'a m -> ('a -> 'b) -> 'b m
let map x f = bind x (fun y -> return (f y))

Error

Maybe lets us compose functions that sometimes fail
What if we want to keep track of why they failed?

type 'a m = Ok of 'a | Error of string

let divide x y =
  if y = 0 then Error "divide by zero!" else Ok (x / y)

divide_and_add 6 2 1 ==> Ok 4
divide_and_add 7 0 2 ==> Error "divide by zero!"

Error

let's implement bind and return

type 'a m = Ok of 'a | Error of string

val return : 'a -> 'a m
let return x = ??

Error

type 'a m = Ok of 'a | Error of string

val return : 'a -> 'a m
let return x = Ok x

Error

type 'a m = Ok of 'a | Error of string

val return : 'a -> 'a m
let return x = Ok x

val bind : 'a m -> ('a -> 'b m) -> 'b m
let bind x f = ??

Error

type 'a m = Ok of 'a | Error of string

val return : 'a -> 'a m
let return x = Ok x

val bind : 'a m -> ('a -> 'b m) -> 'b m
let bind x f = match x with
  | Ok x -> f x
  | Error e -> Error e

IO

original question: "how do we make programs that do IO referentially transparent?"

IO

(* a computation that does some IO and produces an 'a *)
type 'a io

(* sequencing IO computations *)
val bind : 'a io -> ('a -> 'b io) -> 'b io

val return : 'a -> 'a io

IO

val read_char : char io
val write_char : char -> unit io

val read_line : string io
val write_line : string -> unit io

IO

let say_hello =
  write_line "What's your name? "
  >>= fun () -> read_line
  >>= fun name -> write_line ("Hello " ^ name ^ "!\n")

Peeking inside IO

type 'a io =
  | Read : string io
  | Write : string -> unit io
  | Bind : 'a io * ('a -> 'b io) -> 'b io
  | Return : 'a -> 'a io

let read_line = Read
let write_line s = Write s
let bind m f = Bind (m, f)
let (>>=) = bind
let return x = Return x

Peeking inside IO

let say_hello =
  write_line "What's your name? "
  >>= fun () -> read_line
  >>= fun name -> write_line ("Hello " ^ name ^ "!\n")

let say_hello' =
  Bind (Write "What's your name?",
	fun () -> Bind (Read,
		     fun name -> Bind (Write ("Hello " ^ name ^ "!"),
				    fun () -> Return ())))

Peeking inside IO

let rec run : 'a. 'a io -> 'a =
  fun (type a) (io : a io) : a ->
    match io with
    | Read -> "Frank"
    | Write s -> print_endline s
    | Bind (m, f) -> run (f (run m))
    | Return x -> x
;;

run say_hello

: What's your name?
: Hello Frank!
:

Are Monads Required/Inevitable?

not really
Haskell (and pure functional programmers in general) could have used a number of different approaches to sequence IO effects
monads are just a particularly simple one
- and maybe not the simplest!
- algebraic effects (discussed earlier) are less powerful, but more composable