Friends, I address you this evening in the desperate hope that, though we have become divided by harsh words, we may come together again as one family in Haskell. Before, we saw as through a glass, darkly. To drive back the night, we stoked the fires of our passion. Now the heat burns us! The smoke stings our eyes! I intend to magnify what was hidden so we may see clearly by only a small flame. We came to Haskell along many paths, but the same values drew us all. One of the values dearest to us is the ability to reason statically about our programs. To enhance this ability which Haskell naturally affords us, we have devised laws to govern our type classes. Type class laws are rightly judged by their strength: the ways in which they constrain the instances we may write. When these laws bind us most tightly, we may reason most freely. With this in mind, let us turn to the Foldable class. Foldable has several laws, but I will focus on two. First, for foldr and foldMap,
foldr f z t = appEndo (foldMap (Endo . f) t) z
Second, optionally, for Functors,
foldMap f = fold . fmap f
There are other laws, but for my purposes, they essentially follow from the above. It is generally acknowledged that these laws are relatively weak: it is difficult to conceive an instance which violates them that is not an egregious violation. With that, I offer the following simple proposal. I doubt it will achieve consensus, but I believe it will illuminate our positions more clearly. I hope it allows us to see each other with more empathy. SAFE - Stronger Alternative Foldable Enhancement / Elucidation Foldable will gain a superclass, Alternative:
class Alternative t => Foldable t where { ... }
The members of the class will not change. The class will gain the following laws to supercede the existing laws:
foldMap f empty = mempty foldMap f (xs <|> ys) = foldMap f xs <> foldMap f ys
foldr f z empty = z foldr f z (xs <|> ys) = foldr f (foldr f z ys) xs
The laws for the other members follow in the obvious way. Some instances from base are ruled out: Identity, Either a, (,) a, Proxy, and Const m. Implementing this change would necessitate attaching warnings to those instances for the customary length of time. It is my understanding that GHC is not currently able to attach warnings to instances, but I think that would be a useful feature to add, even absent the current proposal. I think this Foldable class is better than the one we have now. These constraints are stronger because they show the connection between Alternative and Monoid. I will pause here a moment because I think this is crucial to the contention between us. Foldable could be a bridge between Alternative and Monoid. We do not agree about how much may be expected of the Foldable class. I think this is what we should expect. I think this guarantee, that there is a monoidal or Alternative structure underlying Foldable, was always the unarticulated vision behind the objections to these contentious instances. I hope that the utility and elegance of my proposal will convince you, but failing that I hope it illuminates what should be our topic of discussion: not "What is to be done about Foldable?" but rather, "What is to be expected of Foldable?" Sincerely, Thomas