In the previous chapter, you learned about functions in Haskell. Many times, in real-world applications you’ll work with functions that recall themselves, which is a process called
recursion
. In this chapter, you will learn what recursion is, see some concrete examples, and learn how you implement them in Haskell and how to apply recursion on lists.
Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem (as opposed to iteration).
—Wikipedia
Let’s start with a simple example. Do you remember the factorial function from math class? Well, it is defined as follows:
This function is also known as n!. The first branch represents an edge condition, which tells when the function terminates. It is important because it will finish the recursive call; otherwise, the execution will enter into an infinite loop.
Returning to the factorial function, you write it in
Haskell as follows:
fact 0 = 1
fact n = n * fact (n - 1)
After writing the previous two lines into a file called
Fact.hs and loading the file, let’s test it.
*Main> fact 5
120
*Main> fact 0
1
*Main> :t fact 5
fact 5 :: (Eq p, Num p) => p
When Haskell needs to decide which function definition to choose, it starts with the foremost definition and picks up the first one that matches. Therefore, the order of definitions in a recursive function is important. If you switched the definitions, you would never get a result, because Haskell would always be stuck in the first definition, fact n = n*fact(n-1). This fact leads us to the following note.
If you call fact for a negative number, an infinite loop will be encountered. Why is that? This happens because
Haskell will always choose the general definition, because it will never reach the edge condition. Anticipating a little, you can use the function
error from
Prelude to report an error (in this example, the function fact cannot be applied on negative integers or any other value that’s not positive). You can improve the function
fact as follows:
fact 0 = 1
fact n | n > 0 = n * fact (n - 1)
| otherwise = error "Wrong input"
Now, for example, if you call fact for
-5 or
3.4, you get the following:
*Main> fact (-5)
*** Exception: Wrong input
CallStack (from HasCallStack):
error, called at Fact.hs:3:22 in main:Main
*Main> fact 3.5
*** Exception: Wrong input
CallStack (from HasCallStack):
error, called at Fact.hs:3:22 in main:MainRecursive Functions on Lists
Handling for and while Loops from Imperative Languages
In Haskell, you don’t have for or while loops like in imperative languages; instead, you declare what something is instead of saying how to get it. Therefore, recursion is even more important because you use it to say what something is.
In functional languages, these loops are expressed as computations over lists. Usually, the following three functions can be used to replace
for/
while loops
:
map
applies a function given as a parameter to every element of a list.
foldl
goes through the entire list from left to right.
foldr
goes through the entire list from right to left.
Of course, these can be combined with other functions (predefined or your own functions) and used on lists to create algorithms that are more complex.
Further, let’s say you have a list of positive integers and you want to compute every element’s factorial. You already saw a fact function defined in the previous section, which computes the factorial for one number. To apply it on the numbers of a list, you proceed as follows:
*Main> map fact [2, 9, 8]
[2,362880,40320]
How simple is that? In this way, you eliminated the need for the while/for loop.
You will learn more about foldl and foldr in Chapter 15.
Recursion on Lists
Let’s begin this section with a simple example: list creation itself. You already know that a list can be empty and you can add an element into a list using the : operator. For example, the list [1,2,3,4] is created as 1:(2:(3:(4:[]))). Here, you used : recursively (remember that an operator is actually a function).
The next function you’ll look at is
reverse. You can define your recursive
recursiveReverse
as follows:
recursiveReverse :: [a] -> [a]
recursiveReverse [] = []
recursiveReverse (x:xs) = recursiveReverse xs ++ [x]
Let’s see how it works:
*Main> recursiveReverse [3,2,6,7]
[7,6,2,3]
Remember that
reverse reverses a list. In the function’s body, a reversed empty list is the empty list itself. On the last line, you concatenate the first element of the list given as a parameter to the end of an existing list. For this example, it works like this:
recursiveReverse [3,2,6,7]
recursiveReverse [2,6,7] ++ [3]
(recursiveReverse [6,7] ++ [2]) ++ [3]
((recursiveReverse [7] ++ [6]) ++ [2]) ++ [3]
(((recursiveReverse [] ++ [7]) ++ [6]) ++ [2]) ++ [3]
On the last line, the call reaches the edge condition. Further, it continues with the following:
((([] ++ [7]) ++ [6]) ++ [2]) ++ [3]
(([7] ++ [6]) ++ [2]) ++ [3]
([7,6] ++ [2]) ++ [3]
[7,6,2] ++ [3]
[7,6,2,3]
That’s it. Next, you implement the recursive version of the
filter function
.
recursiveFilter :: (a -> Bool) -> [a] -> [a]
recursiveFilter condition [] = []
recursiveFilter condition (x:xs)
| condition x = x : recursiveFilter condition xs
| otherwise = recursiveFilter condition xs
You call it as follows:
*Main> recursiveFilter (<10) [2, -9, 4, 20, 0, 100]
[2,-9,4,0]
*Main> import Data.Char
*Main Data.Char> recursiveFilter (isLetter) "Ann has 5 apples."
"Annhasapples"
To use the isLetter function, you need to import the Data.Char module.
Other functions on
lists that can be defined recursively are
length,
repeat,
maximum,
minimum,
take, and
`elem`.
recursiveLength :: [a] -> Int
recursiveLength [] = 0
recursiveLength (x:xs) = 1 + recursiveLength xs
recursiveReverse :: [a] -> [a]
recursiveReverse [] = []
recursiveReverse (x:xs) = recursiveReverse xs ++ [x]
recursiveRepeat :: a -> [a]
recursiveRepeat x = x:recursiveRepeat x
recursiveMaximum :: (Ord a) => [a] -> a
recursiveMaximum [] = error "Empty list"
recursiveMaximum [x] = x
recursiveMaximum (x:xs) = max x (recursiveMaximum xs)
recursiveMinimum :: [Int] -> Int
recursiveMinimum (x:[]) = x
recursiveMinimum (x:xs) = x `min` recursiveMinimum xs
recursiveTake :: (Num i, Ord i) => i -> [a] -> [a]
recursiveTake n _
| n <= 0 = []
recursiveTake _ [] = []
recursiveTake n (x:xs) = x : recursiveTake (n-1) xs
recursiveElem :: (Eq a) => a -> [a] -> Bool
recursiveElem a [] = False
recursiveElem a (x:xs)
| a == x = True
| otherwise = a `elem` xs
Feel free to use and test these functions.
Pattern Matching and Recursion
In this section, you will learn about a pattern matching technique that allows you to write a standard skeleton for recursive functions on lists.
Let’s start with a general definition.
recursiveFunction [] = -- this is the edge condition
recursiveFunction (x:xs) = -- this is the general case
The edge condition is not allowed to include recursive calls; otherwise, it would lead to an infinite loop. The edge condition
must return a value, as you saw in the previous sections. The type of the returned value needs to be the same as the type annotation in the function. Here’s an example:
recursiveReverse :: [a] -> [a]
This definition means the edge condition should have the type
[a], so the “most particular” case for
[a] is the empty list
[].
For the recursion, the recursive function needs to call itself like this:
recursiveFunction (x:xs) = function x recursiveFunction xs
or like this:
recursiveFunction (x:xs) = recursiveFunction xs function x
function assures the chaining of recursive calls. The order of
recursiveFunction and
function depends on the effective specifications. To make it more intuitive, here is how to use
function as an operator:
recursiveFunction (x:xs) = x `function` recursiveFunction xs
Don’t forget to check the annotation type of the recursive function because `function` needs to act accordingly.
For example, in
recursiveReverse,
`function` is actually the operator
++.
recursiveReverse (x:xs) = recursiveReverse xs ++ [x]
Finally, you can obtain the recursive version of recursiveReverse, as defined in the previous section.
Summary
In this chapter, you learned about the following:
What recursion is and why it is important
How to handle for and while loops from imperative languages by using recursion in the functional language Haskell
How to write some common functions recursively on lists
How to write a general skeleton of a recursive function using pattern matching
References
- 1.
R. Hinze and J. Jeuring, “Generic Haskell: Practice and Theory.” Generic Programming (Springer, 2003), 1–56
- 2.
C. McBride, “Faking It Simulating Dependent Types in Haskell,” Journal of Functional Programming, 12(4–5), 375–392 (2002)
- 3.
- 4.
- 5.
- 6.
