5 step process to write recursive functions

Writing a recursive function takes some practice. Hutton recommends a 5-step process for beginners for writing recursive functions. I am finding the process very useful to systematically think through the problem so I thought to take a note.

Steps

1. Define type
2. List cases
3. Define simple case(s)
4. Define other case(s)
5. Generalize and simplify

For example…

sum

Calculate sum of a list of numbers:

1. Define type - let's define the sum initially for integers only:

sum :: [Int] -> Int

2. List cases - here we look at the argument(s) and see what are possible cases. For sum, we have one argument - a list. So the cases will be empty list and non-empty list:

sum [] =
sum (x:xs) =

3. Define simple case - for the empty list, sum is 0 since 0 is identity for sum. This often is the base case.

sum [] = 0
sum (x:xs) =

4. Define other cases - this often is the recursive case. Here we need to think about how sum, x, xs and any other library function(s) can be used to handle this case. For sum, it is the addition of x and sum of xs:

sum [] = 0
sum (x:xs) = x + sum xs

5. Now can we generalize the type? In this case, addition can be applied to numbers of any type and not just integers, so we can modify the type:

sum :: Num a => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs

take

take a given number of elements from the start of a list:

1. Define type - here we realize that take can be applied to list of any type:

take :: Int -> [a] -> [a]

2. List cases - since there are two arguments, an Int and a list, there are four possible cases:

take 0 [] =
take n [] =
take 0 (x:xs) =
take n (x:xs) = 

3. Define simple case - taking 0 elements from any list should give us the empty list. Let's also propose that taking n elements from an empty list gives an empty list too:

take 0 [] = []
take n [] = []
take 0 (x:xs) = []
take n (x:xs) = 

4. Define other cases - taking n elements from a non-empty list is equivalent to head consed to taking (n-1) elements from tail:

take 0 [] = []
take n [] = []
take 0 (x:xs) = []
take n (x:xs) = x : take (n-1) xs

5. Now can we generalize the type? Well, the type is already general, but we note from the above cases that when we take 0 elements, we always get an empty list, so we can use a wild-card pattern to combine the two cases. We can also replace n when the list is empty by wild-card since n is never used in defining that case.

take :: Int -> [a] -> [a]
take 0 _ = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs

last

Select the last element of a non-empty list:

1. Define type - can again be defined as a list of any type:

last :: [a] -> a

2. List cases - a singleton and a non-empty list with two or more elements:

last [x] =
last (x:xs) =

3. Define simple case - a list with single element should return that element:

last [x] = x
last (x:xs) =

4. Define other cases - all other lists throw the head away and apply the function to the tail:

last [x] = x
last (x:xs) = last xs

5. Generalize and simplify - no further simplification is needed here:

last :: [a] -> a
last [x] = x
last (x:xs) = last xs