Exercise 3 – Recursive Functions
1 Example
“subsequences” in Exam 1.
2 Exercises
Hao Tian March 2019
1. Find the range of a list. For example range [1,2,3,4,5,6,7] = 6 (max- min).
Answer:
range :: [Int]− > Int
range [ ] = 0
range [x] = 0
range (x : xs) = helper x x xs where
helper :: Int− > Int− > [Int]− > Int helper a b [ ] = b − a
helper a b (x : xs)
|x < a = helper x b xs
|x > b = helper a x xs |otherwise = helper a b xs
2. Implement the function log2, which computes the integer log (base 2) of its argument. That is, log2 computes the exponent of the largest power of 2 which is less than or equal to its argument. For example, log2 16=4,log2 11=3,andlog2 1=0.
Answer:
log2 :: Int− > Int log2 x
|x < 0 = 0
|otherwise = helper 2 0 where
helper :: Int− > Int− > Int helper a b
|a > x = b
|otherwise = helper (2 ∗ a) (b + 1)
1