ERLANG รายการ Fibonacci อนันต์โดยใช้ 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. งานที่น่าสนใจประเภทนี้คือการใช้ Sieve of Eratosthenes งานหลังไม่ใช่งานประดิษฐ์และจิตวิญญาณที่เกียจคร้านประเภทนี้ก็ดูหรูหราจริงๆ
person Lol4t0    schedule 21.04.2015
comment
ปัญหาคืองานบอกว่าให้ใช้ zipWith ฉันจะลองดูว่าแนวทางของคุณสามารถช่วยฉันได้อย่างไร ขอบคุณ. - person user3556115; 21.04.2015
comment
คุณช่วยอธิบายได้ไหมว่าเมื่อใดที่กรณี e(L)is_list และเมื่อใดที่ is_function เกิดขึ้น และเหตุใดเราจึงต้องสร้างความแตกต่างนี้ ฉันไม่เข้าใจมัน ฉันคิดว่ามันควรจะทำงานได้โดยไม่ต้องใช้ e() เพราะมีรายการ Lazy อยู่เสมอ ซึ่งสนุกเสมอ แต่ในบางกรณีก็ต้องแตกต่างออกไป ที่ไหน? - 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