Deprecate Foldable for Either

[Edward Kmett]

On Thu, Mar 23, 2017 at 6:18 AM, Anthony Clayden <
anthony_clayden at clear.net.nz> wrote:

>      Why is `[a]` hard-coded in the signature for concat?
>      I would expect anything specific to Lists to be
> genericised:
>     concat :: (Foldable t1, Foldable t2) => t1 (t2 a) -> t2
> a
>

Foldable can't be used to 'construct' in this way. There is no way to write
a function with the type you gave. Neither Foldable f nor even Traversable
f give you the power to construct a new 'f' with different shape.

Prelude Data.Foldable> :t concat
concat :: Foldable t => t [a] -> [a]
Prelude Data.Foldable> :t fold
fold :: (Monoid m, Foldable t) => t m -> m

concat is just a type restricted version of fold = foldMap id provided
basically for legacy compatibility.

concat/concatMap can be seen as restricted versions of fold/foldMap, which
are generalized in a variant of the manner that you seek, except for the
small consideration that they can actually exist. =)

The Foldable/Traversable proposal was to bring the functions that already
existed in base in Data.Foldable into the Prelude and eliminate the
monomorphic versions of those combinators that made importing these more
general versions painful for users. We didn't set out to make new
functions, merely standardize on the ones folks had been using for a
decade. concat was left intact, because there was already a generalization
available, and no particular reason to break all the existing code that
expected it.

     Why have an instance of Foldable which always returns
> length 1?
>      (Or for some instances returns length 0 or 1.)
>

Say you go to write a function

toVector :: Foldable f => f a -> Vector a
toVector xs = Vector.fromListN (length xs) (toList xs)

With length in Foldable, you can use and for many container types it'll
compute the length in O(1) rather than a separate pass.

Without length as a member of Foldable then we must *always* do two passes
through the container.

toVector :: Foldable f => f a -> Vector a
toVector xs = Vector.fromListN (getSum $ foldMap (\_ -> Sum 1) xs) (toList
xs)

or rely on Vector internally repeatedly doubling the guessed at size of the
vector and trimming at the end.

A number of container types can use 'length' rather than having to supply
their own monomorphic size function. Would 'length' have been better called
'size'? That is another color the bikeshed could have been colored, but it
would have involved taking a fresh name, possibly in the Prelude, and the
name collisions of a common name with existing code was considered to be
the greater evil.

`concat` and `length` should not be in Foldable.
> They should be in a separate class `Consable` (say),
> which would be a sub-class of Foldable.
>

length being in such a class would mean that every author of such a
toVector combinator above would now be hoist on the horns of the dilemma:
"Do I write this so it works in the most situations and accept two passes,
or do I write it with more constraints." This logic leads to multiple
implementations of every function having to be in scope with simple
variations in names. This would have also meant dumping a brand new
abstraction in Prelude without the preceding decade worth of
experimentation on what works well. In general the FTP didn't seek to go
out of its way to make up new classes, merely to standardize existing code
that we knew people knew how to handle. As I'll note in the following bit,
that didn't _quite_ work out perfectly, but there was initially no
intention of doing "new" API design, just to do the obvious things.

Note that `length` used not to be in Foldable.
> `concat` was, but restricted to Lists, as now.
>

While working on the Foldable/Traversable Proposal what happened was we
found we needed to add a number of methods to the Foldable class to avoid
silent changes in the semantics of existing Haskell programs. Some Foldable
combinators folded in different directions than their monomorphic
counterparts.

Along the way as we worked to fix these infelicities and noticed that as a
side-effect that this allowed Foldable authors some power to execute these
operations with better asymptotics where possible for their containers.
This nice knock-on effect lets folks shed some names that they were taking
from the environment by using what Prelude offers. During this process some
folks noticed that length/null fit into the scheme, and separately proposed
adding them. If they aren't in the class you get the above dilemma for
users of accepting the more general Foldable type with less performance or
picking up a second constraint, and they are trivially implementable as
folds, so the fit within the purview of the class, so we chose to
incorporate the proposal in question. We then chose to export them as the
length/null from the Prelude on the same grounds as the rest of the
Foldable/Traversable proposal, so that users could avoid having to import
Data.Foldable explicitly and that names we take wouldn't conflict with
Prelude.

With the choices made all of the "mainstream" base modules now have no name
conflicts and can be imported unqualified.

If there's a need for a method in Foldable
> to return 1 for a tuple, or 0..1 for Maybe/Either,
> don't call it `length`, call it `cardinality` (say).
> (This is the same approach as for separate `map`, `fmap`,
> `foldMap`.)


Could we have named them flength (or size) and fnull so that people had to
ask for them explicitly and left length/null alone? Yes. But it would have
meant taking new names from the Prelude or not re-exporting them from
Data.Foldable, and the AMP/FTP tried to very careful about introducing any
new names to the Prelude, and wanted users to be able to supply instances
without having to explicitly import Data.Foldable.

We were very dubious about the response we'd get introducing new, untested,
names to Prelude as everyone's code is impacted by that choice and folks
happen to be using all the "good" names for such things, and nobody had
done so in the preceding 17 years, so any changes along those lines are
surprising.

-Edward
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20170323/7f46c3c0/attachment.html>