How to Comprehend Comprehensions
Particularly for Erlang
So, I Gusti Ngurah Oka Prinarjaya was reading Joe’s Book and he found one of the most amazing examples of List Comprehensions I’ve ever seen…
perms([]) -> [[]];
perms(List) -> [ [H|T] || H <- List, T <- perms(List--[H]) ].Output:
1> lib_misc:perms("123").
["123","132","213","231","312","321"]And, of course… he couldn’t understand it. And, as a seasoned Erlang trainer, I got to tell you: He’s not alone… by any means. After a session of the BeamBA Meetup where I casually tried to explain something even simpler than this, we had to schedule another meetup talk just to explain how recursion works and how to think recursively.
So, let me try to explain how recursion and list comprehensions work together in perms/1, how can one end up with a function like that and how to read it. Let’s see how far I can get in a blog post… and Robert Virding (I know you’re a fan of perms/1) please point out the mistakes I’ll surely make ;)
How to write a function like that?
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? 😉
How to read a function like that?
Well, that was fun, but what if you are faced with a function like that and your job is to understand it, not to write it. Well, a neat technique you can use it to compute the reductions manually or using the debugger. I’ll do it manually here.
What we’ll be doing is basically emulating the VM work by hand, one step at a time. So, let’s start with a sample expression and let’s see what the VM would do. To be clear: these are not the actual reductions in the VM. I took some liberties, mostly because LCs are just syntactic sugar. But I hope you understand what I’m showing here…
perms("123").
% Second clause of perms/1
[ [H|T] || H <- "123", T <- joe:perms("123" -- [H])].
% Expansion of the first generator
[ [$1|T] || T <- joe:perms("123" -- "1") ] ++
[ [$2|T] || T <- joe:perms("123" -- "2") ] ++
[ [$3|T] || T <- joe:perms("123" -- "3") ].
% Reduction of --
[ [$1|T] || T <- joe:perms("23") ] ++
[ [$2|T] || T <- joe:perms("13") ] ++
[ [$3|T] || T <- joe:perms("12") ].
% Multiple second clauses of perms/1
[ [$1|T]
|| T <- [ [H|T1] || H <- "23", T1 <- joe:perms("23" -- [H])]] ++
[ [$2|T]
|| T <- [ [H|T1] || H <- "13", T1 <- joe:perms("13" -- [H])] ] ++
[ [$3|T]
|| T <- [ [H|T1] || H <- "12", T1 <- joe:perms("12" -- [H])] ].
% Multiple expansion of first generators and --
[ [$1|T]
|| T <- [ [$2|T1] || T1 <- joe:perms("3")] ++
[ [$3|T1] || T1 <- joe:perms("2")] ] ++
[ [$2|T]
|| T <- [ [$1|T1] || T1 <- joe:perms("3")] ++
[ [$3|T1] || T1 <- joe:perms("1")] ] ++
[ [$3|T]
|| T <- [ [$1|T1] || T1 <- joe:perms("2")] ++
[ [$2|T1] || T1 <- joe:perms("1")] ].Let’s work on perms(“3”) alone for a second…
perms("3").
% Second clause of perms/1
[ [H|T] || H <- "3", T <- joe:perms("3" -- [H])].
% Expansion of the first generator
[ [$3|T] || T <- joe:perms("3" -- "3")].
% Reduction of --
[ [$3|T] || T <- joe:perms("")].
% First clause of perms/1
[ [$3|T] || T <- [[]]].
% Expansion of the generator
[ [$3|[]] ].
% List reduction (and some syntax sugar)
["3"].And you can work with the other small lists in an analogous manner. So, going back to the original example…
% Multiple expansion of all simple perm/1's
[ [$1|T]
|| T <- [ [$2|T1] || T1 <- ["3"]] ++
[ [$3|T1] || T1 <- ["2"]] ] ++
[ [$2|T]
|| T <- [ [$1|T1] || T1 <- ["3"]] ++
[ [$3|T1] || T1 <- ["1"]] ] ++
[ [$3|T]
|| T <- [ [$1|T1] || T1 <- ["2"]] ++
[ [$2|T1] || T1 <- ["1"]] ].
% Expansion of all simple generators
[ [$1|T] || T <- [[$2|"3"]] ++ [[$3|"2"]] ] ++
[ [$2|T] || T <- [[$1|"3"]] ++ [[$3|"1"]] ] ++
[ [$3|T] || T <- [[$1|"2"]] ++ [[$2|"1"]] ].
% Reduction of cons operator
[ [$1|T] || T <- ["23"] ++ ["32"] ] ++
[ [$2|T] || T <- ["13"] ++ ["31"] ] ++
[ [$3|T] || T <- ["12"] ++ ["21"] ].
% Reduction of ++
[ [$1|T] || T <- ["23", "32"] ] ++
[ [$2|T] || T <- ["13", "31"] ] ++
[ [$3|T] || T <- ["12", "21"] ].
% Expansion of generators
[[$1|"23"]] ++ [[$1|"32"]] ++
[[$2|"13"]] ++ [[$2|"31"]] ++
[[$3|"12"]] ++ [[$3|"21"]].
% Reduction of ++ and cons
["123", "132", "213", "231", "312", "321"].Et voilà! 🎉
What you see here is kind of the same algorithm I described above:
For each element in the original list, find all the permutations for the sublist that results from removing it, then attach the element to the head of each permutation.
It’s quite a simple algorithm to describe (and thus the resulting function is also quite simple and descriptive) but it might be hard to understand how such an algorithm actually solves the problem. I hope this article brings some light on the subject. 😃
In Other News…
SpawnFest
We’re less than a month away from SpawnFest!
This year it will happen on September 21st & 22nd.
Register your team and join us for FREE to win several amazing prizes provided by our great sponsors!
ElixirConfLA
ElixirConf is coming to Latin America for the first time!
Thanks to our friends from PlayUS Media, we’ll meet in Medellín, Colombia for ElixirConfLA on October 24th & 25th.
It will be an awesome event, you don’t want to miss it :)
Erlang Battleground
We’re still looking for writers. If you want to write on Erlang Battleground, just let us know! ✍️
