Home
• Education Page
• Schedule
• Literature
 - Errata
• Example Code
• Practical Exercises
• Q & A
• Regulations
• Marks
• Oude Tentamens

Miscellaneous

Center

Page

Web

Wiki

# Some Notes And Some Code

FP

```instance Monad [] where
la >== a2lb = [ b | a <- la, b <- a2lb a]
return a        = [a]
```

### Digestive Functors

Jasper van der jeugd is a Belgian student who has been very active developing various libraries. His blogs contain interesting libraries and examples, e.g. for digenstive functors, which provide yet another example of the Applicative interface.

### Lambda calculus

#### Booleans

```true  = \ t f -> t
false = \ t f -> f

if c t e = c t e
```

#### Pairs

```pair =  \ x y f -> f x y

fst   =  \ p -> p (\ x y -> x)
snd =  \ p -> p (\ x y -> y)
```

#### Maybe

```nothing =         \ n j -> n
just    = \ a ->  \ n j -> j a

case v of
Nothing -> <expr1>
Just a  -> <expr2>

becomes
v (<expr1>) (\ a -> <expr2>)
```

#### Natural numbers

```data Nat = Zero
| Succ Nat

zero =         \ z s -> z
succ = \ n -> \ z s -> s n
```

#### Lists

```data List a = Nil
| Cons a (List a)

nil =                  \ n c -> n
cons = \ a la -> \ n c -> c a la

case v of
Nil        -> <expr1>
Cons a  la -> <expr2>

becomes

v (<expr1>) (\ a la -> <expr2>)
```

#### Non-recursive lets

```let x = <e1> in <e2>

becomes

(\x . e2) e1
```

#### Recursion

Recusion is removed using the =fix=combinator, which itself can be written as a lambda-expression.
```fix = \ f -> (\x -> f(x x)) )(\x -> f (x x)

fix f = (\x -> f(x x)) )(\x -> f (x x) = f ((\x -> f(x x)) )(\x -> f (x x)) = f (fix f)
```

#### Replacing all lambda expressions by S, K and I

```S = \ f g x -> (f x) (g x)
K = \ y   x -> y
I = \     x -> x
```

Even these can be replaced by using only a single combinator: http://www.staff.science.uu.nl/~fokke101/article/combinat/index.html

```X = \f.f S (\xyz.x)

K = X X
S = X K

Rewriting gives:

K y x
(\f.fS(\xyz.x)) X y x
X S (\xyz.x) y x
S S (\xyz.x) (\xyz.x) y x
S (\xyz.x) ((\xyz.x) (\xyz.x)) y x
(\ a b . y) ((\xyz.x) (\xyz.x)) x
y

X K f g x
K S (\xyx.x) f g x
S f g x
```

### Lazy evaluation

#### Repmin

```data Tree a = Leaf a
| Node (Tree a) (Tree a)

repmin t = let repmin' (Leaf v) m = (v, Leaf m)
repmin' (Node l r) m = let (ml, rl) = repmin' l m
(mr, rr) = repmin' r m
in (lm `min` rm, Bin rl rr)
(m,r) = repmin' t m -- !! we feed part of the result to the function call!
in r
```

```data Tree a = Leaf
| Node (Tree a) a (Tree a)
deriving Show

-- the function bfl replaces the a's in a tree by consecutive values from the list [b] in a breadth-first way
bfl :: Tree a -> [b] -> Tree b

bfl t l = let bf Leaf lss = (Leaf, lss)
bf (Node lt _ rt) ((l:ls):lls) =
let (lr, ills) = bf lt lls
(rr, rlls) = bf rt ills
in (Node lr l rr, ls:rlls)
(result, nlevels) = bf t (l:nlevels)
in result

t :: Tree Int
t = Node (Node (Node Leaf 1 Leaf) 1 (Node Leaf 1 (Node Leaf 1  (Node Leaf 1 Leaf)))) 1 Leaf

{-
*Main> bfl t [1..]
Node (Node (Node Leaf 3 Leaf) 2 (Node Leaf 4 (Node Leaf 5 (Node Leaf 6 Leaf)))) 1 Leaf
-}

```

-- DoaitseSwierstra - 31 Oct 2011