I'm experimenting with the Foldable
typeclass in Haskell, using the following data type as an example:
data Tree a = Empty
| Node (Tree a) a (Tree a)
If I use the DeriveFoldable
GHC extension, it seems to derive a Foldable
instance along the lines of
instance Foldable Tree where
foldMap _ Empty = mempty
foldMap f (Node l n r) = (foldMap f l) <> (f n) <> (foldMap f r)
i.e., an inorder traversal of the tree. However, I don't see anything obvious preventing a different Foldable
instance, such as a preorder traversal:
instance Foldable Tree where
foldMap _ Empty = mempty
foldMap f (Node l n r) = (f n) <> (foldMap f l) <> (foldMap f r)
Are there laws for the Foldable
typeclass that would make the preorder traversal instance unlawful?
Node a (Tree a) (Tree a)
, it would be preorder traversal. – SupersonicsfoldMap f = fold . fmap f
(as is specified in the documentation). – SupersonicsNode a (Tree a) (Tree a)
, since then the datastructure "hints" how the foldable will look like. – SupersonicsDeriveFoldable
just uses the parameter order? Sounds like a good answer. – Ezechielsum = getSum . foldMap Sum
, etc. to sum up the type. In essence the idea is that you fold over it satisfying monadic laws. – Supersonics