Introduction

This is the third in a series of articles exploring the Gleam programming language. The first article explored some of the most basic features of Gleam; just enough to say hello. The second discussed looping constructs, namely that gleam doesn’t have them.

This one was supposed to investigate how Gleam integrates with Erlang’s famous OTP library for concurrency and fault tolerance. But I got sidetracked and ended up doing a second article on recursion and tail recursion instead.

Patreon

If you find my content valuable, please do consider sponsoring me on Patreon account. I write about what interests me, and I usually target tutorial style articles for intermediate to advanced developers in a variety of languages.

I’m not sure how far I’m going to go with this series on Gleam, so if you’re particularly interested in the topic, a few dollars a month definitely gives me a bit of motivation to keep it up.

Permutations problem

Here’s the problem I want to solve in this article: Given a count, what is the list of all possible letter combinations that contain that many letters. So, done correctly, permutations(3) should return:

aaa
aab
aac
aad
...<snipped over 17,000 combinations>...
zzw
zzx
zzy
zzz

If this seems like a weird problem to want to solve, try to think about how I might want to use it in Part 4 (hint: it’s nefarious, and it’s highly parallel).

Send me one letter

The first thing I need is a list of lowercase letters. I feel that should be as easy as passing the string "abcdefghijklmnopqrstuvwxyz" into a function that iterates over individual characters, but I couldn’t find one in the standard library. So I had to go a little more verbose:

const letters_list = [
  "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p",
  "q", "r", "s", "t", "u", "v", "w", "x", "y", "z",
]

This introduces us to the const keyword. It’s a bit surprising that the concept of constants exists, since all variables in Gleam are immutable, and therefore constant. However, const is special in that it can be defined outside a function (ie: at the global level). In practice, it’s just a value that the Gleam compiler copies inline everywhere it is used.

I could build up combinations of these tiny one-character strings into multi-character strings using string.append and similar functions. However, the Gleam documentation indicates that this isn’t a very efficient operation and that we should use string_builder instead. That means I need a list of string_builder.StringBuilder objects instead of a list of string.Strings.

Unfortunately, const doesn’t permit us to pipe primitives into arbitrary functions, so instead I created the following function, which takes zero arguments and uses the const defined above to return a list of StringBuilders using the magic of iterators:

fn letters() -> iterator.Iterator(string_builder.StringBuilder) {
  letters_list
  |> iterator.from_list
  |> iterator.map(string_builder.from_string)
}

Permutations of letters (the “wrong” way)

Now we can build a recursive function that takes those tiny one-letter strings and builds up bigger strings. For pedagogical purposes, and not because I did it wrong the first time (no, not at all), let’s build this up using traditional recursion. We’ll convert it to tail recursion later, and take delight in the fact that the more appropriate code is also more legible code. But let’s keep it ugly first.

The function should take a count for the length of string we are looking for, and return an iterator over all the possible permutations of lowercase letters that have that length. Here’s a first stab at the function signature:

pub fn permutations(count: Int) -> iterator.Iterator(string_builder.StringBuilder) {...}

The first thing to note here is the pub keyword, which means the function can be accessed by code in other modules (not that we’ve talked about modules yet in this series).

This publicness (publicosity?) comes with a cost, though. Here’s the problem: count technically needs to be a positive integer, or at least non-negative. There is no unsigned integer type, so if we want to check it, we’ll have to do the work ourselves.

Technically, because Gleam doesn’t yet support exhaustve case checking, we could just ignore this case and let our program have undefined behaviour. But this is a public function and we can’t trust the calling code to know what will break our code, so let’s be complete.

We need a way to inform the calling function if the check fails. Therefore, we actually need to return a Result . Here is the function returning a Result that also handles that failure case and the 0 and 1 base cases:

pub fn permutations(
  count: Int,
) -> Result(iterator.Iterator(string_builder.StringBuilder), String) {
  case count {
    x if x < 0 -> Error("count must be non-negative")
    0 -> Ok(iterator.empty())
    1 -> Ok(letters())
    n -> ??????
  }
}

If count is negative, return an error. If it is zero, return an empty iterator (there are no permutations containing no letters). If it is one, return the iterator over the 26 letters of the English alphabet (I apologize if you are not a native English speaker. Your alphabet probably has way cooler characters than mine and I’m jealous) that we defined earlier.

