S04

Contents

Synopsis

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.

Exercise 3

isSorted :: Ord a => BTree a -> BoolSource

Exercise 6

showBTree :: Show a => BTree a -> StringSource