But sadly I'm not much enough of a Haskell magician to get away with cons.
You've found the fundamental problem that disallows making every Foldable a Functor; foldr
discards the structure that is folded, keeping only (what amounts to) a list of its elements. You can't "get away with cons" because you can't know what the structure of the data is given only a Foldable
instance.
Given this (typical) definition of a tree:
data Tree a = Bin a (Tree a) (Tree a) | Tip
instance Functor Tree where
fmap f (Bin a l r) = Bin (f a) (fmap f l) (fmap f r)
fmap _ Tip = Tip
instance Foldable Tree where
foldMap f (Bin a l r) = foldMap f l <> f a <> foldMap f r
foldMap _ Tip = mempty
Compare these two trees:
let x = Bin 'b' (Bin 'a' Tip Tip) Tip
let y = Bin 'a' Tip (Bin 'b' Tip Tip)
Both trees have a toList
of "ab", but are clearly different. This means that the act of folding the tree loses some information (namely, the boundary between the left subtree, right subtree, and the element) which you can not recover. Since you can't distinguish between x and y using the results from the Foldable
instance, you can't possibly write fmap
such that fmap id == id
using only those methods. We had to resort to pattern matching and using constructors to write out Functor
instance.
IO
is a functor. Let’s say there’s anx = readLn :: IO Int
.foldr (+) 0 x
must be anInt
. What is it?Applicative
andFunctor
. Just "everyApplicative
must be an instance ofFunctor
"Foldable
is too list-centric, it basically allows one to efficiently runfoldr f x . toList
. It will not distinguish between trees having the same in-order visit. Instead,fmap f
will preserve all the tree structure.