ファンチャーではない（または通過できない）折りたたみ可能な例？

Question

a Foldable インスタンスは何らかの容器である可能性が高いので、 Functor 同じように。それはそう、 これ 言う

a Foldable タイプはコンテナでもあります（ただし、クラスは技術的には必要ありませんが Functor, 、 面白い FoldableSはすべてです Functors）。

aの例があります Foldable 当然のことではありません Functor またはa Traversable？ （おそらくHaskell wikiページを逃した:-)）

Answer 1

これが完全にパラメトリックな例です。

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

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

Weird ではありません Functor なぜなら a 負の位置で発生します。

Answer 2

簡単な例があります： 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, 、これはあなたが「面白い」について引用した発言をします FoldableSは少し疑わしいようです！

Answer 3

読む 美しい折りたたみ 私はそれを気づきました Foldable にすることができます Functor それを包むことによって

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

シンプルなスマートコントラクタで：

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

（これは単なるバリアントです 店 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's 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)

明らかに、そのような機能はありません（で確認できます ジン）。だから私たちはどちらも気付くことができません sequenceA.