In this chapter were introduced the recursion, basic mechanism to loop in Haskell.
Exponentiation
Define the exponentiation operator ↑ for non-negative integers using the same pattern of recursion as the multiplication operator
∗, and show how 2 ↑ 3 is evaluated using your definition.
(^) :: Int -> Int -> Int _ ^ 0 = 1 x ^ n = x * (x ^ (n-1))
2 ^ 3 = 2 * (2 ^ 2)
= 2 * 2 * (2 ^ 1)
= 2 * 2 * 2 * (2 ^ 0)
= 2 * 2 * 2 * 1
= 8
evaluated
Using the definitions given in this chapter, show how length [1, 2, 3], drop 3 [1, 2, 3, 4, 5], and init [1, 2, 3] are evaluated.
length
Given the definition:
length :: [a] -> Int length [] = 0 length (_:xs) = 1 + length xs
length [1,2,3] = 1 + length [2,3]
= 1 + 1 + length [3]
= 1 + 1 + 1 + length []
= 1 + 1 + 1 + 0
= 3
drop
Given the definition:
drop :: Int -> [a] -> [a] drop 0 ys = ys drop _ [] = [] drop n (_:ys) = drop (n-1) ys
drop 3 [1,2,3,4,5] = drop 2 [2,3,4,5]
= drop 1 [3,4,5]
= drop 0 [4,5]
= [4,5]
init
Given the definition:
init :: [a] -> [a] init [_] = [] init (x:xs) = x:(init xs)
init [1,2,3] = 1:(init [2,3])
= 1:2:(init [3])
= 1:2:[]
= [1,2]
functions
Without looking at the definitions from the standard prelude, define the following library functions using recursion: – and – concat – replicate – (!!) – elem
Note: most of these functions are in fact defined in the prelude using other library functions, rather than using explicit recursion.
and
– Decide if all logical values in a list are True:
and :: [Bool] → Bool
and :: [Bool] -> Bool and [] = True and (x:xs) = x && (and xs)
Example:
*Ch6> and [True, True, True] True *Ch6> and [True, False, True] False
concat
– Concatenate a list of lists:
concat :: [[a] ] → [a]
concat :: [[a]] -> [a] concat [xs] = xs concat (xs:xxs) = xs ++ (concat xxs)
Example:
*Ch6> concat [[1..10], [2,4], [20..25]] [1,2,3,4,5,6,7,8,9,10,2,4,20,21,22,23,24,25]
replicate
– Produce a list with n identical elements:
replicate :: Int → a → [a]
replicate :: Int -> a -> [a] replicate 0 _ = [] replicate n x = x:(replicate (n-1) x)
Example:
*Ch6> replicate 10 'a' "aaaaaaaaaa" *Ch6> replicate 5 9 [9,9,9,9,9]
(!!)
– Select the nth element of a list:
(!!) :: [a] → Int → a
(!!) :: [a] -> Int -> a (x:_) !! 0 = x (_:xs) !! n = xs !! (n-1)
Example:
*Ch6> [1,2,3] !! 2 3 *Ch6> [1,2,3] !! 0 1
elem
– Decide if a value is an element of a list:
elem :: Eq a ⇒ a → [a] → Bool
elem :: Eq a => a -> [a] -> Bool elem _ [] = False elem x (y:ys) | x == y = True | otherwise = elem x ys
Example:
*Ch6> elem 1 [10,20,30] False *Ch6> elem 10 [10,20,30] True *Ch6> elem 40 [10,20,30,40] True
merge
Define a recursive function
merge :: Ord a ⇒ [a] → [a] → [a]that merges two sorted lists to give a single sorted list.For example:
> merge [2, 5, 6] [1, 3, 4] [1, 2, 3, 4, 5, 6]
Note: your definition should not use other functions on sorted lists such as insert or isort, but should be defined using explicit recursion.
merge :: Ord a => [a] -> [a] -> [a] merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) | x <= y = x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys
Example:
*Ch6> merge [2,5,6] [1,3,4] [1,2,3,4,5,6] *Ch6> merge [10..20] [1..10] [1,2,3,4,5,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20]
msort
Using merge, define a recursive function
msort :: Ord a ⇒ [a] → [a]that implements merge sort, in which the empty list and singleton lists are already sorted, and any other list is sorted by merging together the two lists that result from sorting the two halves of the list separately.Hint: First define a function
halve :: [a] → ([a], [a])that splits a list into two halves whose lengths differ by at most one.
First, following the hint, we define a halve function:
halve :: [a] -> ([a], [a]) halve xs = splitAt (length xs `div` 2) xs
As an example:
*Ch6> halve [1,2,3] ([1],[2,3]) *Ch6> fst ([1],[2,3]) [1] *Ch6> snd ([1],[2,3]) [2,3]
Now:
msort :: Ord a => [a] -> [a] msort [] = [] msort [x] = [x] msort xs = merge (msort fh) (msort sh) where (fh, sh) = halve xs
Example:
*Ch6> msort [3,2,90,54,1] [1,2,3,54,90]
sum
Using the five-step process, define the library functions that calculate the sum of a list of numbers, take a given number of elements from the start of a list, and select the last element of a non-empty list.
sum
Calculate the sum of a list of numbers.
Step 1 - define the types
sum :: Num a => [a] -> a
Step 2 - enumerate the cases
Then what are the cases:
sum [] sum (x:xs)
Step 3 - Define the simple case
Then defining it:
sum [] = 0
0 is the identity of the sum.
Step 4 - Define the other cases
sum (x:xs) = x + sum xs
Step 5 - Generalise and simplify
First, what do we got?
sum :: Num a => [a] -> a sum [] = 0 sum (x:xs) = x + sum xs
This follows the same recursion pattern that the one for product, which is encapsulated in the foldr function, thus simplifying gives:
sum :: Num a => [a] -> a sum = foldr (+) 0
Example:
*Ch6> summ [3,2,90,54,1] 150
take
take a given number of elements.
Step 1 - define the types
take :: Int -> [a] -> [a]
Step 2 - enumerate the cases
Then what are the cases:
- we take no elements in any list
- or we take some elements in an empty list.
take 0 _ = take _ [] =
Step 3 - Define the simple case
Either way, we return an empty list.
take 0 _ = [] take _ [] = []
Step 4 - Define the other cases
We take the head of the list, it becomes the head of a new list. The tail of the list is made by taking n-1 elements in xs.
take n (x:xs) = x : (take (n-1) xs)
Step 5 - Generalise and simplify
First, what do we got?
take :: Int -> [a] -> [a] take 0 _ = [] take _ [] = [] take n (x:xs) = x : (take (n-1) xs)
Example:
*Ch6> take 0 [1..10] [] *Ch6> take 10 [] [] *Ch6> take 3 [1..10] [1,2,3]
last
Select the last element of a non empty list.
Step 1 - define the types
last :: [a] -> a
Step 2 - enumerate the cases
Then what are the cases:
last [] last [x]
Step 3 - Define the simple case
Then defining it:
last [] = [] last [x] = x
Step 4 - Define the other cases
last (_:xs) = last xs
Step 5 - Generalise and simplify
First, what do we got?
last :: [a] -> a last [x] = x last (x:xs) = last xs
Example:
*Ch6> last [1..10] 10