diff options
author | Viktor Dukhovni <ietf-dane@dukhovni.org> | 2021-03-18 20:07:43 -0400 |
---|---|---|
committer | Marge Bot <ben+marge-bot@smart-cactus.org> | 2021-04-01 16:13:59 -0400 |
commit | 84b76f6086d7a294986a50ad0750482582a76772 (patch) | |
tree | 579ec5d0fa3383ed8b54365ac9e3ef51eea9e270 | |
parent | 15b6c9f920d8f60ebfef4580ec7e8f063799a83a (diff) | |
download | haskell-84b76f6086d7a294986a50ad0750482582a76772.tar.gz |
Chiral foldable caveats
-rw-r--r-- | libraries/base/Data/Foldable.hs | 40 |
1 files changed, 37 insertions, 3 deletions
diff --git a/libraries/base/Data/Foldable.hs b/libraries/base/Data/Foldable.hs index 56e12ae9cd..8e797f33f2 100644 --- a/libraries/base/Data/Foldable.hs +++ b/libraries/base/Data/Foldable.hs @@ -52,6 +52,9 @@ module Data.Foldable ( -- * Overview -- $overview + -- ** Chirality + -- $chirality + -- ** Recursive and corecursive reduction -- $reduction @@ -1461,9 +1464,9 @@ https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context. -- #leftright# -- Merging the contribution of the current element with an accumulator value -- from a partial result is performed by an /operator/ function, either --- explicitly provided by the caller as in `foldr`, implicit as in `length`, or --- partly implicit as in `foldMap` (where each element is mapped into a --- 'Monoid', and the monoid's `mappend` operator performs the merge). +-- explicitly provided by the caller as in `foldr`, implicit count as in +-- `length`, or partly implicit as in `foldMap` (where each element is mapped +-- into a 'Monoid', and the monoid's `mappend` operator performs the merge). -- -- A key distinction is between left-associative and right-associative -- folds: @@ -1559,12 +1562,43 @@ https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context. -- reached, by which point a deep stack of pending function applications -- may have been built up in memory. -- + +-- $chirality +-- +-- #chirality# +-- Foldable structures are generally expected to be efficiently iterable from +-- left to right. Right-to-left iteration may be substantially more costly, +-- or even impossible (as with, for example, infinite lists). The text in +-- the sections below that describes performance differences between +-- left-associative right-associative folds pessimistically assumes such +-- /left-handed/ structures. +-- -- In finite structures for which right-to-left sequencing no less efficient -- than left-to-right sequencing, there is no inherent performance distinction -- between left-associative and right-associative folds. If the structure's -- @Foldable@ instance takes advantage of this symmetry to also make strict -- right folds space-efficient and lazy left folds corecursive, one need only -- take care to choose either a strict or lazy method for the task at hand. +-- +-- Foldable instances for symmetric structures should strive to provide equally +-- performant left-associative and right-associative interfaces. The main +-- limitations are: +-- +-- * The lazy 'fold', 'foldMap' and 'toList' methods have no right-associative +-- counterparts. +-- * The strict 'foldMap'' method has no left-associative counterpart. +-- +-- Thus, for some foldable structures 'foldr'' is just as efficient as 'foldl'' +-- for strict reduction, and 'foldl' may be just as appropriate for corecursive +-- folds as 'foldr'. +-- +-- Finally, in some less common structures (e.g. /snoc/ lists) right to left +-- iterations are cheaper than left to right. For these, you may need to flip +-- left and right in the descriptions below. When using such a structure, you +-- may also need to pay careful attention to the chirality of the fold's +-- /operator/ function, it may need to be flipped when its strictness is +-- different between its first and second argument (it will of course need to +-- be flipped when its argument types are different). -------------- |