60

インスタンスはある種のFoldableコンテナである可能性が高く、Functor同様に である可能性もあります。確かに、これは言う

型Foldableはコンテナでもあります (クラスは技術的には を必要としませんがFunctor、興味深いFoldableのはすべてFunctorです)。

Foldableでは、自然に aFunctorまたは aではないa の例はありTraversableますか? (おそらく Haskell の wiki ページは見逃していました :-) )

4

3 に答える 3

61

完全にパラメトリックな例を次に示します。

data Weird a = Weird a (a -> a)

instance Foldable Weird where
  foldMap f (Weird a b) = f $ b a

Weird負の位置で発生するFunctorため、ではありません。a

于 2011-12-02T16:41:41.363 に答える
54

簡単な例を次に示しますData.Set.Set。自分で見て。

foldこの理由は、 に定義された特殊化された関数とmap関数の型を調べれば明らかですSet。

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

map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

データ構造は内部で二分探索木に依存しているOrdため、要素には制約が必要です。Functorインスタンスはあらゆる要素タイプを許可する必要があるため、残念ながらそれは実行できません。

一方、折り畳みは常にツリーを破棄して集計値を生成するため、折り畳みの中間結果をソートする必要はありません。フォールドが実際に新しいSetを構築している場合でも、制約を満たす責任Ordは、フォールド自体ではなく、フォールドに渡される累積関数にあります。

同じことが、完全にパラメトリックではないコンテナー タイプにも適用される可能性があります。の有用性を考えるとData.Set、これにより、「興味深い」 について引用した発言がFoldable少し疑わしいように思えます。

于 2011-12-02T16:16:23.617 に答える
27

美しい折り方を読んで 包み込むことでどんなものでもFoldable作れること に気がついたFunctor

data Store f a b = Store (f a) (a -> b)

シンプルなスマート コンストラクターを使用する場合:

store :: f a -> Store f a a
store x = Store x id

(これはStore comonad データ型の変形です。)

これで定義できます

instance Functor (Store f a) where
    fmap f (Store x g)   = Store x (f . g)

instance (F.Foldable f) => F.Foldable (Store f a) where
    foldr f z (Store x g)    = F.foldr (f . g) z x

このようにしてData.Set.Set、Sjoerd Visscher と Sjoerd Visscher の両方をファンクターにすることができWeirdます。(ただし、構造体はその値をメモ化しないため、使用した関数fmapが複雑な場合、繰り返し折りたたむことは非常に非効率になる可能性があります。)

更新:これは、ファンクターであり、折りたたみ可能であるがトラバース可能ではない構造の例も提供します。トラバース可能にするStoreには、トラバース可能にする必要があり(->) rます。したがって、実装する必要があります

sequenceA :: Applicative f => (r -> (f a)) -> f (r -> a)

Either bとしましょうf。次に、実装する必要があります

sequenceA' :: (r -> Either b a) -> Either b (r -> a)

明らかに、そのような機能はありません ( Djinnで確認できます)。だから私たちはどちらも実現できませんsequenceA。

于 2012-10-15T13:21:22.820 に答える