Haskell：一個不是Functor（或者不可穿越）的Foldable的例子？

Question

A Foldable實例很可能是某種容器，因此也可能是Functor。事實上，this說

一個Foldable類型也是一個容器（雖然類不技術上需要Functor，有趣Foldable s爲所有Functor S）。

那麼，有一個Foldable的一個例子，其是不天然一個Functor或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。 See for yourself.

如果檢查類型爲Set定義的專門fold和map功能的原因應該是顯而易見的：

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的評論似乎有點可疑，我想！

Answer 3

閱讀Beautiful folding 我意識到，任何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的的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。