Some Notes And Some Code

Lists are Monads too

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

Breadth-first labeling

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