Recursion!

This is the weapon of a functional programmer. Not as clumsy or random as a for-loop; an elegant weapon for a more civilized age.

Taking a step back from a pretty dense chapter on more functional patterns, this time we’re looking specifically at one thing: recursion. Chapter 8 of the book covers this in pretty good detail, giving a fairly wide range of examples, but I’ll be trying to distill it down to its essence in this post. Let’s start at the very beginning, why don’t we?

## What is recursion?

A recursive function is—in its simplest terms—a function which calls itself. As the book describes it: “recursion is defining a function in terms of itself via self-referential expressions.” This means that until some condition is met, the function will keep calling itself. If this condition is never met, the function never terminates. Recursion is an important concept in Haskell, because it gives us a way to express indefinite computations.

### Base cases

To reiterate: given that it terminates, a recursive function is a function that will keep calling itself until some condition to stop recursing is met. This condition is often known as the base case. For instance, let’s look at writing a factorial function, which is a function that multiplies all positive integers (1..n) up to and including the number we’re calculating for. In maths, it’s commonly written using an exclamation point, such as 4!.

So we’re all on the same page about what the function should do, 4! is evaluated as 4 ⋅ 3 ⋅ 2 ⋅ 1, which is equal to 24.

To make this a recursive function, we know that for any number n greater than one, it is the result of the factorial of n − 1 multiplied by n. In other words, for n greater than one, n! = n ⋅ (n − 1)!. If n is 1, then n! = 1. In our case, the function is not defined for integers less than one.

Based on the little analysis above, we now know that the value of n! is recursively dependent on the value of (n − 1)! and so on. We have also identified our base case: 1. So how would we go about writing this out? How about something like this:

factorial :: Integral a => a -> a
factorial 1 = 1
factorial n = n * factorial (n - 1)

Note that this function does not terminate if applied to a value less than 1. This is an issue that we’ll come back to shortly.

### Recursion as indefinite function composition

One thing that the book mentions that I found quite interesting, is that you can think of recursion as indefinite function composition. When composing functions, all we do is pipe the output of one function into another function. Recursion is the same thing, except it’s always the same function. We can use this to create functions that will get applied an arbitrary number of times. Indeed, taking it a step further, we can write a function that takes a function, an argument, and the number of times to apply it, and then applies the function the set number of times:

applyNTimes :: (Integral a) => a -> (b -> b) -> b -> b
applyNTimes 0 _ b = b
applyNTimes n f b = f . applyNTimes (n - 1) f \$ b

Using this, we can create an increment function:

increment :: (Integral a, Num b) => a -> b -> b
increment times = applyNTimes times (+1)
-- increment 5 2 = 7

A contrived example, but it’s a pretty cool effect!

## Bottom

I mentioned when talking about the factorial function that it doesn’t terminate for every possible value we can apply it to. A function that never terminates is one of the ways we can play with bottoms in Haskell (and no, it’s not a kinky as it sounds!).

In Haskell, bottom (symbolically: ⊥) is used to refer to computations that do not result in a value. The two main varieties of bottom are computations that fail with an error (partial functions) and computations that fail to terminate (such as with infinite recursion and the factorial example above). When you can, stay away from bottom.

## Definitons

This chapter only comes with a single definition: recursion. The funny thing would be to tell you to start from the top, but let’s be boring and do it the proper way:

Recursion
Recursion is a means of computing results that may require an indefinite amount of work to obtain through the use of repeated function application. A recursive function will usually have at least one case that calls itself and a base case that stops the recursion.

More Functional Patterns: Function composition and pointfree style

Hey, and welcome back to the third and final part of chapter 7 of Haskell Programming From First Principles! Today we’ll be looking at function composition and pointfree style; two related topics that are very commonly seen in Haskell.

## Function composition

Let’s start of with function composition. Function composition allows us to create new functions by combining existing ones. The one criterion for composing two functions is that the return value (range) of the first function matches the input value (domain) of the second function. In Haskell, we use the dot operator (.) to compose two functions.

Let’s inspect the type signature of the . operator and see if we can unpack it:

(.) :: (b -> c) -> (a -> b) -> a -> c

