- Assignment 7 solutions
- “Lambda” notation
- Pseudorandom numbers
- Threading state through pure functions

“Lambda” is a notation for an *anonymous* function. The name comes from the Greek lowercase letter λ, and the symbol we use for it in Haskell is the backslash: `\`

.

Normally when you define a function, you put its name and then its arguments, and then equals, and body.

And then you can use that function in various ways:

```
ghci> map square [3..9]
[9,16,25,36,49,64,81]
ghci> square 15
225
```

Instead, of naming that simple function separately, you can specify it “inline”, without any name, by using the syntax `\x -> x*x`

. The argument(s) are named between the backslash and the arrow, and the body follows the arrow. So here are the previous examples but using a lambda instead:

```
ghci> map (\x -> x*x) [3..9]
[9,16,25,36,49,64,81]
ghci> (\x -> x*x) 15
225
```

In each use, the parentheses around the lambda expression are required. They tell Haskell how far the body of the function extends. If you instead tried to type

`ghci> \x -> x*x 15`

it would generate an error, because it tries to include the `15`

into the body of the function, so the body is an expression like this:

`x * (x 15)`

Which means we’re trying to use `x`

both as a number (in the multiplication) and as a function (in applying it to the argument 15). That conflict is the source of the error message we see.

You can still assign a lambda to a name if you want to, like this:

and that’s equivalent to the usual definition of `square`

previously. We just moved the `x`

argument to the right side of the equals by putting it behind a lambda.

Arguments can migrate in lots of ways – all these definitions would be equivalent (assuming the missing bodies are the same).

```
quadratic a b c = ......
quadratic = \a b c -> ......
quadratic = \a -> \b -> \c -> ......
quadratic a = \b c -> ......
quadratic a = \b -> \c -> ......
quadratic a b = \c -> ......
```

We want random numbers, but a normal random() function like in Python would not be **pure** because it returns different results each time it is called with the same arguments.

```
Python 3.6.6 (default, Jun 27 2018, 05:47:41)
>>> from random import random
>>> random()
0.5123024048063498
>>> random()
0.30976968273997585
>>> random()
0.3808983753319447
>>> random()
0.70678293848969
```

The strategy for making a **pure** version of `random`

is to expose the “state” of the random number generator. Here is a definition of an LCG – Linear Congruential (pseudo-random) Generator.

The constants in here are chosen carefully to have particular effects. The *multiplier* `16807`

ensures that the results are fairly evenly distributed, and the modulus `0x7FFFFFFF`

clamps the range to the range of 31-bit integers (same as *non-negative* 32-bit integers).

But this is just a formula, and if the seed is known then the results are predictable. Here’s how to get a sequence of random numbers:

```
ghci> rand (Seed 294992)
(662963250,Seed {unSeed = 662963250})
ghci> rand (Seed 662963250)
(1278182114,Seed {unSeed = 1278182114})
ghci> rand (Seed 1278182114)
(1127869057,Seed {unSeed = 1127869057})
```

The initial seed value, `294992`

, was chosen arbitrarily by bashing on the number row of my keyboard. From there, we take the seed returned by the previous call to `rand`

and use it in the next call. This generates the sequence of three pseudo-random 31-bit numbers, which here are `662963250`

, then `1278182114`

, then `1127869057`

.

But whenever you give the same seed, you get the same number. Therefore the function is still **pure.**

```
ghci> rand (Seed 662963250)
(1278182114,Seed {unSeed = 1278182114})
```

The type of rand, `Seed -> (Int, Seed)`

is a common pattern that we could call a **generator.** A more generic form of it could be represented as

It represents a function that takes an *incoming* state of type `s`

, produces a *result* of type `a`

, along with an *outgoing* state, also of type `s`

. A common pattern when using a generator of this shape is to **thread** the state through multiple calls to the generator.

For example, suppose we want to write one function to generate three random numbers. That means calling `rand`

three times and assembling the results into a list or tuple:

```
threeRandoms :: Seed -> ([Int], Seed)
threeRandoms s0 = ([r1,r2,r3], s3)
where
(r1, s1) = rand s0
(r2, s2) = rand s1
(r3, s3) = rand s2
```

Notice how this takes an `s0`

, threads it into one `rand`

which produces `s1`

. Then it takes `s1`

and threads it into the next `rand`

, and so on. If any parameter in that sequence is out of place (if `s1`

is duplicated somewhere, for example), then we’ll get a duplication of numbers. Each seed should be used only once.

Here’s a slightly more sophisticated version that can generate a list of random numbers of a specified size:

```
randomList :: Int -> Seed -> ([Int], Seed)
randomList 0 s = ([], s)
randomList n s0 = (r:rs, s2)
where
(r, s1) = rand s0
(rs, s2) = randomList (n-1) s1
```

It still exhibits the threading of `s0`

to `s1`

to `s2`

.

Let’s play with a different function with the same shape, `s -> (a,s)`

. Instead of numbers, this will represent a **counter** that can be incremented.

```
ghci> increment (Counter 5)
(5,Counter 6)
ghci> increment (Counter 6)
(6,Counter 7)
```

Here is the analogue of `threeRandoms`

, it has exactly the same state-passing structure.

```
threeIncrements :: Counter -> ([Integer], Counter)
threeIncrements s0 = ([r1,r2,r3], s3)
where
(r1, s1) = increment s0
(r2, s2) = increment s1
(r3, s3) = increment s2
```

```
ghci> threeIncrements (Counter 5)
([5,6,7],Counter 8)
ghci> threeIncrements (Counter 10)
([10,11,12],Counter 13)
```

This may seem kind of pointless, but it allows us to explore an interesting pattern.

Most operations we explored on trees – `flipTree`

, `fmap`

, `height`

– are **compositional.** That means that the recursion down the left and right side are *independent* of each other.

But with some operations and transformations, the left and right are *not* independent. They may require **threading state** through each branch in the traversal. (After processing the left subtree we need to thread the state into the right subtree.)

One such operation is value-numbering the tree. That means using a counter as the state, and pairing branch values with unique, consecutive integers. Here’s the tree data type:

Some example trees:

```
t1 :: Tree Char
t1 = Branch 'B' (Branch 'F' Leaf Leaf)
(Branch 'C'
(Branch 'D' Leaf Leaf)
(Branch 'E' Leaf Leaf))
```

```
t2 :: Tree Char
t2 = Branch 'B' (Branch 'F'
(Branch 'K' Leaf Leaf)
(Branch 'Z' Leaf (Branch 'G' Leaf Leaf)))
(Branch 'C'
(Branch 'D' Leaf Leaf)
(Branch 'E' Leaf Leaf))
```

And here is where we use the counter increment. Notice the same `s0`

, `s1`

, `s2`

, `s3`

pattern.

```
numberTree :: Tree a -> Counter -> (Tree (Integer,a), Counter)
numberTree Leaf s = (Leaf, s)
numberTree (Branch v left right) s0 =
(Branch (i,v) newL newR, s3)
where
(i, s1) = increment s0
(newL, s2) = numberTree left s1
(newR, s3) = numberTree right s2
```

```
ghci> numberTree t1 (Counter 1)
(Branch (1,'B')
(Branch (2,'F') Leaf Leaf)
(Branch (3,'C')
(Branch (4,'D') Leaf Leaf)
(Branch (5,'E') Leaf Leaf)),
Counter 6)
ghci> numberTree t1 (Counter 10)
(Branch (10,'B')
(Branch (11,'F') Leaf Leaf)
(Branch (12,'C')
(Branch (13,'D') Leaf Leaf)
(Branch (14,'E') Leaf Leaf)),
Counter 15)
ghci> numberTree t2 (Counter 1)
(Branch (1,'B')
(Branch (2,'F')
(Branch (3,'K') Leaf Leaf)
(Branch (4,'Z')
Leaf
(Branch (5,'G') Leaf Leaf)))
(Branch (6,'C')
(Branch (7,'D') Leaf Leaf)
(Branch (8,'E') Leaf Leaf)),
Counter 9)
```