12 Assignment 12: Monads

Our biggest mistake: using the scary term ‘monad’ rather than ‘warm fuzzy thing’.

——Simon Peyton Jones

Preliminaries

Do not use side effects in Racket (as in set! let/cc printf) in this assignment.

Assignment

Monadic if

1. Define and test a function

   ; ifM : [Monad M] [M Boolean] [M α] [M α] -> [M α]

   As the type signature above shows, your function ifM should take four arguments: a monad (a list with two methods as described above), a Boolean computation mb in the monad, and two other computations mt and mf in the same monad. What ifM should return is a computation that begins by performing mb. If the result of mb is #t, then perform mt next; if it’s #f, then perform mf next. You only need to use bind once.

   > (ifM identity-monad #t 3 4)

   3

   > (ifM identity-monad #f 3 4)

   4

   > (ifM writer-monad '(writer "h" #t) '(writer "i" 3) '(writer "ello" 4))

   '(writer "hi" 3)

   > (ifM writer-monad '(writer "h" #f) '(writer "i" 3) '(writer "ello" 4))

   '(writer "hello" 4)

Monadic filter

2. Define and test a function

   ; filterM : [Monad M] [α -> [M Boolean]] [ListOf α] -> [M [ListOf α]]

   As the type signature above shows, your function filterM should take three arguments: a monad, a function f from each list element to a Boolean computation, and a list. What filterM should return is a computation that invokes (f x) for each element x of the list (from left to right). The result of the computation should be the list of those elements x for which the computation (f x) produced true.
   This function filterM is the monadic version of filter, so passing it the identity-monad should recover filter:

   > (filterM identity-monad odd? '(3 20 5))

   '(3 5)

   > (filterM writer-monad

   (lambda (s) `(writer ,s ,(< (string-length s) 5)))

   '("hello" "311" "world" "42"))

   '(writer "hello311world42" ("311" "42"))

3. Define and test a function subsets that takes a list as input and return the list of its subsets, starting with the empty subset.

   > (subsets '(pineapple sausage onion))

   '(()

   (onion)

   (sausage)

   (sausage onion)

   (pineapple)

   (pineapple onion)

   (pineapple sausage)

   (pineapple sausage onion))

   Your definition must use filterM with the list-monad, and should be very short.

4. Define and test a function knapsack that takes a list of positive numbers as input and greedily stuffs the numbers into a knapsack that holds at most 100. The function should work through the list from left to right. For each number, if there is still room in the knapsack, then put it in. In the following example, the 40 doesn’t fit because the knapsack is already holding 70 at that point, and the 9 doesn’t fit because the knapsack is already holding 95 at that point.

   > (knapsack '(50 10 10 40 25 9 3 3 4))

   '(50 10 10 25 3)

   Your definition must use filterM with the state-monad.

Monadic map

5. Define and test a function

   ; mapM : [Monad M] [α -> [M β]] [ListOf α] -> [M [ListOf β]]

   As the type signature above shows, your function mapM should take three arguments: a monad, a function f from each list element to a computation, and a list. What mapM should return is a computation that invokes (f x) for each element x of the list (from left to right). The result of the computation should be the list of each result produced by (f x).
   This function mapM is the monadic version of map, so passing it the identity-monad should recover map:

   > (mapM identity-monad add1 '(3 20 5))

   '(4 21 6)

   > (mapM writer-monad

   (lambda (s) `(writer ,s ,(string-length s)))

   '("hello" "311" "world" "42"))

   '(writer "hello311world42" (5 3 5 2))

6. Some restaurants offer meal deals like this: the customer can choose one appetizer out of a list of appetizers, one main entrée out of a list of main entrées, and one dessert out of a list of desserts. That would make a 3-course meal, but some restaurants offer 2-course meals or 5-course meals.

   Define and test a function deals that takes a list of courses (each course is a list of options to choose from) and returns a list of meals (each meal is a list of chosen options).

   > (deals '((soup salad fries)

   (sandwich stir-fry)

   (chocolate tofu affogato)))

   '((soup sandwich chocolate)

   (soup sandwich tofu)

   (soup sandwich affogato)

   (soup stir-fry chocolate)

   (soup stir-fry tofu)

   (soup stir-fry affogato)

   (salad sandwich chocolate)

   (salad sandwich tofu)

   (salad sandwich affogato)

   (salad stir-fry chocolate)

   (salad stir-fry tofu)

   (salad stir-fry affogato)

   (fries sandwich chocolate)

   (fries sandwich tofu)

   (fries sandwich affogato)

   (fries stir-fry chocolate)

   (fries stir-fry tofu)

   (fries stir-fry affogato))

   Your definition must use mapM with the list-monad, and should be very short.

7. Define and test a function cumulative that takes a list of numbers as input and returns an equally long list of numbers. Each output number should be the sum of all the numbers from the beginning to the corresponding place in the input list.

   > (cumulative '(3 20 5))

   '(3 23 28)

   Your definition must use mapM with the state-monad.

8. Define and test a function reciprocals that takes a list of numbers as input and returns the list of the reciprocals of the numbers. But if any of the numbers is 0, then return the symbol error immediately.

   > (reciprocals '(3 20 5))

   '(1/3 1/20 1/5)

   > (reciprocals '(3 2 0 5))

   'error

   > (reciprocals '(3 2 0 five))

   'error

   The last line above shows that, as soon as 0 is encountered, the rest of the list is not processed at all, so the fact that five is not a number does not matter.

   Your definition must use mapM with the cont-monad.

Monadic traversal

9. Define and test a function

   ; leavesM : [Monad M] [Int -> [M α]] Tree -> [M α]

   As the type signature above shows, your function leavesM should take three arguments: a monad, a function f from numbers to computations, and a Tree. What leavesM should return is a computation that invokes (f x) for each leaf x of the Tree (from left to right). The result of the computation should just be the last result of (f x).

   > (leavesM identity-monad

   (lambda (x) x)

   '(3 (20 5)))

   5

   > (leavesM writer-monad

   (lambda (x) `(writer ,(~a x) ,x))

   '(3 (20 5)))

   '(writer "3205" 5)

10. Define and test a function decimal that takes a Tree as input, treats its leaves as digits, and combines them into a decimal number.

    > (decimal '(3 (2 5)))

    325

    > (decimal '((3 1) 1))

    311

    Your definition must use leavesM with the state-monad.

    Hint: first make a function that returns the sum of the digits.

11. Define and test a function leaf-stream that takes a Tree as input and converts it to a Stream of its leaves from left to right.

    > (define s3 (leaf-stream '((3 1) 1)))

    > s3

    '(3 . #<procedure:...>)

    > (define s4 ((cdr s3)))

    > s4

    '(1 . #<procedure:...>)

    > (define s5 ((cdr s4)))

    > s5

    '(1 . #<procedure:...>)

    > ((cdr s5))

    '()

    Your definition must use leavesM with the cont-monad.
    Using your function, we can compare the fringes of two Trees (i.e., check if they have the same sequence of leaves while ignoring the tree structure) without unnecessary traversal:

    > (stream=? (leaf-stream '((3 1) 1)) (leaf-stream '(3 (1 1))))

    #t

    > (stream=? (leaf-stream '((3 1) 1)) (leaf-stream '(3 (20 five))))

    #f

    Hint: Review the generate function in the file 03-05_control.rkt in the lecture notes.

Brainteaser

12. Finish the definition of prob-bind below, to define the probability monad.

    (define prob-unit (lambda (x) `((,x 1))))

    (define prob-bind ...)

    (define prob-monad `(,prob-unit ,prob-bind))

    Hint: Define helper functions to add two distributions and to multiply a distribution by a factor. To coalesce duplicate Values, it’s also useful to have a helper function that adds a given Value and Number to a given Dist.

13. Following the example of list-init-env in valueM.rkt, define an initial environment prob-init-env so that flip in our little language is a function that takes a number p and returns #t with probability p and #f with probability 1−p.

    > (valueM prob-monad

    '((+ (if (flip 1/3) 1 0)) (if (flip 1/4) 1 0))

    prob-init-env)

    ((0 1/2) (1 5/12) (2 1/12))