-- | -- Module : Foundation.Primitive.Foldable -- License : BSD-style -- Maintainer : Vincent Hanquez <vincent@snarc.org> -- Stability : experimental -- Portability : portable -- -- A mono-morphic re-thinking of the Foldable class -- module Foundation.Collection.Foldable ( Foldable(..) ) where import Foundation.Internal.Base import Foundation.Collection.Element import qualified Data.List import qualified Foundation.Array.Unboxed as UV import qualified Foundation.Array.Boxed as BA -- | Give the ability to fold a collection on itself class Foldable collection where -- | Left-associative fold of a structure. -- -- In the case of lists, foldl, when applied to a binary operator, a starting value (typically the left-identity of the operator), and a list, reduces the list using the binary operator, from left to right: -- -- > 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. This means that foldl' will diverge if given an infinite list. -- -- Also note that if you want an efficient left-fold, you probably want to use foldl' instead of foldl. The reason for this is that 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 O(n) elements long, which then must be evaluated from the outside-in. foldl :: (a -> Element collection -> a) -> a -> collection -> a -- | Left-associative fold of a structure but with strict application of the operator. foldl' :: (a -> Element collection -> a) -> a -> collection -> a -- | Right-associative fold of a structure. -- -- > foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...) foldr :: (Element collection -> a -> a) -> a -> collection -> a -- | Right-associative fold of a structure, but with strict application of the operator. foldr' :: (Element collection -> a -> a) -> a -> collection -> a foldr' f z0 xs = foldl f' id xs z0 where f' k x z = k $! f x z ---------------------------- -- Foldable instances ---------------------------- instance Foldable [a] where foldl = Data.List.foldl foldr = Data.List.foldr foldl' = Data.List.foldl' instance UV.PrimType ty => Foldable (UV.UArray ty) where foldl = UV.foldl foldr = UV.foldr foldl' = UV.foldl' instance Foldable (BA.Array ty) where foldl = BA.foldl foldr = BA.foldr foldl' = BA.foldl'