Glueing functions together
- Having defined lists as follows
listof X ::= nil | cons X (listof X)
[] means nil
[1] means (cons 1 nil)
[1,2,3] means (cons 1 (cons 2 (cons 3 nil)))
- We can define the sum of all elements in a list of numbers
sum nil = 0
sum (cons num list) = num + sum list
Glueing functions together
- There are only two parts specific to computing a sum in
sum
sum nil = 0
sum (cons num list) = num + sum list
- We can build
sum by giving the specific parts to a general function
- This more general function is very useful
sum = reduce add 0
add x y = x + y
(reduce f x) nil = x
(reduce f x) (cons a l) = f a ((reduce f x) l)
Just how useful is reduce
product = reduce multiply 1
anytrue = reduce or false
alltrue = reduce and true
- We can better understand what
reduce does by example
cons 1 (cons 2 (cons 3 nil))
{- APPLY "reduce add 0" to line above -}
add 1 (add 2 (add 3 0))
cons 1 (cons 2 (cons 3 nil))
{- APPLY "reduce multiply 1" to line above -}
multiply 1 (multiply 2 (multiply 3 1))
Just how useful is reduce
- We can even use
reduce to append lists
append a b = reduce cons b a
append [1,2] [3,4]
reduce cons [3,4] [1,2]
(reduce cons [3,4]) (cons 1 (cons 2 nil))
cons 1 (cons 2 [3,4])
[1,2,3,4]
But wait, there's more
doubleall = reduce doubleandcons nil
where doubleandcons num list = cons (2*num) list
doubleandcons = fandcons double
where double n = 2 * n
fandcons f el list = cons (f el) list
fandcons f el = cons (f el) {- because ∀ x. f x = g x ⟶ f = g -}
(f . g) h = f (g h)
fandcons f = cons . f
doubleall = reduce (cons . double) nil
map f = reduce (cons . f) nil
doubleall = map double
Now, for trees…
- We can define ordered labeled trees as:
treeof X ::= node X (listof (treeof X))
node 1
(cons (node 2 nil)
(cons (node 3
(cons (node 4 nil) nil))
nil))
Reducing trees
- We define
redtree by analogy with reduce
- 3 parameters, substituting
node, cons and nil
redtree reduces trees, redtree' reduces list of subtrees
redtree f g a (node label subtrees) = f label (redtree’ f g a subtrees)
redtree’ f g a (cons subtree rest) = g (redtree f g a subtree) (redtree’ f g a rest)
redtree’ f g a nil = a
Example of using redtree
- We can define a function to get a list of all labels in a tree
labels = redtree cons append nil
node 1
(cons (node 2 nil)
(cons (node 3
(cons (node 4 nil) nil))
nil))
{- APPLY "redtree cons append nil" to line above -}
cons 1
(append (cons 2 nil)
(append (cons 3
(append (cons 4 nil) nil))
nil))
- By the way, of course we can map a function over a tree
maptree f = redtree (node . f) cons nil
Glueing programs together: composition
- Remember Unix pipelines?
cmd1 | cmd2
- Output of
cmd1 fed to input of cmd2
- Circular FIFO
- In FP, we write
cmd2 . cmd1
cmd1 ONLY runs enough to provide cmd2 with what it needs- No intermediate data stored
- This is called lazy evaluation
Elegant sqrt
- We use the Newton-Raphson algorithm
- Start with approx.
a0 and compute next approx. as follows:
a(n+1) = (a(n) + N/a(n)) / 2
- If the sequence converges to a certain "
a", then:
a = (a + N/a) / 2
2a = a + N/a
a = N/a
a*a = N
a = √N
This would normally be so ugly…
X = A0
Y = A0 + 2.*EPS
# THE VALUE OF Y DOES NOT MATTER SO LONG AS ABS(X-Y) > EPS
100 IF (ABS(X-Y).LE.EPS) GOTO 200
Y = X
X = (X + N/X) / 2.
GOTO 100
200 CONTINUE
- Making it better with FP: first step is
next
next N x = (x + N/x) / 2
A sequence of approximations appears!
next N x = (x + N/x) / 2
# abbreviating "next N" as "f", this is the sequence we want:
[a0, f a0, f (f a0), f (f (f a0)), ...
repeat f a = cons a (repeat f (f a))
repeat (next N) a0
Stopping before infinity
- In the previous slide we define an infinite seq. of approxs.
- But we can "stop" whenever the difference gets small enough
within eps (cons a (cons b rest)) = if abs (a - b) <= eps
then b
else within eps (cons b rest)
sqrt a0 eps N = within eps (repeat (next N) a0)
- Square-root finder has two "parts":
- Generate sequence of approximations
- Select element from sequence
- Let's re-use them for other goals
Numerical differentiation, FP-style
- A way to approximate a derivative
easydiff f x h = (f(x+h)-f x) / h
- Then we can get a sequence of approximations
- And stop when the difference is small enough
halve x = x/2
differentiate h0 f x = map (easydiff f x) (repeat halve h0)
diffAttempt1 h0 f x = within eps (differentiate h0 f x)
This naïve attempt converges slowly…
- Calculus helps with improving the sequence
- The reasoning behind this is easy, in the paper
- But essentially it gives a function
improve
elimerror n (cons a (cons b rest)) = cons ((b*(2**n)-a)/(2**n-1)) (elimerror n (cons b rest))
order (cons a (cons b (cons c rest))) = round (log2 ((a-c)/(b-c) - 1)) {- NO PROOF HERE -}
improve s = elimerror (order s) s
within eps (improve (differentiate h0 f x))
within eps (improve (improve (differentiate h0 f x)))
What the glue allowed us here…
- More understandable definitions
- Above all: re-usable ingredients
improve, within also useful for integration
An example from artificial intelligence
- Let's write a program capable of playing (deterministic) games
- Using the minimax strategy, with the alpha-beta opt,
- But in super elegant FP style
- First of all we need a function giving the possible moves
moves: position -> listof position
- With this we can calculate a game tree
Game trees
- Remember the trees we had from section 3
treeof X ::= node X (listof (treeof X))
- We can build a tree by repeated applications of a function
- By repeat application of
moves, we get a game tree
repeat f a = cons a (repeat f (f a))
reptree f a = node a (map (reptree f) (f a))
gametree p = reptree moves p
A first attempt at minimax
- We need a function to define how much approx. a position is worth
- Worth for the computer
- Approx. means without lookahead
static: position -> number
- Now we can express the core of minimax as two functions
- For computer: maximise true value
- For the opponent: minimise true value
maximise (node n sub) = max (map minimise sub)
minimise (node n sub) = min (map maximise sub)
A first attempt at minimax
- Little detail: base case for
maximise and minimise
- Leaves of the tree = no more moves to analyse
- Just use the "static" approximation at this point
maximise (node n nil) = n
minimise (node n nil) = n
- With this we can define a minimax algorithm
Making out minimax better
- Doesn't work with infinite game trees
- Even for finite ones (tic-tac-toe), it can take a looooong time
- Fortunately, we can prune a tree
prune 0 (node a x) = node a nil
prune n (node a x) = node a (map (prune (n-1)) x)
- Compare the optimized definition with the unoptimized one
- This modularity could NOT be achieved without lazy eval
evaluateSlow = maximise . maptree static . gametree
evaluateFast = maximise . maptree static . prune 5 . gametree
Last-step: alpha-beta
- Gist of it: when computing a max, we don't need to compute all minima
- Just involves a change from
maximise into maximise'
maximise’ (node n nil) = cons n nil
maximise’ (node n l) = map minimise l
= map (min . minimise’) l
= map min (map minimise’ l)
= mapmin (map minimise’ l)
where mapmin = map min
mapmin (cons nums rest) = cons (min nums) (omit (min nums) rest)
evaluate = max . maximise’ . maptree static . prune 8 . gametree