HASKELL RECURSION

REVISED: Wednesday, January 24, 2024

Haskell Recursion.

I.  HASKELL RECURSION SOURCE CODE EXAMPLES

Loops:

Haskell has neither a "for loop" nor a "while loop."

When trying to understand recursion, you may find it easier to think about how the algorithm behaves for a given input. It is easy to get hung up on what the execution path looks like, so instead ask yourself questions like:

What happens if I pass an empty list?

What happens if I pass a list with one item?

What happens if I pass a list with many items?

Or, for recursion on numbers:

What happens if I pass a negative number?
What happens if I pass 0?
What happens if I pass a number greater than 0?

The structure of a recursive algorithm is often just a matter of covering the above cases.

Recursive Definitions: 

A list is either

null, written []; or cons, written :

which is constructed, and written x:xs, with head x (an element), and tail xs (a list). xs is the plural of x, and should be read that way.

A natural number is either

zero, written 0, or

successor, written n+1

with predecessor n (a natural number).

Commonly used symbols are

--     :: is read as "has type of."
--     [] is read as "empty list."
--     -> is read as an "arrow" and separates parameters.
--     : is read as "cons" and is the append-head operator.
--     | is read as "guard."

--     = is read as "is."
--     := is read as "is replaced by."

A. HASKELL RECURSION

1. Pattern Matching

Pattern matching is basically giving cases of the function. Haskell looks through the patterns and applies the first one that fits what it is trying to evaluate.

Example 1

"Copy Paste" the following Haskell squaresRec function into your text editor and "File, Save As" squaresRec.hs to your working directory:

squaresRec            :: [Double] -> [Double]   -- Type signature.
squaresRec []        = []                                  -- Base case.
squaresRec (x:xs) = x*x : squaresRec xs     -- Recursive case.

The "base case" ensures that squaresRec halts when it reaches the end of the input list.

The "recursive case" constructs a new list that is the same length as its input list, with every element in the input list substituted with its square in the output list.

Load squaresRec into GHCi:

