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?
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
.)
Foldable
itself is very poor in laws. The fundamental method is foldMap
. Other methods are expected to behave like their default definitions up to laziness details. Two laws arise from parametricity:
If g :: m -> n
is a monoid morphism and f :: a -> m
is a function, then
g . foldMap f = foldMap (g . f)
If the Foldable
is also a Functor
, then for all functions g :: b -> m
and f :: a -> b
,
foldMap (g . f) = foldMap g . fmap f
In practice, most Foldable
instances are also Traversable
. Traversable
has much richer laws for traverse
, and imposes the law that
foldMap f = getConst . traverse (Const . f)
This guarantees that for a Traversable
, every element in the container is folded over exactly once. Whereas
instance Foldable [] where
foldMap _ [] = mempty
foldMap f (x:_:xs) = f x <> f x <> foldMap f xs
would be perfectly valid, there's no lawful Traversable
instance that matches.
No, there are no laws that tell what order fields must be visited in. It is conventional to visit fields in the order they appear in the data structure definition (or at least the user-visible API, if pattern synonyms are used), but this is convention only.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With