Exploring Haskell: Recursive Functions

In Haskell recursion serves as the basic mechanism for looping.

Basic Concepts

It is possible to define a function which can call itself. This is the basic principle behind recursion.

-- Without recursion
fac :: Int -> Int
fac n = product [1 .. n]

-- With recursion
fac :: Int -> Int
fac 0 = 1
fac n = n * fac (n - 1)

-- Which can be traced as:

fac 3 -- { applying fac }
↓
3 * fac 2 -- { applying fac }
↓
3 * (2 * fac 1) -- { applying fac }
↓
3 * (2 * (1 * fac 0)) -- { applying fac }
↓
3 * (2 * (1 * 1)) -- { applying * }
↓
6

Same for the multiplication function, which can be defined via multiple additions.

(*) :: Int -> Int -> Int
m * 0 = 0
m * n = m + (m * (n - 1))

4 * 3 -- { applying * }
↓
4 + (4 * 2) -- { applying * }
↓
4 + (4 + (4 * 1)) -- { applying * }
↓
4 + (4 + (4 + (4 * 0))) -- { applying * }
↓
4 + (4 + (4 + 0)) -- { applying + }
↓
12

Recursion on Lists

Previously mentioned product function can be defined with recursion.

product :: Num a => [a] -> a
product []       = 1
product (n : ns) = n * product ns

product [2,3,4] -- { applying product }
↓
2 * product [3,4] -- { applying product }
↓
2 * (3 * product [4]) -- { applying product }
↓
2 * (3 * (4 * product [])) -- { applying product }
↓
2 * (3 * (4 * 1)) -- { applying * }
↓
24

Function length can be defined in a similar way.

length :: [a] -> Int
length []       = 0
length (_ : xs) = 1 + length xs

Defining reverse can be done this way.

reverse :: [a] -> [a]
reverse []       = []
reverse (x : xs) = reverse xs ++ [x]

reverse [1,2,3] -- { applying reverse }
↓
reverse [2,3] ++ [1] -- { applying reverse }
↓
(reverse [3] ++ [2]) ++ [1] -- { applying reverse }
↓
((reverse [] ++ [3]) ++ [2]) ++ [1] -- { applying reverse }
↓
(([] ++ [3]) ++ [2]) ++ [1] -- { applying ++ }
↓
[3,2,1]

And ++ operation.

(++) :: [a] -> [a] -> [a]
[]       ++ ys = ys
(x : xs) ++ ys = x : (xs ++ ys)

[1,2,3] ++ [4,5] -- { applying ++ }
↓
1 : ([2,3] ++ [4,5]) -- { applying ++ }
↓
1 : (2 : ([3] ++ [4,5])) -- { applying ++ }
↓
1 : (2 : (3 : ([] ++ [4,5]))) -- { applying ++ }
↓
1 : (2 : (3 : [4,5])) -- { list notation }
↓
[1,2,3,4,5]

Here's a recursive function that inserts values to an ordered list.

insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y : ys) | x <= y    = x : y : ys
                  | otherwise = y : insert x ys

insert 3 [1,2,4,5] -- { applying insert }
↓
1 : insert 3 [2,4,5] -- { applying insert }
↓
1 : 2 : insert 3 [4,5] -- { applying insert }
↓
1 : 2 : 3 : [4,5] -- { list notation }
↓
[1,2,3,4,5]

Using previously defined function creating insertion sort becomes easy.

isort :: Ord a => [a] -> [a]
isort []       = []
isort (x : xs) = insert x (isort xs)

isort [3,2,1,4] -- { applying isort }
↓
insert 3 (insert 2 (insert 1 (insert 4 []))) -- { applying insert }
↓
insert 3 (insert 2 (insert 1 [4])) -- { applying insert }
↓
insert 3 (insert 2 [1,4]) -- { applying insert }
↓
insert 3 [1,2,4] -- { applying insert }
↓
[1,2,3,4]

Multiple Arguments

For example library function zip takes two lists and produces a list of pairs.

zip :: [a] -> [b] -> [(a, b)]
zip []       _        = []
zip _        []       = []
zip (x : xs) (y : ys) = (x, y) : zip xs ys

zip ['a','b','c'] [1,2,3,4] -- { applying zip }
↓
('a',1) : zip ['b','c'] [2,3,4] -- { applying zip }
↓
('a',1) : ('b',2) : zip ['c'] [3,4] -- { applying zip }
↓
('a',1) : ('b',2) : ('c',3) : zip [] [4] -- { applying zip }
↓
('a',1) : ('b',2) : ('c',3) : [] -- { list notation }
↓
[('a',1), ('b',2), ('c',3)]

In a similar way the drop function is defined which removes a given number of elements from a list.

drop :: Int -> [a] -> [a]
drop 0 xs       = xs
drop _ []       = []
drop n (_ : xs) = drop (n - a) xs

Multiple Recursion

It is also possible to use recursive function multiple times.

-- Get fibonacci at n-th positions
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 2) + fib (n - 1)

Quicksort also demonstrates how multiple recursions occur inside a single function.

qsort :: Ord a => [a] -> [a]
qsort []       = []
qsort (x : xs) = qsort smaller ++ [x] ++ qsort larger
  where
    smaller = [ a | a <- xs, a <= x ]
    larger  = [ b | b <- xs, b > x ]

Mutual Recursion

Functions can also be defined recursively in terms of each other.

even :: Int -> Bool
even 0 = True
even n = odd (n - 1)

odd :: Int -> Bool
odd 0 = False
odd n = even (n - 1)

even 4 -- { applying even }
↓
odd 3 -- { applying odd }
↓
even 2 -- { applying even }
↓
odd 1 -- { applying odd }
↓
even 0 -- { applying even }
↓
True

Another pair of functions evens and odds can be defined similarly.

evens :: [a] -> [a]
evens []       = []
evens (x : xs) = x : odds xs

odds :: [a] -> [a]
odds []       = []
odds (_ : xs) = evens xs

evens "abcde" -- { applying evens }
↓
'a' : odds "bcde" -- { applying odds }
↓
'a' : evens "cde" -- { applying evens }
↓
'a' : 'c' : odds "de" -- { applying odds }
↓
'a' : 'c' : evens "e" -- { applying evens }
↓
'a' : 'c' : 'e' : odds [] -- { applying odds }
↓
'a' : 'c' : 'e' : [] -- { string notation }
↓
"ace"

Advice on Recursion

As an example product function will be used during next steps.

1. define the type

product :: [Int] -> Int

2. enumerate the cases

product :: [Int] -> Int
product []       =
product (n : ns) =

3. define the simple cases

product :: [Int] -> Int
product []       = 1
product (n : ns) =

4. define the other cases

product :: [Int] -> Int
product []       = 1
product (n : ns) = n * product ns

5. generalize and simplify

product :: Num a => [a] -> a
product []       = 1
product (n : ns) = n * product ns

Recursion is an important milestone to reach and understand. End.