Fun and Functions with Gleam

Recursion and Recursive Thinking

---

Recursion

A key difference between functional and imperative programming languages is the concept of immutability. This usually forces us to rethink problems in a more mathematical, recursive fashion. For example, consider the simple problem of calculating the sum of integers from 1 to n.

In an imperative programming language, an idiomatic solution could look like this:

int sum = 0;
for (int i = 1; i <= n; ++i) {
    sum += i;
}

However, if we attempt to translate this directly to Gleam, we quickly run into issues. First of all, there is no for or while expression in Gleam, and if there were, we still wouldn’t have a way to update the values of i and sum as we can’t mutate variables in Gleam.

An idiomatic implementation in Gleam could look something like this:

fn sum(n: Int) -> Int {
    case n {
        0 -> 0              // (1)
        _ -> n + sum(n - 1) // (2)
    }
}

In this code, instead of using a loop, we use the function in its definition, which is called recursion. Substituting loops with recursion is very common when translating imperative code to functional code.

Recursive (or inductive) thinking means “assuming that the recursive function works correctly” and using it by that assumption. For example, on line (2), we use the sum function recursively with the assumption that it returns the correct result for numbers smaller than n. Using that assumption, we know that the “correct thing to do” is to add our n to the previous result. The reason recursion works, is mathematical induction (or specifically induction over natural numbers in this case):

1. We show the base case (1) is correct, i.e. sum(0) evaluates to 0.
2. Inductive/recursive case (2), where assuming sum(n - 1) is correct, we produce the result of n + sum(n - 1).

Think why calling sum with negative numbers “breaks the function”. One reason is that negative numbers are not natural numbers so the same induction principle doesn’t work for them. Gleam unfortunately doesn’t have a type for natural numbers…

Loading Exercise...

Loading Exercise...

Loading Exercise...

Loading Exercise...

The Linked List

pub type List {
  Cons(Int, List)
  Nil
}

Consider the algebraic data type defined above. Notice anything peculiar?

What you might have noticed is that this ADT is recursive, meaning that at least one of its variants contains the type itself. The above data type describes a linked list where each node is either Cons(head, tail) or Nil.

fn is_empty(l: List) -> Bool {
  case l {
    Cons(_) -> False
    Nil -> True
  }
}

The above function uses the case expression from the previous chapter to determine if the given List is empty.

We can implement the head and tail functions for our List as follows:

Run the program to see the output

Iterating Over a Recursive ADT

As one might expect, traversing a list (or any recursive ADT) is also achieved with recursion. For instance, consider the following function that calculates the sum of a given List:

fn sum(l: List) -> Int {
    case l {
        Cons(h, t) -> h + sum(t)
        Nil -> 0
    }
}

The function traverses through the List one element at a time, by destructuring it into a head and a tail on each “iteration” until finally reaching the Nil list.

Loading Exercise...

Higher-Order Functions and Mapping Over Recursive Structures

As we know, functions are not restricted to taking regular values¹ as arguments. They can also take functions as arguments. Higher-order functions allow programmers to, for example, “customize the behavior” of a function.

Perhaps one of the most common functions in functional style code is the map function, which applies a function to each element in the collection returning the mapped version of the collection. Below is an example of the map function for our List of integers.

fn map(f: fn(Int) -> Int, l: List) -> List {
  case l {
    Cons(h, t) -> Cons(f(h), map(f, t))
    Nil -> Nil
  }
}

This map function takes in a function with type signature , but it could theoretically also take in or (or really a function of any return type).

While map “preserves” the structure (i.e. the order and shape) of the collection, there exist also a plethora of useful functions that “alter” the structure, for instance, the filter function that takes in a predicate and returns a collection that consists only of elements in the original collection for which the predicate returns True.

Run the program to see the output

Loading Exercise...

Loading Exercise...

Footnotes

Footnotes

1. Functions are also values, but here we are referring to values of base types such as integers or custom data types. ↩