haskell - 「結び方」の説明

Question

Haskell 関連のものを読んでいると、「結び目を結ぶ」という表現に出くわすことがあります。

それで、この概念の説明を理解するのに適切で、基本的で、簡単なものはありますか?

Answer 1

結び目を作ることは、循環データ構造の問題に対する解決策です。命令型言語では、最初に非循環構造を作成し、次に戻ってポインターを修正して循環性を追加することにより、循環構造を構築します。

要素 "0" と "1" を持つ 2 要素の循環リストが必要だとします。「1」ノードを作成してから「0」ノードを作成してそれを指すようにすると、「1」ノードを修正して「0」ノードを指すように戻すことができないため、構築するのは不可能に思えます。 . そのため、どちらかを作成する前に両方のノードが存在する必要がある、ニワトリが先か卵が先かという状況になります。

これを Haskell で行う方法を次に示します。次の値を検討してください。

alternates = x where
   x = 0 : y
   y = 1 : x

非遅延言語では、再帰が終了していないため、これは無限ループになります。しかし、Haskell では、遅延評価は正しいことを行います。つまり、2 要素の循環リストを生成します。

実際にどのように機能するかを確認するには、実行時に何が起こるかを考えてください。遅延評価の通常の「サンク」実装は、関数ポインターと関数に渡される引数を含むデータ構造として、評価されていない式を表します。これが評価されると、サンクは実際の値に置き換えられるため、将来の参照で関数を再度呼び出す必要はありません。

リストの最初の要素を取得すると、「x」は値 (0, &y) まで評価されます。ここで、「&y」ビットは「y」の値へのポインターです。'y' は評価されていないため、これは現在サンクです。リストの 2 番目の要素を取得すると、コンピューターは x からこのサンクへのリンクをたどって評価します。これは (1, &x) に評価されます。つまり、元の 'x' 値へのポインタです。これで、循環リストがメモリに格納されました。遅延評価メカニズムがバック ポインターを修正するため、プログラマーがバック ポインターを修正する必要はありません。

Answer 2

それはあなたが求めたものとはまったく異なり、Haskell とは直接関係ありませんが、Bruce McAdam の論文That About Wraps It Upは、このトピックをかなり幅広く深く掘り下げています。Bruce の基本的なアイデアは、Haskell、OCaml、およびその他の言語で自動的に行われる暗黙的な結び目結びの代わりに、WRAP と呼ばれる明示的な結び目結び演算子を使用することです。この論文には面白い例がたくさんあります。結び目を作ることに興味があるなら、そのプロセスをよりよく理解できると思います.