Chapter 6: Recursive Functions

6.1 Basic Concepts

fac1 :: Int -> Int
fac1 n = product [1..n]

fac1 5

120

fac :: Int -> Int
fac 0 = 1
fac n = n * fac (n-1)

fac 5

120

fac 5 = 5 * fac 4 = 5 * 4 * fac 3 = 5 * 4 * 3 * fac 2 = 5 * 4 * 3 * 2 * fac 1 = 5 * 4 * 3 * 2 * 1 * fac 0 = 5 * 4 * 3 * 2 * 1 * 1 = 120

(#) :: Int -> Int -> Int
m # 0 = 0
m # n = m + (m # (n - 1))

4 # 3
(#) 4 3
4 * 3
(*) 4 3

12

12

12

12

4 # 3 = 4 + (4 # 2) = 4 + (4 + (4 # 1)) = 4 + (4 + (4 + (4 # 0))) = 4 + (4 + (4 + 0)) = 12

6.2 Recursion on Lists

product1 :: Num a => [a] -> a
product1 [] = 1
product1 (n:ns) = n * product1 ns

Use foldr

Found:

product1 [] = 1 product1 (n : ns) = n * product1 ns

Why Not:

product1 ns = foldr (*) 1 ns

product1 [2,4,6]

48

length1 :: [a] -> Int
length1 [] = 0
length1 (_:xs) = 1 + length1 xs

length1 [1,2,3]

3

reverse1 :: [a] -> [a]
reverse1 [] = []
reverse1 (x:xs) = reverse xs ++ [x]

reverse1 [1,2,3]

[3,2,1]

reverse1 [1,2,3] = reverse1 [2,3] ++ [1] = (reverse1 [3] ++ [2]) ++ [1] = ((reverse1 [] ++ [3]) ++ [2]) ++ [1] = (([] ++ [3]) ++ [2]) ++ [1] = ([3] ++ [2]) ++ [1] = [3,2] ++ [1] = [3,2,1]

(##) :: [a] -> [a] -> [a]
[]     ## ys = ys
(x:xs) ## ys = x : (xs ## ys)

[1,2,3] ## [4,5,6]
[1,2,3] ++ [4,5,6]

[1,2,3,4,5,6]

[1,2,3,4,5,6]

[1,2,3] ## [4,5,6] = 1 : ([2,3] ## [4,5,6]) = 1 : (2 : ([3] ## [4,5,6])) = 1 : (2 : (3 : ([] ## [4,5,6]))) = 1 : (2 : (3 : [4,5,6])) = [1,2,3,4,5,6]

insertion sort

insert :: Ord a => a -> [a] -> [a]
insert x []     = [x]
insert x (y:ys)
  | x <= y    = x : y : ys
  | otherwise = y : insert x ys

insert 3 [1,2,4,5]

[1,2,3,4,5]

insert 3 [1,2,4,5] = 1 : insert 3 [2,4,5] = 1 : 2 : insert 3 [4,5] = 1 : 2 : [3,4,5] = [1,2,3,4,5]

isort :: Ord a => [a] -> [a]
isort []       = []
isort (x : xs) = insert x (isort xs)

Use foldr

Found:

isort [] = [] isort (x : xs) = insert x (isort xs)

Why Not:

isort xs = foldr insert [] xs

isort [4,3,6,5,9]
isort ["john","alice","jim"]

[3,4,5,6,9]

["alice","jim","john"]

6.3 Multiple arguments

zip :: [a] -> [b] -> [(a,b)]
zip []     _      = []
zip _      []     = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

zip ['a','b','c'] [1,2,3,4]

[('a',1),('b',2),('c',3)]

zip ['a','b','c'] [1,2,3,4] = ('a',1) : zip ['b','c'] [2,3,4] = ('a',1) : ('b',2) : zip ['c'] [3,4] = ('a',1) : ('b',2) : ('c',3) : zip [] [4] = ('a',1) : ('b',2) : ('c',3) : [] = [('a',1),('b',2),('c',3)]

drop :: Int -> [a] -> [a]
drop 0 xs     = xs
drop _ []     = []
drop n (_:xs) = drop (n-1) xs

drop 3 [1,2,3,4,5,6]

[4,5,6]

6.4 Multiple recursion

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

fib 4

3

qsort []     = []
qsort (x:xs) = qsort ys ++ [x] ++ qsort zs
           where
              ys = [a | a <- xs, a <= x]
              zs = [b | b <- xs, b > x]

qsort [4,3,6,5,9]

[3,4,5,6,9]

6.5 Mutual recursion

even :: Int -> Bool
even 0 = True
even n = odd (n-1)

odd :: Int -> Bool
odd 0 = False
odd n = even (n-1)

even 8
even 13
odd 7
odd 20

True

False

True

False

even 4 = odd 3 = even 2 = odd 1 = even 0 = True

evens :: [a] -> [a]
evens []     = []
evens (x:xs) = x : odds xs

odds :: [a] -> [a]
odds []     = []
odds (_:xs) = evens xs

evens "abcde"

"ace"

evens "abcde" = 'a' : odds "bcde" = 'a' : evens "cde" = 'a' : 'c' : odds "de" = 'a' : 'c' : evens "e" = 'a' : 'c' : 'e' : odds "" = 'a' : 'c' : 'c' : [] = "ace"

6.6 Advice on recursion

Example 1: product of numbers in a list

STEP 1: Define the type

product :: [Int] -> Int

STEP 2: Enumerate the cases

product [] = 
product (n:ns) =

STEP 3: Define the simple cases (base case)

product [] = 1

STEP 4: Define the other cases (recursive cases)

product (n:ns) = n * product ns

STEP 5: Generalize and simplify

product :: Num a => [a] -> a
product = foldr (*) 1

Example 2: drop n elements from front of a list

STEP 1: Define the type

drop :: Int -> [a] -> a

STEP 2: Enumerate the cases

drop 0 [] = 
drop 0 (x:xs) =
drop n [] = 
drop n (x:xs) =

STEP 3: Define the simple cases (base case)

drop 0 [] = []
drop 0 (x:xs) = x:xs
drop n [] = []
drop n (x:xs) =

STEP 4: Define the other cases (recutsive cases)

drop 0 [] = []
drop 0 (x:xs) = x:xs
drop n [] = []
drop n (x:xs) = drop (n-1) xs

STEP 5: Generalize and simplify

drop :: Integral b => b -> [a] -> a
drop 0 xs = xs
drop n [] = []
drop n (x:xs) = drop (n-1) xs

We can replace n by _ in 3rd equation

drop :: Integral b => b -> [a] -> a
drop 0 xs = xs
drop _ [] = []
drop n (x:xs) = drop (n-1) xs

Example 3: init list returns all but last item in a non-empty list

STEP 1: Define the type

init :: [a] -> [a]

STEP 2: Enumerate the cases

init (x:xs) =

STEP 3: Define the simple cases (base case is 1-element list)

init (x:xs) 
  | null xs   = []
  | otherwise =

STEP 4: Define the other cases (recursive cases)

init (x:xs) 
  | null xs   = []
  | otherwise = x : init xs

STEP 5: Generalize and simplify (nothing to generalize here; but can be simplified)

init :: [a] -> [a]
init [_]    = []
init (x:xs) = x : init xs

Problem Set

-- 7. merge
merge :: Ord a => [a] -> [a] -> [a]
merge [] xs         = xs
merge xs []         = xs
merge (x:xs) (y:ys) 
  | x < y     = x : merge xs (y:ys)
  | otherwise = y : merge (x:xs) ys

merge [2,5,6] [1,3,4]

[1,2,3,4,5,6]

-- 8. mergesort
halve :: [a] -> ([a],[a])
halve []         = ([],[])
halve [x]        = ([x],[])
halve (x1:x2:xs) = (x1:h1s,x2:h2s) where (h1s,h2s)= halve xs

msort :: Ord a => [a] -> [a]
msort []   = []
msort [x]  = [x]
msort xs = merge (msort h1s) (msort h2s) where (h1s,h2s) = halve xs

halve [1,2,3,4,5,6]
msort [20,10,30,40,5,16,19,22]