Demo: https://lucamug.github.io/elm-tutorial-permutations-and-recursion/ (inspect the console for more insights)
Suppose we have a list of list of elements. Let’s build a function to create all possible combinations of these elements. respecting their order.
For example, if this is the input:
[ [ “1”, “2” ], [ “a”, “b” ] ]This should be the output:
[ [ “1”, “a” ], [ “1”, “b” ], [ “2”, “a” ], [ “2”, “b” ] ]The function should work with any quantity of elements, for example:
[ [] ][ [ “1” ], [ "a" ], [ "x" ] ][ [ “1”, "2" ], [ "a", "b" ], [ "x", "y", "z" ], [ "@", "#" ] ]
The type signature of the function should be
List ( List a ) → List ( List a )How to address the problem?
We could go trough each inner element and we add these element to an accumulator that initially is an empty list.
Let’s suppose we are working with this input:
[ [ “1”, “2” ], [ “a”, “b” ] ]1) We take the first element of the list (the head): [ “1”, “2” ]
2) We take the first element of this list and we add to the accumulator, that was empty. The accumulator is now [ “1” ].
3) We take the second element of the list
4) We take the first element of this list and we add to the accumulator. The accumulator is now [ “1”, “a” ]
5) There is no third element in the list, so the accumulator is now one of the permutation.
6) We remove the last item added to the accumulator. The accumulator is now back to [ “1” ]
7) We move to the second element of the second list. Now the accumulator is [ “1”, “b” ]
The process can go ahead this way for many steps but some of these steps seems repeating.
At this point recursion seem a natural way to simplify and generalise this algorithm.
Let’s start from the final step in the chain and let’s move backwards.
How do we detect that we reached the last list? At each step we remove one element from the main list and when the list is empty, it means that we reached the end. To check if we are at the last step we can write
generateCombinations1 list =
case Debug.log "head is" (List.head list) of
Nothing ->
-- We reached the end
[] Just head ->
-- Still stuff to process
[]
Running the function with
generateCombinations2 [ [ “a”, “b” ], [ “1”, “2” ] ]the console output is:
head is: Just [“a”,”b”]Now we need to repeat this step one more time.
We extract the remaining part of the main list, using List.tail, and call the same function again. First lets extract the tail and output some info into the console.
generateCombinations2 list =
case Debug.log "head is" (List.head list) of
Nothing ->
[] Just head ->
let
tail =
case Debug.log "tail is" (List.tail list) of
Just data ->
data Nothing ->
[]
in
[]
The console says
head is: Just [“a”,”b”]
tail is: Just [[“1”,”2"]]Good, we got the head and the tail, as expected.
Lets try calling the function with the tail and see what happen
generateCombinations3 list =
case Debug.log "head is" (List.head list) of
Nothing ->
[] Just head ->
let
tail =
case Debug.log "tail is" (List.tail list) of
Just data ->
data Nothing ->
[]
in
generateCombinations3 tail
The console:
head is: Just [“a”,”b”]
tail is: Just [[“1”,”2"]]
head is: Just [“1”,”2"]
tail is: Just []
head is: NothingNice! Now we need to add an accumulator so that that we can build the output. For the moment lets just add a list and add some test data to it. Also let’s return the accumulator in case the List.head is Nothing.
generateCombinations4 acc list =
let
_ =
Debug.log "acc is" acc
in
case Debug.log "head is" (List.head list) of
Nothing ->
[ acc ] Just head ->
let
tail =
case Debug.log "tail is" (List.tail list) of
Just data ->
data Nothing ->
[]
in
generateCombinations4 ("test" :: acc) tail
The console:
acc is: []
head is: Just [“a”,”b”]
tail is: Just [[“1”,”2"]]
acc is: [“test”]
head is: Just [“1”,”2"]
tail is: Just []
acc is: [“test”,”test”]
head is: NothingOur accumulator is getting populated.
The output is now [[“test”,”test”]]
Now we want to add meaningful stuff in the accumulator instead of “test”. Lets loop all the items in the head and add to the accumulator one by one.
So instead just adding “test” as per
generateCombinations4 (“test” :: acc) tailWe do
List.map (\item -> generateCombinations4 (item :: acc) tail ) headThis doesn’t work. Elm compiler is complaining that:
The 1st branch has this type:
List (List a)But the 2nd is:
List (List (List a))
The first branch is returning the proper type but there is something wrong with the second branch. Too many nested lists. Elm need all branches to be of the same type. The solution is to use List.concat to reduce the nesting level of the List. This will work:
generateCombinations5 acc list =
let
_ =
Debug.log "acc is" acc
in
case Debug.log "head is" (List.head list) of
Nothing ->
[ acc ] Just head ->
let
tail =
case Debug.log "tail is" (List.tail list) of
Just data ->
data Nothing ->
[]
in
List.concat
(List.map
(\item ->
generateCombinations5
(item :: acc)
(tail)
)
head
)
Note that without the type signature at the top and without List.concat, Elm compiler is returning this error. I spent quite a lot of time trying to understand where the problem was.
— INFINITE TYPE — — — — — — — — — — — — — — — — — — test.elmI am inferring a weird self-referential type for `generateCombinations5`89| generateCombinations5 acc list =
^^^^^^^^^^^^^^^^^^^^^
Here is my best effort at writing down the type. You will see ? and ∞ for parts of the type that repeat something already printed out infinitely.List ? -> List (List ?) -> ?Usually staring at the type is not so helpful in these cases, so definitely read the debugging hints for ideas on how to figure this out: <https://github.com/elm-lang/elm-compiler/blob/0.18.0/hints/infinite-type.md>
We are almost there. Looking at the output we note that the order of items is reversed:
[[“1”,”a”],[“2”,”a”],[“1”,”b”],[“2”,”b”]]This is because we are adding elements from the left of the list with the operator ::.
We can solve this with List.reverse before returning the list.
The final function is:
generateCombinations : List a -> List (List a) -> List (List a)
generateCombinations acc list =
case List.head list of
Nothing ->
[ List.reverse acc ] Just head ->
let
tail =
case List.tail list of
Just data ->
data Nothing ->
[]
in
List.concat
(List.map
(\item ->
generateCombinations
(item :: acc)
(tail)
)
head
)
Note that the branch where the List.tail is nothing and we return [] will never happen. List.tail return Nothing only when the list is empty. But an empty list is intercepted in the branch where we check if the List.head is Nothing.
Nevertheless Elm force us to return something so we return an empty list just to be consistent with the other branches.
Another note: there is an edge case where the input is [] and the output is [[]]. Probably this should be considered a special case but is beautiful to see how Elm is handling also this case without complaining.
The reason why there are two nested list is because the function goes directly to the first branch of the first case and that return [ acc ] that is [[]].
The case where the input instead is [[]] go through the third branch and return (List.concat []) that is equal to [].
Do you have any suggestion how this problem can be solved more efficiently? Let me know in the comments below.
Demo: https://lucamug.github.io/elm-tutorial-permutations-and-recursion/ (inspect the console for more insights)
Code: https://github.com/lucamug/elm-tutorial-permutations-and-recursion
This script is used in
