折りたたまれていないフォールドのプロパティは何ですか？

Question

foldlのとfolrはFPやHaskellのための2つの非常に重要な機能がありますが、私はunsided倍についてはあまり聞いたことがない：

ある

fold f [a,b,c,d] = (f (f a b) (f c d)) 

、バイナリ連想機能で動作倍（アプリケーションのように順序関係ない）。正しくリコールすれば、これは並列化が可能なデータベースでは非常に一般的です。それで、それについては、私は尋ねます：

1. foldrのようなユニバーサルですか？
2. foldrのように、重要な機能をすべて使用して定義できますか？
3. foldr/buildやunfoldr/destroyのような融合ルールがありますか？
4. なぜそれほど言及されていませんか？
5. 言及する価値のある検討事項はありますか？

Answer 1

あなたが探している機能はData.Foldable.foldMapです。

foldMap :: Data.Monoid.Monoid m => (a -> m) -> t a -> m 

この関数はfoldrと同形です。証明として、foldMapまたはfoldrのいずれかがFoldableの最小限の完全な定義であることに注意してください。つまり、それぞれが別のものとして記述することができます。最初の2つの質問に肯定的に答えます。

具体的にはfoldMapの融合ルールはわかりませんが、私は存在する可能性が高いと確信しています。最低限、foldr融合ルールはある程度適用されるべきです。

なぜそれがほとんど言及されているのかわかりません。

言及する価値のある考慮事項の1つは、リストに関する限り、この折り目を常にフルに活用できるわけではありません。リストはコンスセルから構成されているので、ツリーフォールドを実行すると、リストの半分をトラバースし、次に各半分を再帰し、再び半分をトラバースすることを意味します。これは、foldlまたはfoldrと比較して多くの余分なトラバーサルです。非リスト構造の場合、ツリーフォールドはより多くの場合となり、リストの場合でもこれを利用することができます。最近、このような仕事の1つについて素晴らしいblogがありました。

Answer 2

これは、しばしばツリーの縮小と考えられ、分割と征服の削減を実現するため、並列計算では重要です。

最初に、結合機能が非結合である場合、明らかにfoldl、foldr、および「非分割の折りたたみ」の間に大きな違いがあります。したがって、結合操作と結合すると仮定しましょう。直ちに、すべての折り目はMonoidで表すことができます。 foldrを使用して、デフォルトで定義され、より良いfoldMap :: Monoid m => (a -> m) -> [a] -> mで表される

foldlm :: Monoid m => [m] -> m 
foldlm = foldl mappend mempty 

foldrm :: Monoid m => [m] -> m 
foldrm = foldr mappend mempty 

usfoldm :: Monoid m => [m] -> m 
usfoldm = foldTree mappend mempty . buildTree 

。

、エレメント Monoid Sが結合される方法を制御するツリー状の配列タイプに定義された Monoid所与のツリー状unsidedフォールディングを生成するために、最終的な抽出工程を、与えられた場合、十分である

foldMap f = foldr (mappend . f) mempty 

。それは根本的なことができますので、

data Tree a 
singleton :: a -> Tree a 
instance Monoid (Tree a) where ... 
foldTree :: Monoid a => Tree a -> a 

foldTree . foldMap singleton :: Monoid a => [a] -> a 

最後に、我々は我々がfoldrからfoldMapを得ることができますが、我々はまた、一般的にfoldMap

newtype Endo a = Endo { appEndo :: a -> a } 

instance Monoid (Endo a) where 
    mempty = id 
    mappend (Endo f) (Endo g) = Endo (f . g) 

foldr f z as = appEndo (foldMap (Endo . f) as) z 

からfoldrを得ることができることを見てきた、foldMapは、より原始的と考えられていますMonoidは、好ましい折り畳み方法を選択します。つまり、データ型ごとに効率的または並列のフォールディングを自由に作成することができますが、適切に行うことはまだ難しいでしょう。

foldMap抽象化は、通常、インスタンスメソッドとしてFoldableというものがありますが、これは非常に一般的ですが、より新しいHaskellのtypeclassです。 Foldableが

toList :: Foldable f => f a -> [a] 

はまた、私たちは普遍MonoidあるfoldMap[a]としてのMonoidアル自然を見ることができますされ、存在していることを除いて非常にいくつかの意味の法律を持っているので、またその実用性にもかかわらず、少し愚かであると考えられていた我々 foldrで回復できます。

融合規則をさらに詳しく調べるには、Gershom BazermanのBuilding up to a Point via Adjunctionsのように、提案されているデュアルタイプクラスBuildableを読むことが重要です。

そして最後に、人気のように、私は必要があれば、それはより効率的Monoid折り目が可能になりますが、それはfoldl、おそらくその相対的な不分明に果たしているfoldr両方よりも間違いなく新しいだから、それは間違いなく、これらの日Foldableをインスタンス化する好ましい方法だと思います。