At first, this may seem a bit complicated, so let’s break it down. The . operator goes between two functions (like this: f . g) and returns a function that goes from a to c. What it does is to simply ‘glue’ the two provided functions together.

I quite like Scott Wlaschin’s explanation of it from his talk The Power of Composition (this link takes you to the point in the talk that talks about gluing together functions, but I highly recommend checking out the whole thing if you’re interested), where he talks about gluing together a transformation from an apple to a banana, and a function from a banana to a cherry to create a function from an apple to a cherry.

The simplest way to explain composition may be to say that you perform an operation on a value, and then pass the result of that operation to the next function. That new function which puts those two together is the composed function. You might see an example like this:

(f . g) x = f (g x)

This tells us that applying f composed with g to x is the same as applying g to the argument x and then applying f to the result of that. Note that the . operator might initially appear to read backwards: It’s the last function to get run that gets written out first. This is because of it’s mathematical roots, where people use the ‘∘’ symbol for composing functions (so our f . g would be f ∘ g). I suggest reading the symbol as ‘after’, which makes it ‘f after g’, for instance.

If this is all a bit abstract and jargon-y, why don’t we look at a concrete example. Say we want a function that tells us whether a string is of even length or not. In that case, we can express the full function as a composition of two smaller functions (the signatures have been simplified/specialized for the sake of example; check the REPL for more): even :: Int -> Bool, and length :: String -> Int (so it’d be ‘even after length’). Notice that the return type of length matches the input type of even, and that the type of isOfEvenLength matches the combination of the functions.

isOfEvenLength :: String -> Bool
isOfEvenLength = even . length

The astute reader (that’s you!) might notice that the function we defined as the composition of the other two functions (isOfEvenLength) doesn’t list any arguments in its definition. This might look strange but it takes us nicely into our next point: pointfree style.

## Pointfree style

Pointfree style is a way of writing functions without specifying their arguments, most notably when working with composition. It’s called ‘pointfree’ because the arguments are also known as ‘points’. There are arguments both for and against writing pointfree style, and it’s true that excessive use may cause code to become harder to understand, but used sensibly it can make code tidier, cleaner, and let’s us put the focus on the transformations, the functions, rather than the data supplied to them.

Using one of the examples from before, we now get:

(f . g) x = f (g x)
-- the above now becomes
f . g = \x -> f (g x)

-- similarly, we can add more functions
f . g . h = \x -> f (g (h x))

How does this work? Well, it all goes back to the lambda calculus and currying. Let’s take a step back and look at how you could write an alias for a function in Haskell:

f a b = -- ... implementation

g = f

In the above code, we have defined g as simply being the same as f. We’ll still need to provide it with the same arguments (a and b), but it’s just given a different name. If we want to, we can choose to define it as a specialized version of f, with the first argument already applied:

f a b = -- ... implementation

g = f 2

In this case, g is a partially applied version of f and is a function from one argument to a result (whatever f returns). We could also write the above as g x = f 2 x, but because of how partial application works, there’s no need to do this. We’ve already said that g is the same as f applied to 2, and that naturally returns a function from one argument to the result.

Similarly, we might do it for something like map. Say we want a function that doubles all values in a list:

doubleVals = map (*2)
-- is the same as
doubleVals xs = map (*2) xs

The two definitions above are equivalent, they’re just written out differently.

Whether you prefer pointfree or ‘pointful’ styles is an individual thing, and is probably based on experience and circumstance. As mentioned earlier, too much and it makes your code hard to read, too little and you’re writing out way more than what you need to and taking focus away from the important parts. Like with so many things, try and apply the Goldilocks principle. As always, the Haskell wiki has more detailed information on the topic, so go give that a read if you fancy.

## Definitions

As it’s the last post for this chapter, let’s go over the chapter definitions.

Anonymous function
Often known as a lambda. It is a function that isn’t bound to an identifier and is instead just used as an argument to another function or the like. For instance, \x -> x is an anonymous version of the id function (id x = x).
Currying
The act of transforming a function which takes multiple arguments to a series of nested functions that each take a single argument and return the next function in line (or the result if we’re at the end). In Haskell, every function is curried, and this is baked into the language so you don’t have to worry about it.
Pattern matching
A way to deconstruct various data types to do something with—or based on—their contents.
Bottom
Bottom is a non-value used to denote that a program cannot return a value or a result. A simple example would be an infinitely looping function, but values that don’t handle all their inputs and throw errors also apply here. We’ll talk more about Bottom in the chapter on non-strictness.
Higher-order functions
Functions that take other functions as arguments or return functions themselves.
Composition
A way of gluing together multiple functions such that each each function is applied to the result of the next function. Creates a pipeline of transformations.
Pointfree
Also known as ‘tacit programming’. Programming without mentioning arguments explicitly.

