SAFE: a Foldable proposal

[Thomas Tuegel]

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