Пустая голова в пользовательской реализации flatten - PullRequest
Новая
       8

Пустая голова в пользовательской реализации flatten

0 голосов
/ 03 апреля 2019

Таким образом, я попытался реализовать функцию выравнивания самостоятельно, используя несколько вложенных рекурсий.Проблема в том, что я получаю бесконечный цикл и при проверке фактической головы он пуст.Я только начал изучать эликсир, поэтому, пожалуйста, не будьте слишком резкими со мной. 

defmodule Test do
  def custom_flatten list do
    custom_flatten list, []
  end
  def custom_flatten [h|t], accumulator do
    custom_flatten [t], [custom_flatten(h) | accumulator]
  end
  def custom_flatten [], accumulator do
    IO.puts "Called empty list match #{accumulator}"
    Enum.reverse accumulator
  end

  def custom_flatten h, accumulator do
    [h|accumulator]
  end
end

Ответы [ 2 ]

0 голосов
/ 03 апреля 2019

Похоже, вы уже делаете это, но хорошая стратегия - посмотреть, что делает официальная реализация. Реализация Elixir просто вызывает к реализации Erlang . Вот реализация Erlang, переписанная в Elixir: 

def flatten([], acc), do: acc

def flatten([h | t], acc) when is_list(h) do
  flatten(h, flatten(t, acc))
end

def flatten([h | t], acc) do
  [h | flatten(t, acc)]
end

Кажется, есть несколько проблем с вашей реализацией.

  1. Завершающее условие - это когда первый аргумент является пустым списком. Но, как Бретт также упомянул, поскольку ваш рекурсивный вызов проходит [t], который является одноэлементным списком, содержащим хвостовой список, условие завершения никогда не происходит.
  2. Вам необходимо использовать охранники , чтобы определить, является ли следующий элемент (h) списком или нет, чтобы решить, нужен ли вам другой уровень рекурсии или можно ли использовать элемент напрямую.
  3. Похоже, ваше пользовательское поведение строит список в обратном порядке. В этом случае вам нужно использовать оператор конкатенации (++), потому что при обратном построении мы должны сгладить подсписки на лету, а затем объединить их с аккумулятором (в нереверсивной реализации Эрланга, хвост всегда сплющен первым, поэтому в этом нет необходимости). Мы также должны убедиться, что мы только полностью изменим окончательный результат, иначе внутренние списки также будут изменены во время рекурсивных вызовов: 
def flatten(list) do
  list
  |> flatten([])
  |> Enum.reverse()
end

def flatten([], acc), do: acc

def flatten([h | t], acc) when is_list(h) do
  flatten(t, flatten(h, []) ++ acc)
end

def flatten([h | t], acc) do
  flatten(t, [h | acc])
end
0 голосов
/ 03 апреля 2019

Эта строка вызывает у вас проблемы: 

    custom_flatten [t], [custom_flatten(h) | accumulator]

Если ваша функция началась с [h | t] = [1, 2, 3], t будет [2, 3], и вы передадите [[2, 3]] следующей функции.Эта функция будет видеть [h | t] = [[2, 3]], поэтому h будет [2, 3], а t будет [], что передаст [[]] следующей функции.Тогда ваша функция застрянет, повторяя [h | t] = [[]], где h это [], а t это [].

Так что на самом деле единственная проблема заключается в том, что вы не хотите обернуть t.Замена строки выше чем-то вроде этого должна решить проблему бесконечной рекурсии. 

    custom_flatten t, [custom_flatten(h) | accumulator]
...