Data.List.Fold - fold lists in constant space

Fold.hs

-- | Lock-step folding.
--
-- This module presents an elegant way of executing multiple left folds
-- on one list using constant memory. For example, the mean can be
-- expressed as:
--
-- @
--     average = foldLeft $ (/) <$> sumF <*> lengthF
-- @

module Data.List.Fold
    (
    -- * Building folds
      Fold(..)
    , fromAccum

    -- * Using folds
    , foldLeft

    -- * Some useful folds
    , sumF
    , lengthF
    , averageF
    , monoidF
    ) where

import Control.Applicative
import Data.List ( foldl' )
import Data.Monoid ( Monoid(..) )

-- | Folding state. A type @Fold i o@ represents a fold which combines
-- multiple values of type @i@ into a summary value of type @o@.
data Fold i o = Fold
    {
    -- | Accumulator value.
      finalize :: o
    -- | Inject a value, updating the state within.
    , inject  :: i -> Fold i o
    }

-- | Apply a function to the result of a fold.
instance Functor (Fold i) where
    fmap f (Fold out run) = Fold (f out) $ \i -> fmap f (run i)

-- | Merge the results of two folds together.
instance Applicative (Fold i) where
    pure x = Fold x $ const (pure x)
    Fold out run <*> Fold out' run' = Fold out'' run''
      where
        out'' = out out'
        run'' = \i -> run i <*> run' i

-- | Fold a list from left to right.
foldLeft :: Fold i o -> [i] -> o
foldLeft f = finalize . foldl' inject f

-- | Bundle an accumulator function into a 'Fold' object.
fromAccum :: (o -> i -> o) -> o -> Fold i o
fromAccum f o = o `seq` Fold o $ \i -> fromAccum f (f o i)

sumF :: Num a => Fold a a
sumF = fromAccum (+) 0

lengthF :: Num i => Fold a i
lengthF = fromAccum (\n _ -> n + 1) 0

averageF :: Fractional a => Fold a a
averageF = (/) <$> sumF <*> lengthF

concatF :: Monoid m => Fold m m
concatF = fromAccum mappend mempty