list - 再帰的に定義されたリストを理解する（zipWithに関するfibs）

Question

私はHaskellを学んでいて、次のコードに出くわしました。

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

それがどのように機能するかという点で、私は解析に少し問題があります。それはとてもきちんとしていて、これ以上何も必要ないことは理解していますが、Haskellが次のように書いたときにどのようにfibsを「埋める」ことができるかを理解したいと思います。

take 50 fibs

何か助けはありますか？

ありがとう！

Answer 1

内部でどのように機能するかについて少し説明します。まず、Haskellがその値にサンクと呼ばれるものを使用していることを理解する必要があります。サンクは基本的にまだ計算されていない値です-引数0の関数と考えてください。Haskellが望むときはいつでも、サンクを評価（または部分的に評価）して、実際の値に変えることができます。サンクを部分的にしか評価しない場合、結果の値にはさらに多くのサンクが含まれます。

たとえば、次の式について考えてみます。

(2 + 3, 4)

通常の言語では、この値はとしてメモリに保存されます(5, 4)が、Haskellでは。として保存され(<thunk 2 + 3>, 4)ます。そのタプルの2番目の要素を要求すると、2と3を足し合わせることなく、「4」と表示されます。そのタプルの最初の要素を要求した場合にのみ、サンクが評価され、5であることがわかります。

fibsの場合、再帰的であるため、少し複雑になりますが、同じアイデアを使用できます。fibs引数を取らないため、Haskellは発見されたリスト要素を永続的に保存します-これは重要です。

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

これは、Haskellの3つの式に関する現在の知識を視覚化するのに役立ちます：fibs、tail fibsおよびzipWith (+) fibs (tail fibs)。Haskellは次のことを知っていると仮定します。

fibs                         = 0 : 1 : <thunk1>
tail fibs                    = 1 : <thunk1>
zipWith (+) fibs (tail fibs) = <thunk1>

2行目は左にシフトした最初の行であり、3行目は最初の2行を合計したものであることに注意してください。

頼むtake 2 fibsとあなたは得るでしょう[0, 1]。Haskellはこれを見つけるために上記をさらに評価する必要はありません。

Ask forを要求するtake 3 fibsと、Haskellは0と1を取得し、サンクを部分的に評価する必要があることに気付きます。を完全に評価するにzipWith (+) fibs (tail fibs)は、最初の2行を合計する必要があります。これを完全に行うことはできませんが、最初の2行の合計を開始することはできます。

fibs                         = 0 : 1 : 1: <thunk2>
tail fibs                    = 1 : 1 : <thunk2>
zipWith (+) fibs (tail fibs) = 1 : <thunk2>

3行目に「1」を入力すると、3行すべてが同じサンクを共有しているため（書き込まれたポインターのように考えてください）、1行目と2行目にも自動的に表示されることに注意してください。また、評価が終了しなかったため、必要になった場合に備えて、リストの残りの部分を含む新しいサンクを作成しました。

ただし、実行されるため、必要ありませtake 3 fibsん[0, 1, 1]。しかし今、あなたが求めているとしましょうtake 50 fibs; Haskellはすでに0、1、1を覚えています。しかし、それは続ける必要があります。したがって、最初の2行を合計し続けます。

fibs                         = 0 : 1 : 1 : 2 : <thunk3>
tail fibs                    = 1 : 1 : 2 : <thunk3>
zipWith (+) fibs (tail fibs) = 1 : 2 : <thunk3>

..。

fibs                         = 0 : 1 : 1 : 2 : 3 : <thunk4>
tail fibs                    = 1 : 1 : 2 : 3 : <thunk4>
zipWith (+) fibs (tail fibs) = 1 : 2 : 3 : <thunk4>

以下同様に、3行目の48列に入力され、最初の50個の数値が計算されるまで続きます。Haskellは必要なだけ評価し、シーケンスの無限の「残り」をサンクオブジェクトとして残します。

後で要求した場合、Haskellはそれを再度評価しないことに注意してくださいtake 25 fibs-すでに計算したリストから最初の25個の数値を取得するだけです。

編集：混乱を避けるために、各サンクに一意の番号を追加しました。

Answer 2

しばらく前にこれについて記事を書きました。ここで見つけることができます。

そこで述べたように、PaulHudakの著書「TheHaskellSchool of Expression」の14.2章を読んでください。ここでは、フィボナッチの例を使用して、再帰ストリームについて説明しています。

注：シーケンスのテールは、最初の項目がないシーケンスです。

| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | フィボナッチ数列（fibs）|
| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |
| 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | フィボナッチ数列のテール（テールフィブ）|
| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |

2つの列を追加します。fibs（テールfibs）を追加して、fibシーケンスのテールのテールを取得します。

| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |
| 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | フィボナッチ数列の尾の尾|
| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |

add fibs（tail fibs）はzipWith（+）fibs（tail fibs）と書くことができます

これで、完全なフィボナッチ数列を取得するために、最初の2つのフィボナッチ数から始めて生成を素数化する必要があります。

1：1：zipWith（+）fibs（テールフィブ）

注：この再帰的定義は、先行評価を行う一般的な言語では機能しません。遅延評価を行うので、haskellで機能します。したがって、最初の4つのフィボナッチ数を要求する場合は、4つのフィボナッチ数を取り、haskellは必要に応じて十分な数のシーケンスのみを計算します。

Answer 3

非常に関連性のある例がここにありますが、完全には説明していませんが、おそらく何らかの助けになるでしょう。

実装の詳細は正確にはわかりませんが、以下の私の議論の行にあるはずだと思います。

これをほんの少しの塩で取ってください。これは実装上不正確かもしれませんが、理解を助けるためのものです。

Haskellは、それ自体が美しい概念である遅延評価として知られている、強制されない限り、何も評価しません。

それで、take 3 fibsHaskellがfibsリストをとして保存する0:1:another_listように求められたとtake 3仮定しましょう。fibs = 0:1:x:another_list(tail fibs) = 1:x:another_list0 : 1 : zipWith (+) fibs (tail fibs)0 : 1 : (0+1) : (1+x) : (x+head another_list) ...

パターンマッチングにより、Haskellはそれを知っていx = 0 + 1ます0:1:1。

誰かが適切な実装の詳細を知っていれば、私は本当に興味があります。ただし、遅延評価手法はかなり複雑になる可能性があることは理解できます。

これが理解に役立つことを願っています。

再度必須の免責事項：これをほんの少しの塩で服用してください。これは実装上不正確かもしれませんが、理解を助けるためのものです。

Answer 4

の定義を見てみましょうzipWith zipWith f (x:xs) (y:ys) = f x y : zipWith xs ys

私たちのfibsは： fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

take 3 fibsの定義を置き換えるzipWithためにxs = tail (x:xs)、 0 : 1 : (0+1) : zipWith (+) (tail fibs) (tail (tail fibs))

take 4 fibsもう一度代用すると 、 0 : 1 : 1 : (1+1) : zipWith (+) (tail (tail fibs)) (tail (tail (tail fibs)))

等々。