On Thu, Mar 23, 2017 at 6:18 AM, Anthony Clayden < anthony_clayden@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