Seems ok so far. However, my first attempt to implement the recursive arm was a bit of a disaster:

    n ->
      permutations(n - 1)
      |> result.map(fn(tail_iter) {
        tail_iter
        |> iterator.flat_map(fn(tail) {
          letters()
          |> iterator.map(fn(letter) {
            string_builder.append_builder(tail, letter)
          })
        })
      })

There is so much wrong here, the worst of it being that it’s impossible to read. I had a hell of a time just getting all the braces and parenthesis in the right place before it would compile. Maybe Gleam isn’t the language for me after all?

Since the code isn’t readable, let me attempt to explain it in words. I’ll probably fail. You might have to read it twice. You might have to give up and skip to my attempts to clarify this code. I wanted to, let me tell you.

We take the output of the call to permutations on the smaller number and pass it to result.map. This function is used to apply a function to the value inside the returned Result and return a new Result if the Result is Ok.

This arm first calls permutations recursively, to get an iterator over all the possible letter combinations that are “one character shorter”.

The function that is applied accepts an iterator and passes it through a rather difficult to understand/explain function called flat_map. The argument is a function that accepts the iterator and returns another iterator. The flat in the name means that all the returned iterators get smooshed together into one iterator. If we just used the normal iterator.map function, we’d get an iterator of iterators (which we could then flatten using iterator.flatten, so flat_map is just a convenience).

The anonymous function that flat_map is called on accepts each iterator in turn and then calls the letters function we defined before to get an iterator over 26 letters. We use the string_builder.append_builder function to concatenate the letter to the existing tail. This is a bit weird because it’s using a closure syntax; the tail variable is defined in the outer scope but is available inside the function passed into map.

Problems with this code

The most glaring code smell is that this function is not tail recursive (as I discussed briefly in part 2). Gleam can’t calculate the current iteration until all of the “smaller” iterations have completed. We’ll solve this tail-recursively later, but let’s keep trying to tidy this version up before we give up on it completely.

The second code smell is the deep indentation. Clean code does one thing at a time, but this code calls a function that needs a function that needs a function…

So… let’s try to remove some of the indent-madness, starting with Result.map. Normally I find that construct makes code easier to read, but in this case, it’s just ugly.

Worse, it’s completely unnecessary, because the result will always be Ok. Can you see why? This recursive arm is only called if n is 2 or higher, so when we call the function with n-1, the number n has to be 1 or higher, which means it’s not going to hit the Error case. It’ll never be negative, because a negative n is handled by the first case instead of going into the recursive arm.

So let’s just use assert (discussed in part 1) on the value returned from permutations, shall we:

    n -> {
      assert Ok(tail_iter) = permutations(n - 1)
      Ok(
        tail_iter
        |> iterator.flat_map(fn(tail) {
          letters()
          |> iterator.map(fn(letter) {
            string_builder.append_builder(tail, letter)
          })
        }),
      )
    }

Ugh, that’s no better. Just as much indentation. We can assign the intermediate result to a variable and wrap it in Ok after the fact:

    n -> {
      assert Ok(tail_iter) = permutations(n - 1)
      let iter =
        tail_iter
        |> iterator.flat_map(fn(tail) {
          letters()
          |> iterator.map(fn(letter) {
            string_builder.append_builder(tail, letter)
          })
        })

      Ok(iter)
    }

