Say I have some simplified lisp-style Expr type as follows
data Expr = String String | Cons Expr Expr
deriving (Show)
I can create lists as Cons-cells of Cons-cells:
Cons (String "hello") (Cons (String "World") (String "!"))
From this I would like to implement Foldable for Expr to fold over these cons lists - but that's not possible, since Foldable requires a type of kind * -> * (i.e. polymorphic with exactly one type parameter), wheres my Expr has kind *.
Why is that? To me it seems like folding over non-polymorphic types like in this case would be perfectly reasonable, but obviously I'm missing something.
To me it seems like folding over non-polymorphic types like in this case would be perfectly reasonable, but obviously I'm missing something.
It is perfectly reasonable indeed. One way of folding a monomorphic container is using MonoFoldable. Another is using a Fold from lens, or from some other optics library:
import Control.Lens
data Expr = String String | Cons Expr Expr
deriving (Show)
-- A Traversal can also be used as a Fold.
-- strings :: Applicative f => (String -> f String) -> (Expr -> f Expr)
strings :: Traversal' Expr String
strings f (String s) = String <$> f s
strings f (Cons l r) = Cons <$> strings f l <*> strings f r
GHCi> hello = Cons (String "hello") (Cons (String "World") (String "!"))
GHCi> toListOf strings hello
["hello","World","!"]
GHCi> import Data.Monoid
GHCi> foldMapOf strings (Sum . length) hello
Sum {getSum = 11}
As for why Foldable instances have kind * -> * rather than *, I would put it down to a combination of simplicity and historical reasons. Historically speaking, Foldable is an offshoot of Traversable, and it is worth noting that, while monomorphic traversals can be useful, their limitations are rather more striking than those which affect monomorphic folds (for instance, you can't recover fmap from them, but merely a monomorphic omap). Finally, the Q&A suggested by Joseph Sible, Is there anything we lose with MonoFoldable?, includes some interesting discussion of potential reasons for not outright replacing Foldable with MonoFoldable.