# Recursion question

A question on recursion, Look at the recursive function below that takes a list of lists as input.

during the recursion the subsequent input will get reduced to [ [] | tail_values ] or [ head_values | [] ] - What I observed is that the VM never calling the method defined for input matching [ head_values | [] ]

What is the best way to solve this scenario ? I have pasted a working and non working input below the method definition.

``````defmodule Transpose do
def transpose(input) do
_transpose(input)
end
defp _transpose([]) do
IO.puts("ONE!!!")
[]
end
defp _transpose([[] | []]) do
IO.puts("TWO!!!")
[]
end
defp _transpose([[] | tail]) do
IO.puts("THREE!!!")
[tail]
end
IO.puts("FOUR!!!")
end
defp _transpose(input) do
IO.inspect(input)
[Enum.map(input, &hd/1) | _transpose(Enum.map(input, &tl/1))]
end
end
IO.puts("**********method call below worked as expected*************")
# This function call worked fine - reached function that prints "THREE!!!"
IO.inspect Transpose.transpose([["A", "B"], ["C", "D", "E"]])

IO.puts("\n\n**********Method call below Did not work as expected*************")
# This function Failed - I was expectign this to reach the function that prints "FOUR!!!"
IO.inspect Transpose.transpose([["A", "B", "C"], ["D", "E"]])
``````

`[ foo | [] ]` does not do what you expect it to do. It splats the tail. Test `[ 1 | [ 2, 3 ] ]` in `iex`.

`[ foo | [] ]` is hence exactly equivalent to `[ foo ]`.

You need a comma everywhere instead of bar.

4 Likes

thank you! that worked.

replacing “|” with comma introduced another problem. Now I can’t have more than two elements in the list after adding comma.

``````#this will fail unless another function is added like this
#defp _transpose([[],[],[]]), do: []  and so on .... for every increment.
IO.inspect Transpose.transpose([["A","B"], ["C","D"], ["E","F"]])
``````

You probably want to match on `[head | tail]` and recurse on them.

``````iex(1)> [head | tail] = [["A","B"], ["C","D"], ["E","F"]]
[["A", "B"], ["C", "D"], ["E", "F"]]
["A", "B"]
iex(3)> tail
[["C", "D"], ["E", "F"]]
``````
3 Likes

Ah, this is supposed to transpose an array. Here you go then:

``````defmodule T do
@test [~w[A B], ~w[C D], ~w[E F]]

def transpose(input, acc \\ [])

def transpose([], acc), do: Enum.reverse(acc)
def transpose(list, acc) when is_list(list) do
Enum.reduce(list, {[], []}, fn
end)
end
def test do
transpose(@test)
end
end

T.test()
``````
2 Likes

Any thoughts on this solution ? It works for all my test scenarios

``````  defp _transpose([]), do: []
defp _transpose([[] | tail]), do: tail

defp _transpose(list) do
tails = Enum.filter(Enum.map(list, &tl/1), &(&1 !=[]))
[Enum.map(list, &hd/1) | _transpose(tails)]
end
#test data
#[[]]
#[["A"]]
#[["A", "B", "C"]]
#[["A", "B", "C"], ["D", "E"]]
#[["A", "B"], ["C", "D", "E"]]
#[["A", "B", "C"], ["D", "E", "F"], ["G", "H", "I"]]

# found this solution in stackoverflow. I modified the code to take care of empty tails
#ref : https://stackoverflow.com/questions/23705074/is-there-a-transpose-function-in-elixir
``````

This is exactly the same as matching a single element list: `[tail]`.

Nope…

`[tail]` would match any list with exactly one element and bind that elements value to `tail`, `[[] | tail]` though will match any list which has at least one element. This element has to match the empty list. The remaining elements are bound to `tail`.

2 Likes

Oops. My mistake, didn’t know that. Thanks.

You probably confused it with `[head | []]`, which in fact is equivalent to `[head]`.

2 Likes