SAFE: a Foldable proposal

[Gershom B]

This sounds appealing until one realizes that Alternative doesn’t just rule out _some_ but _nearly all_ the things we may want to be Foldable. Especially so since Alternative is a subclass of Applicative.

And since Foldable is a superclass of Traversable, it rules out a good degree of the things we want to be Traversable.

For example, Set is a very good example of something we want to be Foldable. But it can’t be made an Alternative.

Something we want to traverse often (and fold sometimes) is Map. Map is not something that can be made an Alternative either.

Another example: Maybe is something that _is_ an Alternative.

But it cannot be made Foldable under this set of laws, since it would fail them. In fact, all alternative instances that have a “choice-like” rather than “concat-like” <|> would fail this law. And alternative instances are rare enough as is.

¯\_(ツ)_/¯

—Gershom

On February 24, 2016 at 11:04:33 PM, Thomas Tuegel (ttuegel at gmail.com) wrote:
> 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
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>