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