ERLANG, daftar Fibonacci tak terbatas menggunakan zipWith

Saya punya tugas dengan daftar tak terbatas.

Saya harus menulis zipWith/3 untuk daftar tak terbatas - selesai

Saya harus menggunakan zipWith/3 ini untuk membuat daftar angka fibonacci yang tak terbatas dengan fib/0 - masalah

Saya harus menulis fibs(N) dengan mengambil N elemen pertama dari fib() - selesai

Inilah yang saya miliki sejauh ini:

-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()).

Saya tahu fib/1 akan terlihat seperti ini (saya cukup yakin - koreksi saya, jika saya salah). Mengambil daftar itu sendiri dan daftar tanpa kepala. Jadi dalam kasus [0,1,...] zipWith(add,[0,1,...],[1,...]) menghasilkan penjumlahan dua angka terakhir. Tapi apa pun yang saya coba sebagai awal dari fib()->... ini menghasilkan kesalahan. Saya ingin mengungkapkannya seperti ini: fib() -> fib([[0,1] ++ fun() -> ... end]...)

Saya entah bagaimana ingin memulai fib/1 dengan [0,1,fun()...] tetapi tidak mengerti bagaimana cara memulai daftarnya.

Terima kasih sebelumnya atas sarannya


list infinite erlang fibonacci
person user3556115    schedule 21.04.2015    source sumber

Jawaban (1)


arrow_upward
2
arrow_downward

Saya tidak mengerti bagaimana Anda akan menggunakan zipwith di sini. Namun, saya menemukan solusi berikut:

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)).

Idenya adalah untuk membangun beberapa elemen dan kemudian meneruskan konteks ke nomor berikutnya.

Sebenarnya menurut saya pendekatan ini tidak menerapkan kemalasan yang sebenarnya karena Anda harus mengevaluasi ulang semua nilai setiap kali Anda memeriksa daftarnya.

MEMPERBARUI

Jika Anda ingin menerapkan ini melalui zipWith, Anda dapat memanfaatkan fakta bahwa setiap elemen urutan berikutnya dibentuk sebagai penjumlahan dari elemen sebelumnya dan elemen saat ini.

Jadi Anda dapat mengambil daftar elemen, dan daftar elemen digeser satu, dan membentuk setiap elemen berikutnya sebagai jumlah elemen dalam daftar tersebut.

Anda memerlukan beberapa elemen pertama untuk melakukan bootstrap. Anda tinggal menerapkan pengetahuan dua elemen pertama

masukkan deskripsi gambar di sini

Seperti yang Anda lihat, pada saat menghitung elemen ke-3 Anda harus mengetahui elemen ke-2 terlebih dahulu, saat menghitung elemen ke-4, Anda harus mengetahui elemen ke-2 dan ke-3, tetapi Anda sudah menghitung elemen ke-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()).

Catatan terakhir

  1. Jangan pernah menulis seperti ini dalam kehidupan nyata.
  2. Tugas yang lebih menarik dari jenis ini adalah menerapkan Saringan Eratosthenes. Tugas terakhir ini tidak terlalu artifisial dan jiwa malas semacam ini benar-benar elegan untuk itu
person Lol4t0    schedule 21.04.2015
comment
Masalahnya adalah, tugas tersebut mengatakan untuk menggunakan zipWith. Saya akan mencoba dan melihat, pendekatan Anda dapat membantu saya. Terima kasih. - person user3556115; 21.04.2015
comment
Bisakah Anda menjelaskan kapan kasus e(L)is_list dan kapan is_function terjadi dan mengapa kita harus membuat perbedaan ini? Saya tidak memahaminya. Saya pikir ini akan berfungsi tanpa e() karena selalu ada daftar Malas, yang selalu menyenangkan tetapi dalam beberapa kasus harus berbeda. Di mana? - person user3556115; 22.04.2015
comment
@ user3556115, di awal fibs == [1,1 | fun()], jadi kami di sini memiliki daftar yang tidak terlalu malas. Saat pola Anda cocok [1,1 | fun()] dengan [H | L], Anda mendapatkan H==1 dan L == [1 | fun()] - person Lol4t0; 22.04.2015
comment
Dan L == [1 | fun()] mengevaluasi sebagai daftar? - person user3556115; 22.04.2015
comment
e([1 | fun()]) pergi ke kasus when is_list - person Lol4t0; 22.04.2015
comment
Terima kasih, sekarang saya mengerti. - person user3556115; 23.04.2015