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