非リストに表示されますか？

Question

最近の課題では、リスト以外のタイプの折り畳み関数を定義するように求められています。私はまだこのコンセプトの周りを頭で覆うことはできません。これまでのところ、私はfoldがlistの後続の要素に対して実行していると理解しています。 fold on Treeは、ルートのサブツリーに対して再帰的にいくつかの関数を適用できるので、直感的に理解できます。

しかし、のようなデータ型に：（それは私には思えるよう）の倍のアクションを実行するために

Maybe a :: Nothing | Just a 

何listはありません。

ここでは基本的な概念を理解する上で問題があると確信しています。

Answer 1

Foldableは非常に混乱しやすいクラスです。正直なところ、多くの法律がないため、ほぼすべての種類の異なるFoldableインスタンスをかなり書くことが可能です。幸いなことに、同じタイプのがある場合はTraversableインスタンスに基づいて、Foldableインスタンスが純粋に機械的な方法で何をすべきかを理解することができます。私たちは、

class (Functor t, Foldable t) => Traversable t where 
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b) 

Traversableを持って

は、いくつかの異なる法律がありますが、それは最も重要なものはtraverse Identity = Identityで判明します。のは、これがMaybeに適用される方法を見てみましょう：

traverse :: Applicative f => (a -> f b) -> Maybe a -> f (Maybe b) 
traverse g Nothing = _none 
traverse g (Just a) = _some 

は今最初のケースでは、あなたはf (Maybe b)を生成する必要がある、とあなたが持っているすべてがg :: a -> f bです。 fの値がなく、aの値がないため、生成できるのはpure Nothingです。

2番目のケースでは、f (Maybe b)を生成し、g :: a -> f bとaが必要です。だから興味深いのは、gをaに適用してg a :: f bにすることです。これで、この値を捨ててNothingを返すか、Justにまとめて返すことができます。

同一性法により、traverse Identity (Just a) = Identity (Just a)。あなたはNothingを返すことができません。 のみ法的定義はMaybeためTraversableインスタンスが完全にTraversable法律やparametricityによって決定され

traverse _ Nothing = pure Nothing 
traverse g (Just a) = Just <$> g a 

です。これはMaybeに適用されるとして、

foldMapDefault :: (Traversable t, Monoid m) 
       => (a -> m) -> t a -> m 
foldMapDefault f xs = 
    getConst (traverse (Const . f) xs) 

私たちの定義を拡大

foldMapDefault f Nothing = 
    getConst (traverse (Const . f) Nothing) 
foldMapDefault f (Just a) = 
    getConst (traverse (Const . f) (Just a)) 

、pureと<$>の定義によって

foldMapDefault f Nothing = getConst (pure Nothing) 
foldMapDefault f (Just a) = getConst (Just <$> (Const (f a))) 

：

今ではtraverseを使用して折り畳むことが可能です0の場合は、これらのコンストラクタをアンラップ

foldMapDefault f Nothing = getConst (Const mempty) 
foldMapDefault f (Just a) = getConst (Const (f a)) 

、

foldMapDefault f Nothing = mempty 
foldMapDefault f (Just a) = f a 

されており、これはfoldMapがMaybeに定義されている正確にどのように確かにあります。

Answer 2

"基本的なコンセプト"として、これはかなり心地よい曲ですので、あまり気にしないでください。

それはさておき倍がリストに何をするかについてのあなたの直感を設定し、タイプ特定の折りたたみ機能（のはfoldrを使ってみましょうが）Maybeに適用された場合持っているべきかを考えるのに役立つことがあります。

foldr :: (a -> b -> b) -> b -> List a -> b 

もちろん、多分持っている必要がありますタイプに対応倍：

foldrMaybe :: (a -> b -> b) -> b -> Maybe a -> b 

は何の定義について考え[a]の代わりにList aを書くことは、それをより明確にするために、リスト上のfoldrの標準タイプがありますタイプについて他に何も知らずにすべてaとbに定義する必要があることを考えれば、これは可能性があります。さらにヒントとして、類似のタイプのData.Maybeに既に定義されている関数があるかどうかを確認してください。