{-# LANGUAGE MultiParamTypeClasses
,FunctionalDependencies
,FlexibleInstances #-}
{-
Copyright (C) 2007 John Goerzen
All rights reserved.
For license and copyright information, see the file COPYRIGHT
-}
{- |
Module : Data.ListLike.FoldableLL
Copyright : Copyright (C) 2007 John Goerzen
License : LGPL
Maintainer : John Goerzen
Stability : provisional
Portability: portable
Generic tools for data structures that can be folded.
Written by John Goerzen, jgoerzen\@complete.org
-}
module Data.ListLike.FoldableLL
(-- * FoldableLL Class
FoldableLL(..),
-- * Utilities
fold, foldMap
) where
import Prelude hiding (foldl, foldr, foldr1)
import qualified Data.Foldable as F
import Data.Monoid
import Data.Maybe
import qualified Data.List as L
{- | This is the primary class for structures that are to be considered
foldable. A minimum complete definition provides 'foldl' and 'foldr'.
Instances of 'FoldableLL' can be folded, and can be many and varied.
These functions are used heavily in "Data.ListLike". -}
class FoldableLL full item | full -> item where
{- | Left-associative fold -}
foldl :: (a -> item -> a) -> a -> full -> a
{- | Strict version of 'foldl'. -}
foldl' :: (a -> item -> a) -> a -> full -> a
-- This implementation from Data.Foldable
foldl' f a xs = foldr f' id xs a
where f' x k z = k $! f z x
-- | A variant of 'foldl' with no base case. Requires at least 1
-- list element.
foldl1 :: (item -> item -> item) -> full -> item
-- This implementation from Data.Foldable
foldl1 f xs = fromMaybe (error "fold1: empty structure")
(foldl mf Nothing xs)
where mf Nothing y = Just y
mf (Just x) y = Just (f x y)
{- | Right-associative fold -}
foldr :: (item -> b -> b) -> b -> full -> b
-- | Strict version of 'foldr'
foldr' :: (item -> b -> b) -> b -> full -> b
-- This implementation from Data.Foldable
foldr' f a xs = foldl f' id xs a
where f' k x z = k $! f x z
-- | Like 'foldr', but with no starting value
foldr1 :: (item -> item -> item) -> full -> item
-- This implementation from Data.Foldable
foldr1 f xs = fromMaybe (error "foldr1: empty structure")
(foldr mf Nothing xs)
where mf x Nothing = Just x
mf x (Just y) = Just (f x y)
{- | Combine the elements of a structure using a monoid.
@'fold' = 'foldMap' id@ -}
fold :: (FoldableLL full item, Monoid item) => full -> item
fold = foldMap id
{- | Map each element to a monoid, then combine the results -}
foldMap :: (FoldableLL full item, Monoid m) => (item -> m) -> full -> m
foldMap f = foldr (mappend . f) mempty
instance FoldableLL [a] a where
foldl = L.foldl
foldl1 = L.foldl1
foldl' = L.foldl'
foldr = L.foldr
foldr1 = L.foldr1
foldr' = F.foldr'
{-
instance (F.Foldable f) => FoldableLL (f a) a where
foldl = F.foldl
foldl1 = F.foldl1
foldl' = F.foldl'
foldr = F.foldr
foldr1 = F.foldr1
foldr' = F.foldr'
-}