haskellderivingfoldable

Are there laws for the Foldable typeclass that constrain how Foldable instances can be derived?


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?


Solution

  • Foldable has no laws guiding the order of traversal. In fact, we can think of the act of writing a Foldable instance as choosing a specific order of traversal. If DeriveFoldable is used, the choice will be to follow the order of the fields in the definition of the type (see also Daniel Wagner's answer); the details are documented in the relevant section of the GHC User's Guide.

    (Side note: As discussed in dfeuer's answer, Traversable has richer laws that, among other things, limit the range of acceptable foldMap implementations. Still, both inorder and preorder traversals for your Tree give out lawful implementations of Traversable.)