How to Comprehend Comprehensions - Erlang Battleground

By Brujo Benavides

So, let’s first think of how will we come up with such a beautiful function.

The requirement here is pretty simple:

The function perms/1 should receive a single argument (a list) and return the list of all possible permutations of it.

To understand what it does, let’s write a test for it, shall we? (I’ll use strings, since that’s what Joe used in his book, but any list will do)

Cool, if we try to run that test it will tell us that we need to implement the function…

1> c(joe), joe:test().** exception error: undefined function joe:perms/1 in function joe:test/0 (joe.erl, line 6)

2>

We can start with the base case then… The only permutation of an empty list is itself.

That moved us one step ahead. Cool!

2> c(joe), joe:test().** exception error: no function clause matching joe:perms("a") (joe.erl, line 13) in function joe:test/0 (joe.erl, line 7)

3>

Now, for the recursive step…

When writing recursive functions, we must assume that we know how to apply the function to a smaller input. In our case, we’re working with lists, so a smaller input can be the tail of the list (since it’s a smaller list). That’s why my first step when writing this code would be something like this…

perms([H|T]) -> … perms(T) ….

In other words, I take the head of the list (H) and apply the function recursively to its tail (T). Now we have to figure out how to move from the list of permutations for T to the list of permutations for [H|T] .

So, let’s say H=a, T=[b,c], then perms(T) == [[b,c], [c,b]] and we want to get to [[a,b,c], [a,c,b], [b,a,c], [c,a,b], [b,c,a], [c,b,a]]. 🤔

The first two are easy to build: [ [H|P] || P <- perms(T) ]. So far, so good. Let’s try it and see what the tests have to say about it.

3> c(joe), joe:test().** exception error: no match of right hand side value ["ab"] in function joe:test/0 (joe.erl, line 8)

4>

Right… perms("ab") is not equal to ["ab", "ba"] , it’s just ["ab"]. We’re just adding the permutations that have the elements in order, since we’re traversing the list from left to right. We need a different way to reduce our list.

So far we had perms(T) be the list of permutations of the elements in the tail of the list. What if we had access to the list of all permutations of any sublist of the original list ([H|T]) with one element less (i.e. what if for [a,b,c] we could build the list of all permutations for [a,b], the list of all permutations for [b,c], and the one for [a,c]). In that case, to build the final result we will only need to add the missing element to their heads.

Too complex? Well… let’s go step by step… First let’s build all the sublists…

perms(List) -> [List -- [H] || H <- List].

Let’s test that on the shell for a second…

4> c(joe), joe:perms("ab").["b","a"]5> c(joe), joe:perms("abc").["bc","ac","ab"]6> c(joe), joe:perms("abcd").["bcd","acd","abd","abc"]

7>

Nice! So… this following code won’t work, but if we could compute the permutations for each of those sublists like this…

perms(List) -> [perms(List -- [H]) || H <- List].

…we would end up with something like…

4> c(joe), joe:perms("ab").[["b"],["a"]]5> c(joe), joe:perms("abc").[["bc","cb"], ["ac","ca"], ["ab","ba"]]

6>

Let me first apply a neat trick here to flatten the list. Something we can easily do in List Comprehensions by just using multiple generators.

perms(List) -> [T || H <- List, T <- perms(List -- [H])].

Again, using a built-up example since the code won’t actually work like this…

4> c(joe), joe:perms("ab").["b","a"]5> c(joe), joe:perms("abc").["bc","cb", "ac","ca", "ab","ba"]

6>

We’re really close there. To get from ["b","a"] to the actual result we want (["ab", "ba"]) we just need to prepend each list with the element we originally removed (which is H in our code). Let’s try that!

7> c(joe), joe:test().ok

8>

Well… that’s Joe’s code, isn’t it? What did you expect? 😉