import GHC.Arr
#elif defined(__HUGS__)
import Hugs.Array
+#elif defined(__NHC__)
+import Array
#endif
-- | Data structures that can be folded.
--
-- a suitable instance would be
--
--- > instance Foldable Tree
+-- > instance Foldable Tree where
-- > foldMap f Empty = mempty
-- > foldMap f (Leaf x) = f x
-- > foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
--
-- This is suitable even for abstract types, as the monoid is assumed
--- to satisfy the monoid laws.
+-- to satisfy the monoid laws. Alternatively, one could define @foldr@:
+--
+-- > instance Foldable Tree where
+-- > foldr f z Empty = z
+-- > foldr f z (Leaf x) = f x z
+-- > foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
--
class Foldable t where
-- | Combine the elements of a structure using a monoid.
-- instances for Prelude types
instance Foldable Maybe where
- foldr f z Nothing = z
+ foldr _ z Nothing = z
foldr f z (Just x) = f x z
- foldl f z Nothing = z
+ foldl _ z Nothing = z
foldl f z (Just x) = f z x
instance Foldable [] where
foldr1 = Prelude.foldr1
foldl1 = Prelude.foldl1
-#ifndef __NHC__
instance Ix i => Foldable (Array i) where
- foldr f z = Prelude.foldr f z . elems
-#endif
+ foldr f z = Prelude.foldr f z . elems
+ foldl f z = Prelude.foldl f z . elems
+ foldr1 f = Prelude.foldr1 f . elems
+ foldl1 f = Prelude.foldl1 f . elems
-- | Fold over the elements of a structure,
-- associating to the right, but strictly.
foldr' :: Foldable t => (a -> b -> b) -> b -> t a -> b
-foldr' f z xs = foldl f' id xs z
+foldr' f z0 xs = foldl f' id xs z0
where f' k x z = k $! f x z
-- | Monadic fold over the elements of a structure,
-- associating to the right, i.e. from right to left.
foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b
-foldrM f z xs = foldl f' return xs z
+foldrM f z0 xs = foldl f' return xs z0
where f' k x z = f x z >>= k
-- | Fold over the elements of a structure,
-- associating to the left, but strictly.
foldl' :: Foldable t => (a -> b -> a) -> a -> t b -> a
-foldl' f z xs = foldr f' id xs z
+foldl' f z0 xs = foldr f' id xs z0
where f' x k z = k $! f z x
-- | Monadic fold over the elements of a structure,
-- associating to the left, i.e. from left to right.
foldlM :: (Foldable t, Monad m) => (a -> b -> m a) -> a -> t b -> m a
-foldlM f z xs = foldr f' return xs z
+foldlM f z0 xs = foldr f' return xs z0
where f' x k z = f z x >>= k
-- | Map each element of a structure to an action, evaluate
-- | List of elements of a structure.
toList :: Foldable t => t a -> [a]
+{-# INLINE toList #-}
#ifdef __GLASGOW_HASKELL__
toList t = build (\ c n -> foldr c n t)
#else