Recursion question

Questions / Help
#1

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
  defp _transpose([head | []]) do
    IO.puts("FOUR!!!")
    [head]
  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"]])
#2

[ 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
#3

thank you! that worked.

#4

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"]])
#5

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"]]
iex(2)> head
["A", "B"]
iex(3)> tail
[["C", "D"], ["E", "F"]]
3 Likes
#6

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
    {heads, tails} =
      Enum.reduce(list, {[], []}, fn
        [h], {heads, tails} -> {[h | heads], tails}
        [h|t], {heads, tails} -> {[h | heads], [t | tails]}
      end)
    [Enum.reverse(heads) | transpose(tails)]
  end
  def test do
    transpose(@test)
  end
end

T.test()
2 Likes
#8

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
#9

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

#10

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
#11

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

#12

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

2 Likes