SAFE: a Foldable proposal

[Thomas Tuegel]

Gershom,

Thank you for taking the time to write such a thoughtful response. I appreciate
that you gave concrete examples; I think the discussion will be more meaningful
for it.

On Wed, Feb 24, 2016 at 10:34 PM, Gershom B <gershomb at gmail.com> wrote:

> 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.

This is a radical position, but I don't think we do want these things to be
Traversable or Foldable. Let me explain.

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

Foldable implies a notion of structural direction through the associativity of
its members. Set is different from the well-behaved Foldables because its notion
of direction or order is not structural, i.e. not preserved by operations on
Set.

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

Because it is not Applicative? Yes. For the same reason as Set, though, I do not
think it should be Foldable or Traversable. It is convenient, but unsound. Or at
least, less-sound. To fold or traverse Set and Map, I think the sound thing to
do is to use one of the provided functions to convert them to a type where
ordering is reflected structurally.

> 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.

Yes, exactly. I am suggesting we curtail the scope of Foldable severely in order
to expand its power vastly.

Regards,
Tom