Lazily конкатенировать перечислимые списки

Question

Я хотел бы написать функцию, сходную с List.concat/1, которая перечислит списки и испускает объединенные списки как непрерывный поток.

Это будет выглядеть так:

iex> 1..3 |> Stream.map(&([&1])) |> Enum.to_list 
[[1], [2], [3]] 
iex> 1..3 |> Stream.map(&([&1])) |> MyStream.concat |> Enum.to_list 
[1, 2, 3] 

То, что я придумал до сих пор это:

defmodule MyStream do 
    def concat(lists) do 
    Enumerable.reduce(lists, [], fn(x, acc) -> acC++ x end) 
    end 
end 

Это дает правильный результат, но явно не лень.

Я безуспешно пробовал использовать Stream.Lazy, но на самом деле не понял его внутренней работы. Любое объяснение на Stream.Lazy было бы благодарно!

Answer 1

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

Вся идея Stream заключается в том, что вы можете создавать эти уменьшающие функции. Давайте карту в качестве примера:

def map(enumerable, f) do 
    Lazy[enumerable: enumerable, 
     fun: fn(f1) -> 
     fn(entry, acc) -> 
      f1.(f.(entry), acc) 
     end 
     end] 
end 

Вы получаете перечислимы и вы хотите отобразить над каждым элементом с функцией f. Ленивая версия получает фактическую функцию уменьшения f1 и возвращает новую функцию, которая принимает entry и acc (те же аргументы f1 будет получать), а затем вызывают f.(entry), эффективно отображая элемент перед вызовом f1 (функция уменьшения). Обратите внимание, как мы сопоставляем элементы по одному.

Плоская карта вариант это, вероятно, будет что-то вроде:

def flat_map(enumerable, f) do 
    Lazy[enumerable: enumerable, 
     fun: fn(f1) -> 
     fn(entry, acc) -> 
      Enumerable.reduce(f.(entry), acc, f1) 
     end 
     end] 
end 

Теперь, каждый раз, когда вы звоните f.(entry), вы получите список назад, и вы хотите перебрать каждый элемент этого нового списка, вместо итерации по списку в целом.

Я не пробовал код выше (и, возможно, я пропустил некоторые детали), но так работает Streams.

Answer 2

С the help of José Valim это был всего лишь небольшой шаг от его кода до того, что я искал. Вероятно, я задал этот вопрос довольно плохо, но то, что я действительно искал, было эквивалентно функции itertools.chain Python.

def chain(enumerable) do 
    Stream.Lazy[enumerable: enumerable, 
       fun: fn(f1) -> 
       fn(entry, acc) -> 
        Enumerable.reduce(entry, acc, f1) 
       end 
       end] 
end 

Это позволяет вам цепью потенциально бесконечных перечислимых объектов как потоков, так и списков.

iex> 1..1000000 |> Stream.map(&(1..(&1))) |> MyModule.chain |> Enum.take(20) 
[1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5]