Proposal: Add a few extra members to Foldable and Traversable classes

Herbert Valerio Riedel hvr at
Fri Sep 19 11:54:19 UTC 2014

On 2014-09-19 at 01:26:22 +0200, David Feuer wrote:
> After discussing these matters some more with Edward Kmett and Reid Barton,
> it appears the following makes sense:
> Add the following to Foldable:

> length—often stored as a separate field for O(1) access
> null—called very often and slightly faster than foldr (\_ _ -> False) True
> for some containers
> toList—may be the identity or nearly so, and this fact may not be
> statically available to the foldr/id rule
> sum, product—may be cached internally in tree nodes for fast update, giving
> O(1) access; may be calculated in parallel.
> maximum, minimum—O(n) for a search tree; O(1) for a finger tree.
> elem—O(log n) for search trees; likely better for hash tables and such.
> Don't add anything to Traversable, because scanl1 and scanr1 are not worth
> the extra dictionary weight.

Seems sensible to me, hence +1

More information about the Libraries mailing list