Learn You a Haskell for Great Good! - Miran Lipovaca [24]
Finally, comparing 2 to the maximum of [5,1], which we now know is 5, we obtain the answer to the original problem. Since 5 is greater than 2, we can now say that 5 is the maximum of [2,5,1].
A Few More Recursive Functions
Now that we’ve seen how to think recursively, let’s implement a few more functions this way. Like maximum, these functions already exist in Haskell, but we’re going to write our own versions to exercise the recursive muscle fibers in the recursive muscles of our recursive muscle groups. Let’s get buff!
replicate
First off, we’ll implement replicate. Remember that replicate takes an Int and a value, and returns a list that has several repetitions of that value (namely, however many the Int specifies). For instance, replicate 3 5 returns a list of three fives: [5,5,5].
Let’s think about the base cases. We immediately know what to return if we’re asked to replicate something zero or fewer times. If we try to replicate something zero times, we should get an empty list. And we declare that the result should be the same for negative numbers, because replicating an item fewer than zero times doesn’t make sense.
In general, a list with n repetitions of x is a list with x as its head and a tail consisting of x replicated n-1 times. We get the following code:
replicate' :: Int -> a -> [a]
replicate' n x
| n <= 0 = []
| otherwise = x : replicate' (n-1) x
We used guards here instead of patterns because we’re testing for a Boolean condition.
take
Next up, we’ll implement take. This function returns a specified number of elements from a specified list. For instance, take 3 [5,4,3,2,1] will return [5,4,3]. If we try to take zero or fewer elements from a list, we should get an empty list, and if we try to take anything at all from an empty list, we should get an empty list. Notice that those are our two base cases. Now let’s write the function:
take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
| n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n-1) xs
Notice that in the first pattern, which specifies that we get an empty list if we try to take zero or fewer elements from a list, we use the _ placeholder to match the list value, because we don’t really care what it is in this case. Also notice that we use a guard, but without an otherwise part. That means that if n turns out to be more than 0, the matching will fall through to the next pattern.
The second pattern indicates that if we try to take any number of things at all from an empty list, we get an empty list.
The third pattern breaks the list into a head and a tail. We call the head x and the tail xs. Then we state that taking n elements from a list is the same as creating a list that has x as its first element and n-1 elements from xs as its remaining elements.
reverse
The reverse function takes a list and returns a list with the same elements, but in the reverse order. Once again, the empty list is the base case, since trying to reverse an empty list just results in the empty list. What about the rest of the function? Well, if we split the original list into its head and tail, the reversed list that we want is the reverse of the tail, with the head stuck at the end:
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
repeat
The repeat function takes an element and returns an infinite list composed of that element. A recursive implementation of repeat is really easy:
repeat' :: a -> [a]
repeat' x = x:repeat' x
Calling repeat 3 will give us a list that starts with 3 as the head and has an infinite amount of 3s as the tail. So calling repeat 3 evaluates to 3:repeat 3, which evaluates to 3:(3:repeat 3), which evaluates to 3:(3:(3:repeat 3)), and so on. repeat 3 will never finish evaluating. However, take 5 (repeat 3) will give us a list of five 3s. Essentially, it’s like calling replicate 5 3.
This is a nice example of how we can successfully use recursion that doesn’t have a base case to make infinite lists—we just have to be sure to chop them off somewhere along the