S04
Exercise 2
Using the definitions
foldr k z xs = go xs
where go [] = z
go (y:ys) = y k go ys
and
foldl f z xs = lgo z xs
where lgo z [] = z
lgo z (x:xs) = lgo (f z x) xs
The expression foldr (-) 0 [1,2,3] can be evaluated as
foldr (-) 0 [1,2,3]
= go [1,2,3]
= 1 - go [2,3]
= 1 - (2 - go [3])
= 1 - (2 - (3 - go []))
= 1 - (2 - (3 - 0))
= 2
and the expression foldl (-) 0 [1,2,3] as
foldl (-) 0 [1,2,3]
= lgo 0 [1,2,3]
= lgo (0 - 1) [2,3]
= lgo ((0 - 1) - 2) [3]
= lgo (((0 - 1) - 2) - 3) []
= ((0 - 1) - 2) - 3
= -6
Exercises 4 and 5
See Grep.