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))