More Functional Patterns: Higher-order functions and guards

Continuing our foray into the More Functional Patterns chapter, today we’re looking at higher-order functions and guards.

## Higher-order functions

First off, let’s establish some common ground and agree on the definition. According to Wikipedia and the Haskell wiki, a higher-order function is a function that takes other functions as arguments or returns a function as a result. In essence, it’s a function that operates on functions as values. Because functions are just any other value in haskell1, this comes very naturally to the language.

So to qualify as a higher-order function, a function must fulfill one of two criteria:

Accept a function as a parameter

map and sorting functions are great examples of this. For instance, map’s signature is map :: (a -> b) -> [a] -> [b], where the first parameter is the function used to transform the values of type a in the list to values of type b. Sorting functions could take a comparison function (a -> a -> Ordering) and a list ([a]), sort the list for you and return the sorted list.

Return a function

This probably happens more than you realize. Any function that accepts more than one argument in Haskell is by default a higher-order function due to how the lambda calculus works. That said, you can also explicitly return a partially applied function based on the input arguments. For instance, this example takes a boolean value saying whether the function should return a partially applied multiplication or addition, and the first argument to apply to the calculation. It returns the partially applied function:

f :: Num a => Bool -> a -> (a -> a)
f multiply n =
if multiply then
(n*)
else
(n+)

It’s a silly example, but it gets the point across.

## Guards

Next up, the book returns to a form of pattern matching by introducing guards, which allow us to run code conditionally based on the truth of a statement. If you think that sounds a lot like an if-then-else expression, that’s because it works pretty much the same but with some different syntax. We’ll run through a couple of different examples to examine the various features that are introduced.

The basic syntax looks like this:

myAbs :: Integer -> Integer
myAbs x
| x < 0     = (-x)
| otherwise =   x

This function has two guards, each beginning with a pipe symbol (|). Note that we don’t need an equals sign after the arguments in the first line of the definition; instead, the symbol comes after each respective guard. The first of the guards that evaluates to True will be executed.

In this function, we have two cases: One for when the value of x is negative (in which case we’ll return the absolute value of x), and one for every other case. In the above example, we have used the word otherwise, which is a synonym for True, as a catch-all for every other case.

If we want to explicitly enumerate all options, we can do that too:

myAbs :: Integer -> Integer
myAbs x
| x <  0 = (-x)
| x >= 0 =   x

This will work the exact same as the previous version, but in this case we’re handling all cases explicitly. When explicitly listing all options, make sure you have enabled warnings (or errors) for non-exhaustive patterns to avoid accidentally partial functions.

What if we want to share some values between the different guards? We can use where-statements for that! Imagine a function that takes the lengths of the two legs (catheti) of a right triangle and returns whether the triangle is big, small, or medium based on the length of the hypotenuse:

triangleSize :: (Floating a, Ord a) => a -> a -> String
triangleSize c1 c2
| h >= 5 = "Big triangle"
| h >= 2 = "Medium triangle"
| h <  2 = "Small triangle"
where h = sqrt (c1^2 + c2^2)

When declaring variables like this, they’re in scope for all of the guards.

This last example also demonstrates the importance of order on the guards. Because only the first guard that evaluates to True is executed, the above function works as expected. If we switched the two guards for big and medium triangles, no triangle would ever be considered ‘big’. What a sad world that would be.

## Next up

That was all we had time for today, my dear reader. We still have a little bit left of this chapter: function composition and pointfree style. Two very interesting topics which I’m looking forward to covering next time. Until then: take care!

## Footnotes

1. You may have heard the term ‘first-class functions’. This is what that means. You can pass functions around like any other variable, store them in data structures, assign them to variables, and so forth. See MDN or Wikipedia for more.

First Prev Page 2 Next Last