ERLANG, бесконечный список Фибоначчи с использованием zipWith

У меня есть задача с бесконечными списками.

Я должен написать zipWith/3 для бесконечных списков - готово

Я должен использовать этот zipWith/3 для создания бесконечного списка чисел фибоначчи с fib/0 - проблема

Мне нужно написать fibs(N), взяв первые N элементов из fib() - готово

Это то, что у меня есть до сих пор:

-module(zipWith).
-export([take/2, zipWith/3, fib/0]).

take(0, _)         -> [];
take(N, [H|LazyT]) -> [H | take(N-1, LazyT())].

zipWith(F, [H1|L1], [H2|L2]) -> [F(H1, H2) | fun() -> zipWith(F, L1(),   L2()) end].

fib() -> ...
fib(L) -> zipWith(fun(X,Y) -> X + Y end, L(), tl(L())).

fibs(N) -> take(N, fib()).

Я знаю, что fib/1 должна выглядеть так (я почти уверен — поправьте меня, если я ошибаюсь). Берем сам список и список без головы. Таким образом, в случае [0,1,...] zipWith(add,[0,1,...],[1,...]) приводит к добавлению двух последних чисел. Но что бы я ни пробовал в качестве начала этого fib()->..., это приводит к ошибкам. Я хочу выразить это как-то так: fib() -> fib([[0,1] ++ fun() -> ... end]...)

Я как-то хотел начать fib/1 с [0,1,fun()...], но не понимаю, как начать список.

Заранее спасибо за совет


list infinite erlang fibonacci
person user3556115    schedule 21.04.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Я не понимаю, как вы собираетесь использовать здесь zipwith. Однако я придумал следующее решение:

map(_, []) -> [];
map(F, [H | T]) -> [F(H) | fun() -> map(F, T()) end].

fib1(X, Y) -> [{X, Y} | fun() -> fib1(Y, X+Y) end].

fib() -> map(fun({_X, Y}) -> Y end, fib1(1,1)).

Идея состоит в том, чтобы построить некоторый элемент, а затем передать контекст для следующего числа.

На самом деле я не думаю, что этот подход реализует настоящую лень, поскольку вам нужно переоценивать все значения каждый раз, когда вы просматриваете список.

ОБНОВИТЬ

Если вы хотите реализовать это через zipWith, вы можете поиграться с тем, что каждый следующий элемент последовательности формируется как сумма предыдущего и текущего.

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

Вам понадобится несколько первых элементов для начальной загрузки. Вы просто применяете знание первых двух элементов

введите здесь описание изображения

Как видите, к моменту вычисления 3-го элемента вы должны знать сначала 2, при вычислении 4-го элемента вам нужно знать 2-й и 3-й, но вы уже вычислили 3-й.

%% this eveluates the lazy list and just returns normal one
e(L) when is_list(L) -> L; 
e(LazyL) when is_function(LazyL, 0) -> LazyL().

take(0, _)         -> [];
take(N, [H|LazyT]) -> [H | take(N-1, e(LazyT))].

drop(0, T)         -> e(T);
drop(N, [_|LazyT]) -> drop(N-1, e(LazyT)).

zipWith(F, [H1|L1], [H2|L2]) -> [F(H1, H2) | fun() -> zipWith(F, e(L1),   e(L2)) end].

fib() -> [1, 1 | fun() -> zipWith(fun(X,Y) -> X + Y end, fib(), drop(1, fib())) end ].

fibs(N) -> take(N, fib()).

Последние заметки

  1. Никогда не пишите так в реальной жизни.
  2. Более интересной задачей такого рода является реализация Решета Эратосфена. Последняя задача не так искусственна, и ленивая душа такого рода действительно элегантна для нее.
person Lol4t0    schedule 21.04.2015
comment
Проблема в том, что в задании сказано использовать zipWith. Я примерю и посмотрю, чем ваш подход может мне помочь. Спасибо. - person user3556115; 21.04.2015
comment
Не могли бы вы объяснить, когда случаются случаи e(L)is_list и is_function, и почему мы должны делать это различие? Я этого не понимаю. Я думал, что это должно работать без e(), потому что всегда есть ленивый список, который всегда забавен, но в некоторых случаях он должен быть другим. Где? - person user3556115; 22.04.2015
comment
@ user3556115, в самом начале fibs == [1,1 | fun()], так что у нас здесь не очень ленивый список. Когда вы сопоставляете шаблон [1,1 | fun()] с [H | L], вы получаете H==1 и L == [1 | fun()] - person Lol4t0; 22.04.2015
comment
А L == [1 | fun()] оценивает как список? - person user3556115; 22.04.2015
comment
e([1 | fun()]) переходит к делу when is_list - person Lol4t0; 22.04.2015
comment
Спасибо, теперь я понял. - person user3556115; 23.04.2015