最も簡単で、最も専門用語のない英語、「フォールドの普遍的な財産」で説明してください。

Question

私は「現実世界のハスケル」を通して働いています。 「フォールドの普遍性と表現力に関するチュートリアル」. 。 「折り畳み」が「普遍的」であると主張します。私は彼の「ユニバーサル」の定義に取り組んでおり、すでに時間を投資している人々からそれを消化している人々から聞きたいです。 最も簡単で、最も専門用語のない英語、「フォールドの普遍的な財産」で説明してください。 この「普遍的な財産」とは何ですか、そしてなぜそれが重要なのですか？

ありがとう。

Answer 1

（jargonモードオフ:-)

ユニバーサルプロパティは、2つの表現が等しいことを証明する方法にすぎません。 （それが専門用語の「証明原則」の意味です。）ユニバーサルプロパティは、これらの2つの方程式を証明できれば言うと言います

g []     = v
g (x:xs) = f x (g xs)

次に、追加の方程式を締めくくることができます

g = fold f v

逆も真実ですが、それはの定義を拡大するだけで示すのは些細なことです fold. 。ユニバーサルプロパティは、はるかに深いプロパティです（これは、なぜそれが真実であるのかはあまり明白ではないと言っています。）

これを行うことが興味深い理由は、誘導によって証明を避けることができるためです。これはほとんど常に避ける価値があります。

Answer 2

論文は2つのプロパティを定義します。

g   []     = v
g (x : xs) = f x (g xs)

そして、それを述べています fold だけではありません a これらのプロパティを満たす機能ですが、です それだけ これらのプロパティを満たす関数。その点でユニークであるということは、論文が使用している意味でそれを「普遍的」にするものです。

Answer 3

foldが持っているプロパティは、それが適切なパラメーターを提供する場合、他のすべてのリスト回収関数に相当するリスト再送信機能であるということです。

このプロパティは、リスト内の項目に適用される機能をパラメーターとして受け入れるためです。

たとえば、単純な合計関数を書いた場合：

sum []          = 0
sum (head:tail) = head + (sum tail)

その後、アイテムを組み合わせるために使用する（+）演算子を渡すことにより、実際にそれを折り畳み関数として書くことができます。

sum list = foldl (+) 0 list

したがって、リストを介して簡単かつ再帰的に作用する関数は、折り畳み関数として書き換えることができます。その同等性は、それが保持するプロパティです。私は彼が財産を普遍的に呼ぶと信じています。 全て 例外なく、これらの線形リストに再回復的なアルゴリズム。

そして、彼が説明するように、このプロパティが非常に有用である理由は、これらの他のアルゴリズムをすべて折り畳むことと実際に同等であることを示すことができるからです。

私は個人的に折りたたみ関数を理解しにくいと感じたので、時々私は自分のものを使用しました。

-- forall - A kind of for next loop
-- list is list of things to loop through
-- f is function to perform on each thing
-- c is the function which combines the results of f
-- e is the thing to combine to when the end of the list is reached
forall :: [a] -> (a->b) -> (b->b->b) -> b -> b
forall [] f c e = e
forall (x:xs) f c e = c (f x) (forall xs f c e)

（これは実際には、リスト内の各アイテムに関数fを適用する特徴があるため、実際にはFoldlよりもわずかに強力です。）

まあ、私の機能について何も証明しませんでした。しかし、それは問題ではありません。なぜなら、私の関数が実際には折り畳み関数であることを示すことができるからです。

forall l f c e = foldl c e (map fn l)

したがって、フォールドについて証明されたすべてのことも、私のforall機能と、私のプログラム全体でそのすべての使用に当てはまることが証明されています。 （注意する必要はありません。

Answer 4

ウィキペディアで「ユニバーサルプロパティ」で新しい（私にとって）新しいエントリーを見つけました。この質問に大量の光を当てます。 これがリンクです： それから、私は（テナリー）次のことを結論付けます。

1. リストを歩き、途中で計算し、リストから1つの最終的な値を作成する100の異なる方法を考えることができますが、それらの100の方法はすべてです。 同型 （つまり、最終的には同じです）。リストを1つの値に削減する方法は本当に1つしかありません。それは折りたたまれています。
2. Foldは、リストを単一の値に削減する方法の「最も効率的なソリューション」でもあります。または、あなたが言うかもしれません、最も「因数分解された」または最も単純化されたソリューション。

一緒に、これらの2つのポイントは「ユニバーサルプロパティ」という用語の意味を捉えています。

Answer 5

カテゴリーの観点から普遍的な特性を説明するシリーズの以前の投稿を読むことなく従うことは少し難しいかもしれませんが、この投稿は、MapとFilterの普遍的な特性の詳細なカテゴリの説明を提供します。

http://jeremykun.com/2013/09/30/the-universal-poperties-of-mapfold-filter/

私はまだそれを書いていませんが、フォローアップはこれを一般化します（そして、より抽象的ではありますが、より抽象的ではありますが、一般的なデータ構造の「折りたたみのような」操作に対してより簡単になります）。

普遍的なプロパティとは何かについては、この投稿を参照してください。 http://jeremykun.com/2013/05/24/universal-properties/

そして、ここでシリーズのすべての投稿へのリンクについては： http://jeremykun.com/main-content/

実際には、現在受け入れられている答えは、ユニバーサルプロパティが折り畳みについて言っていることを理解する最も簡単な方法です。上記にリンクされている記事は、問題の論文にはないカテゴリ理論を介して、より詳細な技術的説明を提供します。しかし、私は、普遍的な財産は専門用語のない声明よりもはるかに深い財産であるという認められた答えで声明に同意しません。 foldの普遍的な特性はまったく同じ声明であり、カテゴリ理論を使用して物事を分析する性質に従って、初期および最終オブジェクトの言語に囲まれたばかりです。この分析は、その自然な一般化のために正確に貴重です。