Lecture 8-2
List Recursion Examples
In this section we will be re-implementing the built in functions for operating on lists.
take
take' 0 list = []
take' n [] = []
take' n (x:xs) = x : take' (n - 1) xs
With the two base cases the program will end in one of two ways:
- We take as many items as we asked for.
- We run out of elements to take.
drop
drop' 0 list = list
drop' n [] = [] -- could also be an error
drop' n (x:xs) = drop' (n - 1) xs
elem
elem' e [] = False
elem' e (x:xs)
| e == x = True
| otherwise = elem' e xs
This will cycle through every item in the list and will stop and say True if it is found. If it isn’t found then it will return False.
This also implements pattern matching and guards in one function.
maximum
Maximum will say which is the largest element in a list.
maximum' [] = error "Called with empty list."
-- This prints an error with this label
maximum' [x] = x
-- This pattern matches against a list of length 1.
maximum' (x:xs) =
let
max_tail = maximum' xs
in
if (x > max_tail) then x else max_tail
This checks from the back of the list and keeps the largest element in the list as x
reverse
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
-- ++ puts an element onto the tail of a list
Consuming More Than One Element
add_adjacent
add_adjacent [] = []
add_adjacent [x] = error "Odd number of elements"
add_adjacent (x:y:xs) = x + y : add_adjacent xs
> add_adjacent [1,2,3,4,5,6]
> [3,7,11]
add_next
add_next [] = error "Not enough elements"
add_next [_] = error "Not enough elements"
add_next [x,y] = [x+y]
add_next (x:y:xs) = x + y : add_next (y:xs)
Exercises
-
containsThree [] = False containsThree (x:xs) | x == 3 = True | otherwise = containsThree xs -
sumEvenIdx [] = 0 sumEvenIdx [x] = x -- Required to catch 1 and odd element lists. sumEvenIdx (x:_:xs) = x + sumEvenIdx xs