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
  1. enumerate the cases
product :: [Int] -> Int
product [] =
product (n : ns) =
  1. define the simple cases
product :: [Int] -> Int
product [] = 1
product (n : ns) =
  1. define the other cases
product :: [Int] -> Int
product [] = 1
product (n : ns) = n * product ns
  1. 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.



You've made it to the end! Sharing this article on your favorite social media network would be highly appreciated 🧑‍💻! For more information you can find me on Twitter.

Published