We’re sacrificing vertical space to save on some indentation, a practice I’m very familiar with as a Python programmer. Another way to remove some indentation is to take away the pipes and use the composition syntax instead:

    n -> {
      assert Ok(tail_iter) = permutations(n - 1)
      let iter =
        iterator.flat_map(
          tail_iter,
          fn(tail) {
            iterator.map(
              letters(),
              fn(letter) { string_builder.append_builder(tail, letter) },
            )
          },
        )
      Ok(iter)

We can also make the calls a bit more descriptive using Gleam’s labelled argument syntax (labels looked up from the Gleam documentation):

    n -> {
      assert Ok(tail_iter) = permutations(n - 1)
      let iter =
        iterator.flat_map(
          over: tail_iter,
          with: fn(tail) {
            iterator.map(
              over: letters(),
              with: fn(letter) { string_builder.append_builder(tail, letter) },
            )
          },
        )
      Ok(iter)
    }

That’s… acceptable. I guess. I could move the outer with function to a top level function and I’d probably be ok with it, but the truth is, I only showed you this function because it was the first version that came to mind it’s a “how not to do it” situation.

Let’s switch the whole thing to be tail recursive and discover that it’s easier to read and code than the traditional recursive version (this isn’t normal in most languages).

Tail Recursion (revisited)

The key to successful tail recursion is passing an “accumulator” into the recursive call that collects any intermediate results. This accumulator can then be returned directly when the base case is hit. When you call the function, prime the accumulator with an appropriate initial value and have at it. In our case, the inital accumulator could be the list of 26 letters we already know how to generate. Then the recursive call will pass in the list of 676 two-letter strings to the third call and so on.

It is common (though not required) to put the bit that primes the accumulator in its own separate function. That way the calling code doesn’t have to know about tail recursion, so the API is a bit cleaner. In our case, there is another added benefit to having a separate function: the negativity check. (I don’t know if we can get rid of the negativity, but I’m optimistic…).

So let’s trim back the permutations function to something like it was originally:

pub fn permutations(
  count: Int,
) -> Result(iterator.Iterator(string_builder.StringBuilder), String) {
  case count {
    x if x < 0 -> Error("count must be non-negative")
    0 -> Ok(iterator.empty())
    n -> Ok(permutations_recursive(letters(), n))
  }
}

This checks the negative and empty cases, and then only calls the yet-to-be-defined (we’re almost there) recursive function if we know n is a positive number.

The permutations_recursive function is kept private to this module, so we can manually guarantee that it is never called with a non-positive integer, and therefore, a Result return type is not required on that function.

Note how very readable the case statement above is, with each arm getting a single line of code. This is a good indicator that splitting our function in two will indeed help make things more readable.

Since we’ve defined the calling code already, we know the signature for the new function is as follows:

fn permutations_recursive(
  tails: iterator.Iterator(string_builder.StringBuilder),
  count: Int,
) -> iterator.Iterator(string_builder.StringBuilder) {
  ...
}

The difference between this and our earlier attempt at a recursive function is that we are passing the newly constructed tails into the recursive call, instead of constructing new tails from the results of the recursive call. Clearly we’ll have to return the tails eventually, so let’s add a base case for the lowest possible number count can be (any lower and the outer permutations function won’t call this one):

fn permutations_recursive(
  tails: iterator.Iterator(string_builder.StringBuilder),
  count: Int,
) -> iterator.Iterator(string_builder.StringBuilder) {
  case count {
    1 -> tails
    n -> ...
  }
}

Simple enough so far. The recursive call needs to construct new tails and call itself with a slightly smaller count. I reuse the flat_map logic from my earlier attempt (good thing I had this article open with all my notes, eh?), but it is a bit tidier now:

  case count {
    1 -> tails
    n ->
      letters()
      |> iterator.flat_map(fn(letter) {
        tails
        |> iterator.map(fn(tail) { string_builder.append_builder(tail, letter) })
      })
      |> permutations_recursive(n - 1)
  }

Note how I am able to pipe the new list of tails directly into the permutations_recursive call. If you were wondering why I put count as the second argument instead of first, now you know. Pipes are wonderful, so make sure your APIs have nice pipe fittings.

The indentation still reads a little wonky to my eye, but I don’t think I can make it any neater. It’s possible I’m just not used to the way gleam formats things.

Summary

I was expecting you to know a little something about parallel programming in Gleam at this point, but I guess that’ll have to wait for part 4. Yes, there will be a part 4 It’s already partially written. I had to butcher the hell out of it when I realized I was going off track and needed to pull an entire section out to create this one.

Anyway, you’ve now seen what it takes to convert a function from traditional to tail recursion in Gleam. This was an important exercise because while traditional recursion is often easier to reason about (though it’s still a mind-bender), tail recursion is both more performant, and (in Gleam, at least) often easier to read.

And you have a way to generate a list of all possible letter combinations of a certain length. That’s going to come in handy next article, I promise.