diff options
author | Viktor Dukhovni <ietf-dane@dukhovni.org> | 2021-01-05 06:55:43 -0500 |
---|---|---|
committer | Marge Bot <ben+marge-bot@smart-cactus.org> | 2021-01-09 21:20:23 -0500 |
commit | e07ba458156c7d038dba2e7b9e1372c3bbed9994 (patch) | |
tree | e20a86726b7dc3009671c81920d73de310aaa0aa /libraries | |
parent | f9605e1a34e7586c371b3c4b7fdbfb8743ad6861 (diff) | |
download | haskell-e07ba458156c7d038dba2e7b9e1372c3bbed9994.tar.gz |
More tidy synopses, and new generative recursion
- Further correction and reconcialation with new overview
of the existing synopses. Restored some "Tree" examples.
- New section on generative recursion via Church encoding
of lists.
Diffstat (limited to 'libraries')
-rw-r--r-- | libraries/base/Data/Foldable.hs | 329 |
1 files changed, 260 insertions, 69 deletions
diff --git a/libraries/base/Data/Foldable.hs b/libraries/base/Data/Foldable.hs index d2c880f2e6..3ca6713c0f 100644 --- a/libraries/base/Data/Foldable.hs +++ b/libraries/base/Data/Foldable.hs @@ -76,7 +76,10 @@ module Data.Foldable ( -- *** Hybrid folds -- $hybrid - -- ** Avoiding multi-pass algorithms + -- ** Generative Recursion + -- $generative + + -- ** Avoiding multi-pass folds -- $multipass -- * Defining instances @@ -124,13 +127,17 @@ infix 4 `elem`, `notElem` -- | The Foldable class represents data structures that can be reduced to a -- summary value one element at a time. Strict left-associative folds are a -- good fit for space-efficient reduction, while lazy right-associative folds --- are good fit for corecursive iteration or for folds that short-circuit after --- processing an initial subsequence of the structure's elements. +-- are a good fit for corecursive iteration, or for folds that short-circuit +-- after processing an initial subsequence of the structure's elements. -- -- Instances can be derived automatically by enabling the @DeriveFoldable@ -- extension. For example, a derived instance for a binary tree might be: -- --- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a) deriving Foldable +-- > {-# LANGUAGE DeriveFoldable #-} +-- > data Tree a = Empty +-- > | Leaf a +-- > | Node (Tree a) a (Tree a) +-- > deriving Foldable -- -- A more detailed description can be found in the overview section of -- "Data.Foldable#overview". @@ -138,10 +145,10 @@ infix 4 `elem`, `notElem` class Foldable t where {-# MINIMAL foldMap | foldr #-} - -- | Combine the elements of a structure using `mappend`. - -- Right-associative and lazy in the accumulator. For - -- strict left-associative folds, use `foldMap'` instead, - -- with 'id' as the map. + -- | Given a structure with elements whose type is a 'Monoid', combine them + -- via the monoid's @('<>')@ operator. This fold is right-associative and + -- lazy in the accumulator. When you need a strict left-associative fold, + -- use `foldMap'` instead, with 'id' as the map. -- -- ==== __Examples__ -- @@ -150,16 +157,16 @@ class Foldable t where -- >>> fold [[1, 2, 3], [4, 5], [6], []] -- [1,2,3,4,5,6] -- - -- >>> fold [Sum 1, Sum 3, Sum 5] + -- >>> fold $ Node (Leaf (Sum 1)) (Sum 3) (Leaf (Sum 5)) -- Sum {getSum = 9} -- - -- Folds of unbounded structures do not terminate when the Monoid's - -- `mappend` is strict: + -- Folds of unbounded structures do not terminate when the monoid's + -- @('<>')@ operator is strict: -- -- >>> fold (repeat Nothing) -- * Hangs forever * -- - -- Lazy folds of unbounded structures are fine: + -- Lazy corecursive folds of unbounded structures are fine: -- -- >>> take 12 $ fold $ map (\i -> [i..i+2]) [0..] -- [0,1,2,1,2,3,2,3,4,3,4,5] @@ -169,9 +176,10 @@ class Foldable t where fold :: Monoid m => t m -> m fold = foldMap id - -- | Map each element of the structure to a monoid, and combine the - -- results. Right-associative and lazy in the accumulator. - -- For strict left-associative folds consider `foldMap'` instead. + -- | Map each element of the structure into a monoid, and combine the + -- results with @('<>')@. This fold is right-associative and lazy in the + -- accumulator. For strict left-associative folds consider `foldMap'` + -- instead. -- -- ==== __Examples__ -- @@ -186,9 +194,10 @@ class Foldable t where -- >>> foldMap (replicate 3) [1, 2, 3] -- [1,1,1,2,2,2,3,3,3] -- - -- When a Monoid's `mappend` is lazy in its second argument, 'foldMap' can - -- return a possibly unbounded result even from a structure that is - -- unbounded on the right: + -- When a Monoid's @('<>')@ is lazy in its second argument, 'foldMap' can + -- return a result even from an unbounded structure. For example, lazy + -- accumulation enables "Data.ByteString.Builder" to efficiently serialise + -- large data structures and produce the output incrementally: -- -- >>> import qualified Data.ByteString.Lazy as L -- >>> import qualified Data.ByteString.Builder as B @@ -199,12 +208,30 @@ class Foldable t where -- foldMap :: Monoid m => (a -> m) -> t a -> m {-# INLINE foldMap #-} - -- This INLINE allows more list functions to fuse. See #9848. + -- This INLINE allows more list functions to fuse. See #9848. foldMap f = foldr (mappend . f) mempty -- | A left-associative variant of 'foldMap' that is strict in the - -- accumulator. Best method for strict reduction when partial - -- results are merged via `mappend`. + -- accumulator. Use this method for strict reduction when partial + -- results are merged via @('<>')@. + -- + -- ==== __Examples__ + -- + -- Define a 'Monoid' over finite bit strings under 'xor'. Use it to + -- strictly compute the `xor` of a list of 'Int' values. + -- + -- >>> :set -XGeneralizedNewtypeDeriving + -- >>> import Data.Bits (Bits, FiniteBits, xor, zeroBits) + -- >>> import Data.Foldable (foldMap') + -- >>> import Numeric (showHex) + -- >>> + -- >>> newtype X a = X a deriving (Eq, Bounded, Enum, Bits, FiniteBits) + -- >>> instance Bits a => Semigroup (X a) where X a <> X b = X (a `xor` b) + -- >>> instance Bits a => Monoid (X a) where mempty = X zeroBits + -- >>> + -- >>> let bits :: [Int]; bits = [0xcafe, 0xfeed, 0xdeaf, 0xbeef, 0x5411] + -- >>> (\ (X a) -> showString "0x" . showHex a $ "") $ foldMap' X bits + -- "0x42" -- -- @since 4.13.0.0 foldMap' :: Monoid m => (a -> m) -> t a -> m @@ -252,7 +279,7 @@ class Foldable t where -- -- ====== Short-circuiting -- - -- '(||)' short-circuits on 'True' values, so the following terminates + -- @('||')@ short-circuits on 'True' values, so the following terminates -- because there is a 'True' value finitely far from the left side: -- -- >>> foldr (||) False (True : repeat False) @@ -266,9 +293,10 @@ class Foldable t where -- ====== Laziness in the second argument -- -- Applying 'foldr' to infinite structures terminates when the operator is - -- lazy in its second argument: + -- lazy in its second argument (the initial accumulator is never used in + -- this case, and so could be left 'undefined', but @[]@ is more clear): -- - -- >>> take 5 $ foldr (\i acc -> i : fmap (+3) acc) [42] (repeat 1) + -- >>> take 5 $ foldr (\i acc -> i : fmap (+3) acc) [] (repeat 1) -- [1,4,7,10,13] foldr :: (a -> b -> b) -> b -> t a -> b foldr f z t = appEndo (foldMap (Endo #. f) t) z @@ -293,15 +321,15 @@ class Foldable t where -- > foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn -- -- Note that to produce the outermost application of the operator the - -- entire input list must be traversed. Like all left-associative folds, + -- entire input list must be traversed. Like all left-associative folds, -- 'foldl' will diverge if given an infinite list. -- -- If you want an efficient strict left-fold, you probably want to use - -- `foldl'` instead of 'foldl'. The reason for this is that the latter does - -- not force the /inner/ results (e.g. @z \`f\` x1@ in the above example) - -- before applying them to the operator (e.g. to @(\`f\` x2)@). This - -- results in a thunk chain \(\mathcal{O}(n)\) elements long, which then - -- must be evaluated from the outside-in. + -- `foldl'` instead of 'foldl'. The reason for this is that the latter + -- does not force the /inner/ results (e.g. @z \`f\` x1@ in the above + -- example) before applying them to the operator (e.g. to @(\`f\` x2)@). + -- This results in a thunk chain \(\mathcal{O}(n)\) elements long, which + -- then must be evaluated from the outside-in. -- -- For a general 'Foldable' structure this should be semantically identical -- to: @@ -338,10 +366,10 @@ class Foldable t where -- | Left-associative fold of a structure but with strict application of -- the operator. -- - -- This ensures that each step of the fold is forced to weak head normal - -- form before being applied, avoiding the collection of thunks that would - -- otherwise occur. This is often what you want to strictly reduce a finite - -- structure to a single strict result (e.g. 'sum'). + -- This ensures that each step of the fold is forced to Weak Head Normal + -- Form before being applied, avoiding the collection of thunks that would + -- otherwise occur. This is often what you want to strictly reduce a + -- finite structure to a single strict result (e.g. 'sum'). -- -- For a general 'Foldable' structure this should be semantically identical -- to, @@ -462,10 +490,10 @@ class Foldable t where toList t = build (\ c n -> foldr c n t) -- | Test whether the structure is empty. The default implementation is - -- Left-associative, lazy in both the initial element and the accumulator. - -- Thus optimised for structures where the first element can be accessed in - -- constant time. Structures where this is not the case should have a - -- non-default implementation. + -- Left-associative and lazy in both the initial element and the + -- accumulator. Thus optimised for structures where the first element can + -- be accessed in constant time. Structures where this is not the case + -- should have a non-default implementation. -- -- ==== __Examples__ -- @@ -543,8 +571,10 @@ class Foldable t where -- | The largest element of a non-empty structure. -- - -- This function is non-total and will raise a runtime exception if the - -- structure happens to be empty. + -- This function is non-total and will raise a runtime exception if the + -- structure happens to be empty. A structure that supports random access + -- and maintains its elements in order should provide a specialised + -- implementation to return the maximum in faster than linear time. -- -- ==== __Examples__ -- @@ -568,7 +598,9 @@ class Foldable t where -- | The least element of a non-empty structure. -- -- This function is non-total and will raise a runtime exception if the - -- structure happens to be empty + -- structure happens to be empty A structure that supports random access + -- and maintains its elements in order should provide a specialised + -- implementation to return the minimum in faster than linear time. -- -- ==== __Examples__ -- @@ -969,7 +1001,7 @@ foldlM f z0 xs = foldr c return xs z0 {-# INLINE c #-} -- | Map each element of a structure to an 'Applicative' action, evaluate these --- actions from left to right, and ignore the results. For a version that +-- actions from left to right, and ignore the results. For a version that -- doesn't ignore the results see 'Data.Traversable.traverse'. -- -- 'traverse_' is just like 'mapM_', but generalised to 'Applicative' actions. @@ -988,7 +1020,7 @@ traverse_ f = foldr c (pure ()) where c x k = f x *> k {-# INLINE c #-} --- | 'for_' is 'traverse_' with its arguments flipped. For a version +-- | 'for_' is 'traverse_' with its arguments flipped. For a version -- that doesn't ignore the results see 'Data.Traversable.for'. This -- is 'forM_' generalised to 'Applicative' actions. -- @@ -1008,7 +1040,7 @@ for_ :: (Foldable t, Applicative f) => t a -> (a -> f b) -> f () for_ = flip traverse_ -- | Map each element of a structure to a monadic action, evaluate --- these actions from left to right, and ignore the results. For a +-- these actions from left to right, and ignore the results. For a -- version that doesn't ignore the results see -- 'Data.Traversable.mapM'. -- @@ -1020,7 +1052,7 @@ mapM_ f = foldr c (return ()) where c x k = f x >> k {-# INLINE c #-} --- | 'forM_' is 'mapM_' with its arguments flipped. For a version that +-- | 'forM_' is 'mapM_' with its arguments flipped. For a version that -- doesn't ignore the results see 'Data.Traversable.forM'. -- -- 'forM_' is just like 'for_', but specialised to monadic actions. @@ -1030,7 +1062,7 @@ forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m () forM_ = flip mapM_ -- | Evaluate each action in the structure from left to right, and --- ignore the results. For a version that doesn't ignore the results +-- ignore the results. For a version that doesn't ignore the results -- see 'Data.Traversable.sequenceA'. -- -- 'sequenceA_' is just like 'sequence_', but generalised to 'Applicative' @@ -1051,7 +1083,7 @@ sequenceA_ = foldr c (pure ()) {-# INLINE c #-} -- | Evaluate each monadic action in the structure from left to right, --- and ignore the results. For a version that doesn't ignore the +-- and ignore the results. For a version that doesn't ignore the -- results see 'Data.Traversable.sequence'. -- -- 'sequence_' is just like 'sequenceA_', but specialised to monadic @@ -1393,16 +1425,16 @@ Note [maximumBy/minimumBy space usage] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ When the type signatures of maximumBy and minimumBy were generalized to work over any Foldable instance (instead of just lists), they were defined using -foldr1. This was problematic for space usage, as the semantics of maximumBy +foldr1. This was problematic for space usage, as the semantics of maximumBy and minimumBy essentially require that they examine every element of the -data structure. Using foldr1 to examine every element results in space usage -proportional to the size of the data structure. For the common case of lists, +data structure. Using foldr1 to examine every element results in space usage +proportional to the size of the data structure. For the common case of lists, this could be particularly bad (see #10830). For the common case of lists, switching the implementations of maximumBy and minimumBy to foldl1 solves the issue, assuming GHC's strictness analysis can then -make these functions only use O(1) stack space. As of base 4.16, we have -switched to employing foldl' over foldl1, not relying on GHC's optimiser. See +make these functions only use O(1) stack space. As of base 4.16, we have +switched to employing foldl' over foldl1, not relying on GHC's optimiser. See https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context. -} @@ -1537,7 +1569,7 @@ https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context. -- entire input structure, and so the input must be finite. -- -- * __Corecursion__, which yields intermediate results as it encounters --- additional input elements. Lazy processing of the remaining elements +-- additional input elements. Lazy processing of the remaining elements -- makes the intermediate results available even before the rest of the -- input is processed. The input may be unbounded, and the caller can -- stop processing intermediate results early. @@ -1557,7 +1589,7 @@ https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context. -- suited to the task at hand, resulting in a fold that fails to yield -- incremental results until the entire input is processed, or fails to -- strictly evaluate results as it goes, deferring all the work to the --- evaluation of a large final thunk. Such cases should be avoided, either by +-- evaluation of a large final thunk. Such cases should be avoided, either by -- selecting a more appropriate @Foldable@ method, or by tailoring the operator -- to the chosen method. -- @@ -1634,7 +1666,7 @@ https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context. -- #corec# -- Common examples of lazy corecursive reduction are functions that map and -- flatten a structure to a lazy stream of result values, i.e. an iterator --- over the transformed input elements. In such cases, it is important to +-- over the transformed input elements. In such cases, it is important to -- choose a @Foldable@ method that is lazy in the tail of the structure, such -- as `foldr` (or `foldMap`, if the result @Monoid@ has a lazy `mappend` as -- with e.g. ByteString Builders). @@ -1875,7 +1907,7 @@ https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context. -- The 'Node' case is a right fold of the left subtree whose initial -- value is a right fold of the rest of the tree. -- --- For example, when `f` is '(:)', all three cases return an immediate value, +-- For example, when @f@ is @(':')@, all three cases return an immediate value, -- respectively @z@ or a /cons cell/ holding @x@ or @l@, with the remainder the -- structure, if any, encapsulated in a lazy thunk. This meets the expected -- efficient [corecursive](#corec) behaviour of 'foldr'. @@ -1938,7 +1970,7 @@ https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context. -- would support only corecursive and short-circuit folds (diverge under strict -- reduction). -- --- Returning to more mininal instances defined in terms of just `foldr`, it is +-- Returning to simpler instances, defined just in terms of `foldr`, it is -- somewhat surprising that a fairly efficient /default/ implementation of the -- strict `foldl'` is defined in terms of lazy `foldr` when only the latter is -- explicitly provided by the instance. It may be instructive to take a look @@ -1983,8 +2015,167 @@ https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context. -------------- +-- $generative +-- +-- #generative# +-- So far, we have not discussed /generative recursion/. Unlike recursive +-- reduction or corecursion, instead of processing a sequence of elements +-- already in memory, generative recursion involves producing a possibly +-- unbounded sequence of values from an initial seed value. The canonical +-- example of this is 'Data.List.unfoldr' for Lists, with variants available +-- for Vectors and various other structures. +-- +-- A key issue with lists, when used generatively as /iterators/, rather than as +-- poor-man's containers (see [[1\]](#uselistsnot)), is that such iterators +-- tend to consume memory when used more than once. A single traversal of a +-- list-as-iterator will run in constant space, but as soon as the list is +-- retained for reuse, its entire element sequence is stored in memory, and the +-- second traversal reads the copy, rather than regenerates the elements. It +-- is sometimes better to recompute the elements rather than memoise the list. +-- +-- Memoisation happens because the built-in Haskell list __@[]@__ is +-- represented as __data__, either empty or a /cons-cell/ holding the first +-- element and the tail of the list. The @Foldable@ class enables a variant +-- representation of iterators as /functions/, which take an operator and a +-- starting accumulator and output a summary result. +-- +-- The [@fmlist@](https://hackage.haskell.org/package/fmlist) package takes +-- this approach, by representing a list via its `foldMap` action. +-- +-- Below we implement an analogous data structure using a representation +-- based on `foldr`. This is an example of /Church encoding/ +-- (named after Alonzo Church, inventor of the lambda calculus). +-- +-- > {-# LANGUAGE RankNTypes #-} +-- > newtype FRList a = FR { unFR :: forall b. (a -> b -> b) -> b -> b } +-- +-- The __@unFR@__ field of this type is essentially its `foldr` method +-- with the list as its first rather than last argument. Thus we +-- immediately get a @Foldable@ instance (and a 'toList' function +-- mapping an __@FRList@__ to a regular list). +-- +-- > instance Foldable FRList where +-- > foldr f z l = unFR l f z +-- > -- With older versions of @base@, also define sum, product, ... +-- > -- to ensure use of the strict `foldl'`. +-- > -- sum = foldl' (+) 0 +-- > -- ... +-- +-- We can convert a regular list to an __@FRList@__ with: +-- +-- > fromList :: [a] -> FRList a +-- > fromList as = FRList $ \ f z -> foldr f z as +-- +-- However, reuse of an __@FRList@__ obtained in this way will typically +-- memoise the underlying element sequence. Instead, we can define +-- __@FRList@__ terms directly: +-- +-- > -- | Immediately return the initial accumulator +-- > nil :: FRList a +-- > nil = FRList $ \ _ z -> z +-- > {-# INLINE nil #-} +-- +-- > -- | Fold the tail to use as an accumulator with the new initial element +-- > cons :: a -> FRList a -> FRList a +-- > cons a l = FRList $ \ f z -> f a (unFR l f z) +-- > {-# INLINE cons #-} +-- +-- More crucially, we can also directly define the key building block for +-- generative recursion: +-- +-- > -- | Generative recursion, dual to `foldr`. +-- > unfoldr :: (s -> Maybe (a, s)) -> s -> FRList a +-- > unfoldr g s0 = FR generate +-- > where generate f z = loop s0 +-- > where loop s | Just (a, t) <- g s = f a (loop t) +-- > | otherwise = z +-- > {-# INLINE unfoldr #-} +-- +-- Which can, for example, be specialised to number ranges: +-- +-- > -- | Generate a range of consecutive integral values. +-- > range :: (Ord a, Integral a) => a -> a -> FRList a +-- > range lo hi = +-- > unfoldr (\s -> if s > hi then Nothing else Just (s, s+1)) lo +-- > {-# INLINE range #-} +-- +-- The program below, when compiled with optimisation: +-- +-- > main :: IO () +-- > main = do +-- > let r :: FRList Int +-- > r = range 1 10000000 +-- > in print (sum r, length r) +-- +-- produces the expected output with no noticeable garbage-collection, despite +-- reuse of the __@FRList@__ term __@r@__. +-- +-- > (50000005000000,10000000) +-- > 52,120 bytes allocated in the heap +-- > 3,320 bytes copied during GC +-- > 44,376 bytes maximum residency (1 sample(s)) +-- > 25,256 bytes maximum slop +-- > 3 MiB total memory in use (0 MB lost due to fragmentation) +-- +-- The Weak Head Normal Form of an __@FRList@__ is a lambda abstraction not a +-- data value, and reuse does not lead to memoisation. Reuse of the iterator +-- above is somewhat contrived, when computing multiple folds over a common +-- list, you should generally traverse a list only [once](#multipass). The +-- goal is to demonstrate that the separate computations of the 'sum' and +-- 'length' run efficiently in constant space, despite reuse. This would not +-- be the case with the list @[1..10000000]@. +-- +-- This is, however, an artificially simple reduction. More typically, there +-- are likely to be some allocations in the inner loop, but the temporary +-- storage used will be garbage-collected as needed, and overall memory +-- utilisation will remain modest and will not scale with the size of the list. +-- +-- If we go back to built-in lists (i.e. __@[]@__), but avoid reuse by +-- performing reduction in a single pass, as below: +-- +-- > data PairS a b = P !a !b -- We define a strict pair datatype +-- > +-- > main :: IO () +-- > main = do +-- > let l :: [Int] +-- > l = [1..10000000] +-- > in print $ average l +-- > where +-- > sumlen :: PairS Int Int -> Int -> PairS Int Int +-- > sumlen (P s l) a = P (s + a) (l + 1) +-- > +-- > average is = +-- > let (P s l) = foldl' sumlen (P 0 0) is +-- > in (fromIntegral s :: Double) / fromIntegral l +-- +-- the result is again obtained in constant space: +-- +-- > 5000000.5 +-- > 102,176 bytes allocated in the heap +-- > 3,320 bytes copied during GC +-- > 44,376 bytes maximum residency (1 sample(s)) +-- > 25,256 bytes maximum slop +-- > 3 MiB total memory in use (0 MB lost due to fragmentation) +-- +-- (and, in fact, faster than with __@FRList@__ by a small factor). +-- +-- The __@[]@__ list structure works as an efficient iterator when used +-- just once. When space-leaks via list reuse are not a concern, and/or +-- memoisation is actually desirable, the regular list implementation is +-- likely to be faster. This is not a suggestion to replace all your uses of +-- __@[]@__ with a generative alternative. +-- +-- The __@FRList@__ type could be further extended with instances of 'Functor', +-- 'Applicative', 'Monad', 'Alternative', etc., and could then provide a +-- fully-featured list type, optimised for reuse without space-leaks. If, +-- however, all that's required is space-efficient, re-use friendly iteration, +-- less is perhaps more, and just @Foldable@ may be sufficient. + +-------------- + -- $multipass -- +-- #multipass# -- In applications where you want to compute a composite function of a -- structure, which requires more than one aggregate as an input, it is -- generally best to compute all the aggregates in a single pass, rather @@ -2001,21 +2192,21 @@ https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context. -- -- > import Data.Foldable (foldl') -- > --- > data PairS a b = P !a !b -- strict pair +-- > data PairS a b = P !a !b -- We define a strict pair datatype -- > -- > -- | Compute sum and length in a single pass, then reduce to the average. -- > average :: (Foldable f, Fractional a) => f a -> a --- > average = pairToFrac . foldl' f z --- > where --- > z = P 0 (0 :: Int) --- > f (P s l) a = P (s+a) (l+1) --- > pairToFrac (P s l) = s / fromIntegral l --- --- The above example is somewhat contrived, some structures keep track of --- their length internally, and can return it in @O(1)@ time, so this --- particular recipe for averages is not always the most efficient. --- In general, composite aggregate functions of large structures benefit --- from single-pass reduction. +-- > average xs = +-- > let sumlen (P s l) a = P (s + a) (l + 1 :: Int) +-- > (P s l) = foldl' sumlen (P 0 0) xs +-- > in s / fromIntegral l +-- +-- The above example is somewhat contrived, some structures keep track of their +-- length internally, and can return it in \(\mathcal{O}(1)\) time, so this +-- particular recipe for averages is not always the most efficient. In +-- general, composite aggregate functions of large structures benefit from +-- single-pass reduction. This is especially the case when reuse of a list and +-- memoisation of its elements is thereby avoided, -------------- |