What are some Foldable instances that are _not_ "general Foldable structures" in the sense of Data.Foldable?

Question

The documentation for Foldable lists several properties that are demanded of "general Foldable structures":

• For foldr:

  For a general Foldable structure this should be semantically identical to,

  foldr f z = foldr f z . toList
  

• For foldl:

  For a general Foldable structure this should be semantically identical to,

  foldl f z = foldl f z . toList
  

• For foldl' (with what looks like a typo to me):

  For a general Foldable structure this should be semantically identical to,

  foldl f z = foldl' f z . toList
  

What are some instances of Foldable where these properties need not or cannot hold?

Answer 1

As I understand it, these are rules that an instance must obey if it defines those optional functions. By default, a Foldable instance only has to define either foldMap or foldr. From one of those two definitions, all the other functions of the type class follow automatically.

Often, however, type classes give you the option to define more of the type class' behaviour. This can be useful if the default, automatic definition of, say, toList is inefficient, and you wish to supply a more efficient implementation. This may be easier to understand for the Monoid type class, which defines mconcat as an optional function "so that an optimized version can be provided for specific types".

The laws quoted in the OP are laws that an instance must obey if you choose to define some or all of these functions yourself. As an example of a (nonsensical) type that breaks the rules, consider this Invalid type:

import Data.Foldable

data Invalid a = Invalid a deriving (Show, Eq)

instance Foldable Invalid where
  foldMap f (Invalid x) = f x
  foldr _ x _ = x -- Unlawful!!
  toList (Invalid x) = [x]

While it only has to define foldMap to be a Foldable instance, this one also defines foldr and toList. While the toList definition is fine, the foldr definition breaks the rules:

*Q53460772 Data.Monoid Data.Foldable> toList $ Invalid 42
[42]
*Q53460772 Data.Monoid Data.Foldable> foldMap Sum $ Invalid 42
Sum {getSum = 42}
*Q53460772 Data.Monoid Data.Foldable> f = \x acc -> x + acc
*Q53460772 Data.Monoid Data.Foldable> z = 0
*Q53460772 Data.Monoid Data.Foldable> (foldr f z . toList) $ Invalid 42
42
*Q53460772 Data.Monoid Data.Foldable> foldr f z $ Invalid 42
0

The toList and foldMap functions behave like you'd expect them to behave, but notice that foldr f z doesn't produce the same output as foldr f z . toList.

While Invalid is a nonsensical example, it demonstrates that you can write code that compiles and looks like it provides an instance of Foldable. The laws and rules associated with each function, however, makes it clear that this is not a valid instance.