機能リンクリスト

クロージャを通してリンクリストの実装を考えてください。

リストを示すために、Haskell： x:xsに似た表記を使用します。ここで、 xはリストのhead （ head ）、 xsは継続（ tail ）です。



実装言語としてJavaScriptを選択しました。

リストを作成する

リンクリストを使用するには、次の基本的なプリミティブが必要ですprepend空のリスト、 prepend （ cons ）-リストの先頭に挿入する関数、 headおよびtail

2つのアイテムのリストの作成は次のとおりです。

 prepend('a', prepend('b', nil)) // 'a' -> 'b' -> nil 

prepend関数の実装：

 function prepend(x, xs) { return function (select) { return select(x, xs) } } 

自由変数（ x:xs ）にアクセスするには、 select関数が必要です。

headとtailの実装は、目的のselect値を使用してリスト関数を呼び出すことに要約されます。

 function select_head(x, xs) { return x } function select_tail(x, xs) { return xs } function head(a) { return a(select_head) } function tail(a) { return a(select_tail) } 

空のリスト（ nil ）を実装します：

 function nil() { return nil } 

したがって、 head(nil) === tail(nil) === nil 。

使用例

リストの作成とトラバースを説明する簡単なプログラム：

 var a = prepend('a', prepend('b', nil)) // 'a' -> 'b' -> nil head(a) // => 'a' head(tail(a)) // => 'b' head(tail(tail(a))) // => nil while (a !== nil) { console.log(head(a)) a = tail(a) } 

高階関数

結果のデータ構造に対して、たとえばmapような高階関数を実装できます。

 function map(fn, a) { if (a === nil) return nil return prepend(fn(head(a)), map(fn, tail(a))) } 

これにより、機能的なスタイルでリストを操作できます。

 var a = prepend(1, prepend(2, prepend(3, nil))) // 1 -> 2 -> 3 -> nil function power_of_2(x) { return 1 << x } var b = map(power_of_2, a) // 2 -> 4 -> 8 -> nil 

その他の関連機能（ filter 、 reduce ）は、宿題として読者に提供されます。

そのようなこと™

記事を書くときに、単一の配列が破損していませんでした。

パンからトロリーの絵を予想する：これは確かに適用された解決策ではありません。 さらに、そのようなコミットのために仕事をしていると、彼らは簡単かつ無制限に手を引きちぎることができます。 この知識で次に何をするかはあなた次第です。

Github： github.com/mvasilkov/functional-js