Haskell: The Craft of Functional Programming Simon Thompson (c) Addison-Wesley, 1999. Chapter 19 Time and space behaviour ^^^^^^^^^^^^^^^^^^^^^^^^ > module Chapter19 where > import Prelude hiding (map) Various functions whose complexity is discussed. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Naive Fibonacci function > fib 0 = 0 > fib 1 = 1 > fib m = fib (m-2) + fib (m-1) Naive factorial function > fac :: Int -> Int > fac 0 = 1 > fac n = n * fac (n-1) Insertion sort > iSort :: Ord a => [a] -> [a] > iSort [] = [] > iSort (x:xs) = ins x (iSort xs) > ins :: Ord a => a -> [a] -> [a] > ins x [] = [x] > ins x (y:ys) > | (x<=y) = x:y:ys > | otherwise = y:ins x ys Quicksort > qSort :: Ord a => [a] -> [a] > qSort [] = [] > qSort (x:xs) = qSort [z|z<-xs,z<=x] ++ [x] ++ qSort [z|z<-xs,z>x] Two reverse functions > rev1 [] = [] > rev1 (x:xs) = rev1 xs ++ [x] > rev2 = shunt [] > shunt xs [] = xs > shunt xs (y:ys) = shunt (y:xs) ys Two multiplication functions > mult n 0 = 0 > mult n m = mult n (m-1) + n > russ n 0 = 0 > russ n m > | (m `mod` 2 == 0) = russ (n+n) (m `div` 2) > | otherwise = russ (n+n) (m `div` 2) + n The merge sort function > mSort xs > | (len < 2) = xs > | otherwise = mer (mSort (take m xs)) (mSort (drop m xs)) > where > len = length xs > m = len `div` 2 > mer (x:xs) (y:ys) > | (x<=y) = x : mer xs (y:ys) > | otherwise = y : mer (x:xs) ys > mer (x:xs) [] = (x:xs) > mer [] ys = ys Implementations of sets ^^^^^^^^^^^^^^^^^^^^^^^ Sets implemented as _unordered_ lists. type Set a = [a] empty = [] memSet = member inter xs ys = filter (member xs) ys union = (++) subSet xs ys = and (map (member ys) xs) eqSet xs ys = subSet xs ys && subSet ys xs makeSet = id mapSet = map Space behaviour ^^^^^^^^^^^^^^^ Lazy evaluation ^^^^^^^^^^^^^^^ List examples > exam1 n = [1 .. n] ++ [1 .. n] > exam2 n = list ++ list > where > list=[1 .. n] > exam3 n = [1 .. n] ++ [last [1 .. n]] > exam4 n = list ++ [last list] > where > list=[1 .. n] Saving space? ^^^^^^^^^^^^^ A new version of factorial > newFac :: Int -> Int > newFac n = aFac n 1 > aFac 0 p = p > aFac n p = aFac (n-1) (p*n) This can be modified thus: aFac n p | p==p = aFac (n-1) (p*n) Miscellaneous functions > sumSquares :: Integer -> Integer > sumSquares n = sumList (map sq [1 .. n]) > sumList = foldr (+) 0 > sq n = n*n Folding revisited ^^^^^^^^^^^^^^^^^ Map defined using foldr > map f = foldr ((:).f) [] Factorial using foldr > facFold n = foldr (*) 1 [1 .. n] Examples > foldEx1 n = foldr (&&) True (map (==2) [2 .. n]) Avoiding re-computation: memoization ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The Fibonacci numbers A naive algorithm is given earlier in this script. An algorithm which returns a pair of consecutive Fibonacci numbers. > fibP :: Int -> (Int,Int) > fibP 0 = (0,1) > fibP n = (y,x+y) > where > (x,y) = fibP (n-1) The list of Fibonacci values, defined directly. > fibs ::[Int] > fibs = 0 : 1 : zipWith (+) fibs (tail fibs) Dynamic programming: maximal common subsequence ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The naive algorithm ... > mLen :: Eq a => [a] -> [a] -> Int > mLen xs [] = 0 > mLen [] ys = 0 > mLen (x:xs) (y:ys) > | x==y = 1 + mLen xs ys > | otherwise = max (mLen xs (y:ys)) (mLen (x:xs) ys) ... translated to talk about sub-components of lists, described by their endpoints ... > maxLen :: Eq a => [a] -> [a] -> Int -> Int -> Int > maxLen xs ys 0 j = 0 > maxLen xs ys i 0 = 0 > maxLen xs ys i j > | xs!!(i-1) == ys!!(j-1) = (maxLen xs ys (i-1) (j-1)) + 1 > | otherwise = max (maxLen xs ys i (j-1)) > (maxLen xs ys (i-1) j) ... and then transliterated into a memoised version. > maxTab :: Eq a => [a] -> [a] -> [[Int]] > maxTab xs ys > = result > where > result = [0,0 .. ] : zipWith f [0 .. ] result > f i prev > = ans > where > ans = 0 : zipWith g [0 .. ] ans > g j v > | xs!!i == ys!!j = prev!!j + 1 > | otherwise = max v (prev!!(j+1))