CODEWITHSUNDEEP
listrecursionelixir
Sightvision
Sightvision

Reputation: 45

Reversing list with recursion in Elixir

My task is to take a list and then reverse it recursively, using one parameter. What I have arrived at is this solution:

def reverse(l) do
      [head | tail] = l
      cond do

          tail == [] ->
             head

          true ->
             [reverse(tail) , head]

      end 
end

I have attempted having a | instead of a comma in the true statement, but to no avail. The problem with this solution is that it prints out the following when inputting [1,2,3,4,5]:

[[[[5, 4], 3], 2], 1]

It doesn't actually add the head part to the list aside from when returning the final value of the list. (in this case 5)

Upvotes: 3

Views: 1086

Answers (3)

prnvbn
prnvbn

Reputation: 1018

I personally like to use pattern matching in this way instead of the cond as I feel like it makes it easier to reason about it.

defmodule M do

  def reverse(list) do
    reverse_helper(list, [])
  end

  defp reverse_helper([], reversed) do
    reversed
  end

  defp reverse_helper([h|t], reversed) do
    reverse_helper(t, [h|reversed])
  end
end

Upvotes: 2

S4eed3sm
S4eed3sm

Reputation: 1478

For fixing your solution you could use List.flatten:

  @spec reverse(list()) :: list()
  def reverse([]), do: []

  def reverse([head | tail]) do
    cond do
      tail == [] ->
        [head]

      true ->
        List.flatten(reverse(tail) ++ head)
    end
  end

Flatten for example takes [1, [2]] and returns [1, 2]. But this solution is not efficient. You could use @aleksei-matiushkin solutions or you can use foldl which is tail recursive:

  @spec reverse_fold(list()) :: list()
  def reverse_fold(l) do
    List.foldl(l, [], fn x, acc ->
      [x | acc]
    end)
  end

Upvotes: 0

Aleksei Matiushkin
Aleksei Matiushkin

Reputation: 121000

One cannot expect implicit flattening for [list, elem] as you do in [reverse(tail), head].

The former is a list, and this is why you receive nested lists back.

One way to approach the problem would be to indeed add lists one to another with reverse(tail) ++ [head]. It’s not efficient though because it would produce new lists on each step and is not tail-recursive.

The proper solution would be to introduce an accumulator to collect the processed items

def reverse(input, acc \\ [])
def reverse([], acc), do: acc
def reverse([head | tail], acc) do
  reverse(tail, [head | acc])
end 

reverse([1, 2, 3])
#⇒ [3, 2, 1]

Upvotes: 8

Related Questions