Prelude>  :load squaresRec
[1 of 1] Compiling Main             ( squaresRec.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Call the squaresRec function as follows:

Prelude>  squaresRec [1.0,2.0,3.0]
[1.0,4.0,9.0]
it :: [Double]
Prelude>

Prelude>  :type squaresRec
squaresRec :: [Double] -> [Double]   -- squaresRec type signature.
Prelude> 

When the recursive function squaresRec is called its execution path is as follows:

squaresRec [1.0,2.0,3.0]
=
squaresRec (1.0 : (2.0 : (3.0 : [])))
=
1.0*1.0 : squaresRec (2.0 : (3.0 : []))
=
1.0*1.0 : (2.0*2.0 : squaresRec (3.0 : []))
=
1.0*1.0 : (2.0*2.0 : (3.0*3.0 : squaresRec []))
=
1.0*1.0 : (2.0*2.0 : (3.0*3.0 : []))
=
1.0 : (4.0 : (9.0 : []))
=
[1.0,4.0,9.0]

Example 2

"Copy Paste" the following Haskell oddsRec function into your text editor and "File, Save As" oddsRec.hs to your working directory:

oddsRec :: [Integer] -> [Integer]                         -- Type signature.
oddsRec []                                  = []                             -- Base case.
oddsRec (x:xs) | odd x          = x : oddsRec xs    -- Guard recursive case.
                          | otherwise = oddsRec xs          -- Guard recursive case.

The "base case "ensures that oddsRec halts when it reaches the end of the input list.

Load oddsRec into GHCi:

Prelude>  :load oddsRec
[1 of 1] Compiling Main             ( oddsRec.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Call the oddsRec function as follows:

Prelude>  oddsRec [1,2,3]
[1,3]
it :: [Integer]
Prelude>

Prelude>  :type oddsRec
oddsRec :: [Integer] -> [Integer]   -- oddsRec type signature.
Prelude>  

When the recursive function oddsRec is called its execution path is as follows:

oddsRec [1,2,3]
=
oddsRec (1 : (2 : (3 : [])))
=
1 : oddsRec (2 : (3 : []))
=
1 : oddsRec (3 : [])
=
1 : (3 : oddsRec [])
=
1 : (3 : [])
=
[1,3]

Example 3

"Copy Paste" the following Haskell enumFromToRec function into your text editor and "File, Save As" enumFromToRec.hs to your working directory:

enumFromToRec :: Int -> Int -> [Int]     -- Type signature.
enumFromToRec m n | m > n     = []         -- Guard base case.
                                    | m <= n = m : enumFromToRec (m+1) n

Load enumFromToRec into GHCi:

Prelude>  :load enumFromToRec
[1 of 1] Compiling Main             ( enumFromToRec.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Call the enumFromToRec function as follows:

Prelude>  enumFromToRec 1 3
[1,2,3]
it :: [Int]
Prelude>

Prelude>  :type enumFromToRec
enumFromToRec :: Int -> Int -> [Int]   -- enumFromToRec type signature.
Prelude>  

When the recursive function enumFromToRec is called its execution path is unfolded as follows:

               
enumFromToRec 1 3
=
1 : enumFromToRec 2 3
=
1 : (2 : enumFromToRec 3 3)
=
1 : (2 : (3 : enumFromToRec 4 3))
=
1 : (2 : (3 : []))
=
[1,2,3]

Example 4

"Copy Paste" the following Haskell factorialRec function into your text editor and "File, Save As" factorialRec.hs to your working directory:

factorialRec    :: Int -> Int                                    -- Type signature.
factorialRec n = fact 1 n
    where
    fact :: Int -> Int -> Int                                     -- Type signature.
    fact m n | m > n     = 1                                      -- Guard base case.
                   | m <= n = m * fact (m+1) n      -- Guard recursive case.

Load factorialRec into GHCi:

Prelude>  :load factorialRec
[1 of 1] Compiling Main             ( factorialRec.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Call the factorialRec function as follows:

Prelude>  factorialRec 3

6
it :: Int
Prelude>  

Prelude>  :type factorialRec

factorialRec :: Int -> Int  -- Type signature.

Prelude>

When the recursive function factorialRec is called its execution path is unfolded as follows:
             
factorialRec 3
=
fact 1 3
=
1 * fact 2 3
=
1 * (2 * fact 3 3)
=
1 * (2 * (3 * fact 4 3))
=
1 * (2 * (3 * 1))
=
6

Example 5

"Copy Paste" the following Haskell factorial function into your text editor and "File, Save As" factorial.hs to your working directory:

factorial :: Int -> Int                         -- Type signature.
factorial 0 = 1                                      -- Base case.
factorial n = n * factorial (n - 1)  -- Recursive case.

Load factorial into GHCi:

Prelude>  :load factorial
[1 of 1] Compiling Main            ( factorial.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Call the factorial function as follows:

Prelude>  factorial 3

6
it :: Int
Prelude>  

Prelude>  :type factorial

factorial :: Int -> Int  -- Type signature.

Prelude>

When the recursive function factorial is called its execution path is as follows:

factorial 3
=
3 * factorial (3 - 1)
=
3 * factorial 2
=
3 * (2 * factorial (2 - 1))
=
3 * (2 * factorial 1)
=
3 * (2 * ( 1 * factorial (1 - 1)))
=
3 * (2 * ( 1 * factorial 0))
=
3 * (2 * (1))
=
6

2. Conditionals With Binding

"Copy Paste" the following Haskell squaresCond function into your text editor and "File, Save As" squaresCond.hs to your working directory:

squaresCond :: [Integer] -> [Integer]
squaresCond ws =
    if null ws then
        []
    else
        let
            x   = head ws
            xs = tail ws
        in
            x*x : squaresCond xs

Load squaresCond into GHCi:

Prelude>  :load squaresCond
[1 of 1] Compiling Main             ( squaresCond.hs, interpreted )
Ok, modules loaded: Main.
Prelude>  

Call the squaresCond function as follows:

Prelude>  squaresCond [1,2,3]
[1,4,9]
it :: [Integer]
Prelude>  

Prelude>  :type squaresCond
squaresCond :: [Integer] -> [Integer]
Prelude>

When the recursive function squaresCond is called its execution path is as follows:

squaresCond [1,2,3]
=
squaresCond (1 : (2 : (3 : [])))
=
1*1 : squaresCond (2 : (3 : []))
=
1*1 : (2*2 : squaresCond (3 : []))
=
1*1 : (2*2 : (3*3 : squaresCond []))
=
1*1 : (2*2 : (3*3 : []))
=
1 : (4 : (9 : []))
=
[1,4,9]

B. HASKELL RECURSIVE MULTIPLICATION EXAMPLE

Mathematical induction is the basic theoretical background for recursion.

Recursion replaces loop constructs in imperative programs in a mathematically sound way.

"Copy Paste" the following module example into your text editor:

module Productx where

productx              :: Num a => [a] -> a   -- Function signature.
productx []             = 1                               -- Base case.
productx (n : ns) = n * productx ns        -- Recursive case.

The example above should be saved as Productx.hs to your working directory.

The function productx is defined in terms of itself; therefore, productx is recursive.

The function signature shows, for any type a of Num, productx is a function that maps a list of such numbers to a single such number.

In the definition of the function, the first equation states that the empty list is one, the identity for multiplication. The second equation states that the product of any non-empty list is given by multiplying the first number and the product of the remaining list of numbers.

Each application of productx reduces the length of the argument list by one, until the list eventually becomes empty at which point the recursion stops.

Open GHCi and load Productx as shown below:

Prelude> :load Productx

[1 of 1] Compiling Productx         ( Productx.hs, interpreted )

Ok, modules loaded: Productx.

Prelude>

Since the function signature for Productx shows a list of numbers mapped to  a single number, we have to use a list of arguments when we call the function in GHCi, as shown below:

Prelude> productx [1..4]

24

it :: (Num a, Enum a) => a
Prelude>

Prelude>  :type productx
productx :: Num a => [a] -> a
Prelude>  

When the recursive function productx is called its execution path is as follows:

productx [1..4]
=
productx (1 : (2 : (3 : (4 : []))))
=
1 * productx (2 : (3 : (4 : [])))
=
1 * (2 * productx (3 : (4 : [])))
=
1 * (2 * (3 * productx (4 : [])))
=
1 * (2 * (3 * (4  * productx ([])))
=
1 * (2 * (3 * (4 * (1))))
=
24

C. HASKELL RECURSIVE PERMUTATIONS EXAMPLE

A permutation of a list is a list with the same elements in a different order. The permutats function returns a list of all permutations of a list.

"Copy Paste" the following module example into your text editor:

module Permutats where

import Data.List

permutats     :: Eq a => [a] -> [[a]]                                                -- Function signature.
permutats [] = [[ ]]                                                                          -- Base case.
permutats xs = [ x:ps | x <- xs , ps <- permutats (xs\\[x]) ]        -- Recursive case.

The example above should be saved as Permutats.hs to your working directory.

The function permutats is defined in terms of itself; therefore, permutats is recursive.

Recursively [[a]] is a list of values of type [a], i.e. a list of lists of a.

The Eq class defines equality == and inequality /=.

The function signature shows, for any type a of Eq, permutats is a function that maps a list of such numbers to a list of lists of such numbers.

In the definition of the function, the first equation states that the empty list has one permutation, itself. The second equation states that if xs is not empty, a permutation is given by picking an element x from xs and putting x at the front of a permutation of the remainder xs \\ [x] . The operation '\\' returns the difference of two lists: xs \\ ys is the list xs with each element of ys removed, if it is present.

Each application of permutats reduces the length of the argument list by one, until the list eventually becomes empty at which point the recursion stops.

Open GHCi and load Permutats as shown below:

Prelude> :load Permutats

[1 of 1] Compiling Permutats        ( Permutats.hs, interpreted )

Ok, modules loaded: Permutats.

Prelude>

Since the function signature for Permutats shows a list of numbers mapped to a list of lists, we have to use a list of arguments when we call the function in GHCi, as shown below:

Prelude> permutats [1..4]

[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[1,4,3,2],[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],[3,1,2,4],[3,1,4,2],[3,2,1,4],[3,2,4,1],[3,4,1,2],[3,4,2,1],[4,1,2,3],[4,1,3,2],[4,2,1,3],[4,2,3,1],[4,3,1,2],[4,3,2,1]]

it :: (Num a, Eq a, Enum a) => [[a]]
Prelude> 

Prelude>  :type permutats
permutats :: Eq a => [a] -> [[a]]
Prelude>  

D. HASKELL RECURSIVE SUMMATION EXAMPLES

Example 1

"Copy Paste" the following module example into your text editor:

module Summation where
summation             :: Num a => [a] -> a    -- Function signature.
summation []            = 0                                -- Base case.
summation (x : xs) = x + summation xs    -- Recursive case.

The example above should be saved as Summation.hs to your working directory.

The function summation is defined in terms of itself; therefore, summation is recursive.

The function signature shows, for any type a of Num, summation is a function that maps a list of such numbers to a single such number.

In the definition of the function, the first equation states that the sum of the empty list is zero, the identity for addition. The second equation states that the sum of any non-empty list comprising a first number x and a remaining list of numbers xs is given by adding x and the summation of xs.

Each application of summation reduces the length of the argument list by one, until the list eventually becomes empty at which point the recursion stops.

Open GHCi and load Summation as shown below:

Prelude> :load Summation

[1 of 1] Compiling Summation        ( Summation.hs, interpreted )

Ok, modules loaded: Summation.

Prelude>

Since the function signature for Summation shows a list of numbers mapped to  a single number, we have to use a list of arguments when we call the function in GHCi, as shown below:

Prelude> summation [1..4]
10
it :: (Num a, Enum a) => a
Prelude>  

Prelude>  :type summation
summation :: Num a => [a] -> a
Prelude>

Example 2

"Copy Paste" the following Haskell sumRec function into your text editor and "File, Save As" sumRec.hs to your working directory:

sumRec            :: [Integer] -> Integer
sumRec []          = 0
sumRec (x:xs) = x + sumRec xs

Open GHCi and load sumRec as shown below:

Prelude>  :load sumRec
[1 of 1] Compiling Main             ( sumRec.hs, interpreted )
Ok, modules loaded: Main.
Prelude> 

Call the sumRec function as follows:

Prelude>  sumRec [1,2,3]
6
it :: Integer
Prelude>  

Prelude>  :type sumRec
sumRec :: [Integer] -> Integer
Prelude>  

When the recursive function sumRec is called its execution path is as follows:

sumRec [1,2,3]
=
sumRec (1 : (2 : (3 : [])))
=
1 + sumRec (2 : (3 : []))
=
1 + (2 + sumRec (3 : []))
=
1 + (2 + (3 + sumRec []))
=
1 + (2 + (3 + 0))
=
6

Example 3

"Copy Paste" the following Haskell sumSqOddRec function into your text editor and "File, Save As" sumSqOddRec.hs to your working directory:

sumSqOddRec :: [Integer] -> Integer
sumSqOddRec []                                  = 0
sumSqOddRec (x:xs) | odd x          = x*x + sumSqOddRec xs
                                    | otherwise = sumSqOddRec xs

Open GHCi and load sumSqOddRec as shown below:

Prelude>  :load sumSqOddRec
[1 of 1] Compiling Main             ( sumSqOddRec.hs, interpreted )
Ok, modules loaded: Main.
Prelude>  

Call the sumSqOddRec function as follows:

Prelude>  sumSqOddRec [1,2,3]
10
it :: Integer
Prelude>  

Prelude>  :type sumSqOddRec
sumSqOddRec :: [Integer] -> Integer
Prelude> 

When the recursive function sumSqOddRec is called its execution path is as follows:

sumSqOddRec [1,2,3]
=
sumSqOddRec (1 : (2 : (3 : [])))
=
1*1 + sumSqOddRec (2 : (3 : []))
=
1*1 + sumSqOddRec (3 : [])
= 
1*1 + (3*3 + sumSqOddRec [])
=
1*1 + (3*3 + 0)
=
1 + (9 + 0)
=
10

II. TYING THE KNOT

Tying the knot is a solution to the problem of circular data structures. This procedure allocates only two numbers 0 and 1 in memory. We produce two open-ended objects, and then link their ends together. The procedure of doing so is called tying the knot. 

"Copy Paste" the following Haskell function into your text editor and "File, Save As" TyingTheKnot.hs to your working directory:

module TyingTheKnot where

cyclic :: [Integer]
cyclic = let x = 0 : y
                   y = 1 : x
              in  x

Load TyingTheKnot into GHCi:

Prelude>  :load TyingTheKnot
[1 of 1] Compiling TyingTheKnot     ( TyingTheKnot.hs, interpreted )
Ok, modules loaded: TyingTheKnot.
Prelude>

Call the cyclic function:

Prelude>  take 10 cyclic
[0,1,0,1,0,1,0,1,0,1]
Prelude>

When the function cyclic is called its execution path is as follows:

= x
= 0 : y
= 0 : 1 : x -- Knot! Back to the beginning.
= 0 : 1 : 0 : y
= -- etc. take had to be used when calling cyclic without take cyclic is an infinite loop.

III. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.

In this tutorial, you have received an introduction to Haskell recursion.