Lecture 9-2

COMP105 Lectures 2020-10-29

Recursion with Multiple Lists

Sometimes we want to use recursion on more than one list at a time. The following example adds the elements of two lists together:

add_lists _ [] = []
add_lists [] _ = []
addlists (x:xs) (y:ys) = x + y : addlists xs ys

• Base cases stop when either of the lists is empty.
• Recursive rule pulls an element form both lists.

Another method to implement this, provided that you don’t want to accept lists which don’t have equal length is like the following:

f [] [] = []
f [] _ = error "Second list is longer"
f _ [] = error "First list is longer"
f (x:xs) (y:ys) = x + y : f xs ys

• This will give an explicit error if they aren’t matching length.

Splitting a List in Two

Other functions can take a list and return a pair of lists:

gt_10 [] = ([],[])
gt_10 (x:xs)
	| x > 10	= (x:gt, lt)
	| otherwise	= (gt, x:lt)
	where (gt, lt) = gt_10 xs

This will split a list into two lists containing values that are bigger and smaller than 10.

• The base case sets up the tuple.
• The recursive rule modifies one of the two lists.

zip

zip takes two lists and returns a list of pairs

zip' [] _ = []
zip' _ [] = []
zip' (x:xs) (y:ys) = (x, y) : zip' xs ys

Exercises

1.  multiplyLists _ [] = []
    multiplyLists [] _ = []
    multiplyLists (x:xs) (y:ys) = x * y : multiplyLists xs ys
   

2.  zip3' [] _ _ = []
    zip3' _ [] _ = []
    zip3' _ _ [] = []
    zip3' (x:xs) (y:ys) (z:zs) = (x,y,z) : zip3' xs ys zs