You're reading from Haskell Design Patterns Take your Haskell and functional programming skills to the next level by exploring new idioms and design patterns

Product type Paperback

Published in Nov 2015

Publisher

ISBN-13 9781783988723

Length 166 pages

Edition 1st Edition

Languages

Haskell

Concepts

Design Patterns

Author (1):

Ryan Lemmer

View More author details

Table of Contents (9) Chapters

Preface

1. Functional Patterns – the Building Blocks FREE CHAPTER

2. Patterns for I/O

3. Patterns of Composition

4. Patterns of Folding and Traversing

5. Patterns of Type Abstraction

6. Patterns of Generic Programming

7. Patterns of Kind Abstraction

Index

Recursion

Recursion is even more fundamental than functions and types, in the sense that we can have recursive functions and types. Moreover, "recursion" can refer to syntax (a function or type referring to itself) or to the execution process.

Non-tail recursion

Recursion can be viewed as a pattern for avoiding a mutable state:

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

Without recursion, we would need to iterate through the list and keep adding to an intermediary sum until the list is exhausted, as shown in the following code:

sumNonTail [2, 3, 5, 7]

This first expands into a nested chain of deferred operations, and when there are only primitives left in the expression, the computation starts folding back in on itself:

-- 2 + sumNonTail [3, 5, 7]
-- 2 + (3 + sumNonTail [5, 7])
-- 2 + (3 + (5 + sumNonTail [7]))
-- 2 + (3 + (5 + (7 + sumNonTail [])))
-- 2 + (3 + (5 + (7 + 0)))
-- 2 + (3 + (5 + 7))
-- 2 + (3 + 12)
-- 2 + 15
-- 17

The sumNonTail function is non-tail-recursive. Because the recursion is "trapped" by the + operator, we need to hold the entire list in memory to perform the sum.

Tail recursion

Tail recursion addresses the exorbitant use of space we have with non-tail-recursive processes:

sumTail' acc [] = acc
sumTail' acc (x:xs) = sumTail' (acc + x) xs
sumTail xs = sumTail' 0 xs

This form of recursion looks less like mathematical induction than the sumNonTail function did, and it also requires a helper function sumTail' to get the same ease of use that we had with sumNonTail. The advantage is clear when we look at the use of "constant space" in this process:

-- sumTail [2, 3, 5, 7]
-- sumTail' 0 [2, 3, 5, 7]
-- sumTail' 2 [3, 5, 7]
-- sumTail' 5 [5, 7]
-- sumTail' 10 [7]
-- sumTail' 17 []
-- 17

Even though sumTail is a recursive function, it expresses an iterative process. sumNonTail is a recursive function that expresses a recursive process.

Folding abstracts recursion

Tail recursion is captured by the foldl function, as shown in the following code:

  foldlSum = foldl (+) 0

The foldl function expands in exactly the same way as sumTail'. In contrast, foldrSum expands in the same way as sumNonTail:

foldrSum = foldr (+) 0

One can clearly see the tail recursion in the definition of foldl, whereas in the definition of foldr, recursion is "trapped" by f:

foldr _ v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

foldl _ v [] = v
foldl f v (x:xs) = foldl f (f v x) xs