11 Jan

This time, no new examples will be provided, only additional explanations and tips for solving the exercises in the sheet.

Audit

Function that also logs something, aside from returning its value.

1 bind

You can think of bind f as an “upgraded” f, and just write what it does with its argument: (prevRes, prevLog).

Some examples of logging functions:

add5 :: Float -> (Float, String)

divideBy2 :: Float -> Audit Float  -- same as (Float, String)
divideBy2 x = (x / 2, "divideBy2 was called")

Composing them using the bind function:

divideThenAdd :: Float -> (Float, String)
15  -- 20/2=10 +5=15

Using the composition operator #:

divideThenAdd :: Float -> (Float, String)

2 unit

Remember that lift f is a function, so it may be easier to understand if it is written like this:

lift :: (a -> b) -> (a -> Audit b)
(lift f) x = unit (f x)

Or even:

(lift f) x = (f(x), "")

Which explains what the lifted f does to its argument, f: it creates a pair of the normal result f(x) and logs nothing ("").

Nondet

Function that returns multiple values of the same type – like a list.

4 bind

Again, remember to treat bind f as a function. It may also be useful to remember what the built-in function concat does.

Some example non-deterministic functions:

oppositeToo :: Int -> [Int]
oppositeToo x = [x, -x]

plus1n2n3 :: Int -> Nondet Int  -- same as [Int]
plus1n2n3 x = [x + 1, x + 2, x + 3]
> oppositeToo 5
[5, -5]

> plus1n2n3 10
[11, 12, 13]

Composing them:

plusOpposites :: Int -> [Int]
plusOpposites = oppositeToo # plus1n2n3
-- or explicitly with the `bind` function: (bind oppositeToo) . plus1n2n3
> plusOpposites 10
[11,-11, 12,-12, 13,-13]

5 unit

Just like before, keep in mind that lift f should be treated like a function:

lift :: (a -> b) -> (a -> Nondet b)
(lift f) x = [f(x)]

Randomized

Function that uses randomization in its body, which requires a seed (for generating random numbers).

To avoid getting tangled in notation, it may be useful to remember that StdGen can be thought of as a Seed. Also MyRandom a describes a function that returns an element of type a and employs an element of randomness in its body (also returning a new Seed).

type Seed = StdGen  -- alias
type RandFunc a = Seed -> (a,Seed)  -- instead of MyRandom a

If you try to evaluate uniformNat on, say 5, instead of getting a random integer between 0 and 5 you will get an error:

> uniformNat 5
error:
"No instance for (Show (RandFunc Int))"  -- says it can't print a function
"Maybe you haven't applied a function to enough arguments?"  -- good question

Let’s see what uniformNat 5 actually is:

> :type (uniformNat 5)
(uniformNat 5) :: RandFunc Int

It is a function that returns an integer (and uses some kind of randomness inside)! Of course we can’t print it.

In order to get a result, we also have to pass a Seed to it. Luckily we have a seed defined for us - zeroSeed:

> (uniformNat 5) zeroSeed
(1, 13463877652103410263)  -- the generated integer is 1, the new seed is the long number