[add 'applicative' package, which has Control.Applicative, Control.Arrow Control.Category Data.Foldable and Data.Traversable
John Meacham <john@repetae.net>**20090226115308
 Ignore-this: 6663b690f2fef4ae82fed1bdcf7c7af0
] adddir ./lib/applicative
adddir ./lib/applicative/Control
addfile ./lib/applicative/Control/Applicative.hs
addfile ./lib/applicative/Control/Arrow.hs
addfile ./lib/applicative/Control/Category.hs
adddir ./lib/applicative/Data
addfile ./lib/applicative/Data/Foldable.hs
addfile ./lib/applicative/Data/Traversable.hs
addfile ./lib/applicative/applicative.cabal
hunk ./Makefile.am 51
-JHC_LIBS =  base-1.0.hl haskell98-1.0.hl
+JHC_LIBS =  base-1.0.hl haskell98-1.0.hl applicative-1.0.hl
hunk ./Makefile.am 218
+applicative-1.0.hl: lib/applicative/applicative.cabal base-1.0.hl
+	mkdir -p tmp/libho
+	./jhc -v $(RTSOPTS) $(JHC_TEST)  --ho-dir tmp/libho -ilib/applicative  --noauto -L- -L. -p base --build-hl lib/applicative/applicative.cabal -o $@
+
hunk ./lib/applicative/Control/Applicative.hs 1
+-----------------------------------------------------------------------------
+-- |
+-- Module      :  Control.Applicative
+-- Copyright   :  Conor McBride and Ross Paterson 2005
+-- License     :  BSD-style (see the LICENSE file in the distribution)
+--
+-- Maintainer  :  ross@soi.city.ac.uk
+-- Stability   :  experimental
+-- Portability :  portable
+--
+-- This module describes a structure intermediate between a functor and
+-- a monad: it provides pure expressions and sequencing, but no binding.
+-- (Technically, a strong lax monoidal functor.)  For more details, see
+-- /Applicative Programming with Effects/,
+-- by Conor McBride and Ross Paterson, online at
+-- <http://www.soi.city.ac.uk/~ross/papers/Applicative.html>.
+--
+-- This interface was introduced for parsers by Niklas R&#xF6;jemo, because
+-- it admits more sharing than the monadic interface.  The names here are
+-- mostly based on recent parsing work by Doaitse Swierstra.
+--
+-- This class is also useful with instances of the
+-- 'Data.Traversable.Traversable' class.
+
+module Control.Applicative (
+        -- * Applicative functors
+        Applicative(..),
+        -- * Alternatives
+        Alternative(..),
+        -- * Instances
+        Const(..), WrappedMonad(..), WrappedArrow(..), ZipList(..),
+        -- * Utility functions
+        (<$>), (<$), (*>), (<*), (<**>),
+        liftA, liftA2, liftA3,
+        optional, some, many
+        ) where
+
+import Prelude hiding (id,(.))
+import qualified Prelude
+
+import Control.Category
+import Control.Arrow
+        (Arrow(arr, (&&&)), ArrowZero(zeroArrow), ArrowPlus((<+>)))
+import Control.Monad (liftM, ap, MonadPlus(..))
+import Control.Monad.Instances ()
+import Data.Monoid (Monoid(..))
+
+infixl 3 <|>
+infixl 4 <$>, <$
+infixl 4 <*>, <*, *>, <**>
+
+-- | A functor with application.
+--
+-- Instances should satisfy the following laws:
+--
+-- [/identity/]
+--      @'pure' 'id' '<*>' v = v@
+--
+-- [/composition/]
+--      @'pure' (.) '<*>' u '<*>' v '<*>' w = u '<*>' (v '<*>' w)@
+--
+-- [/homomorphism/]
+--      @'pure' f '<*>' 'pure' x = 'pure' (f x)@
+--
+-- [/interchange/]
+--      @u '<*>' 'pure' y = 'pure' ('$' y) '<*>' u@
+--
+-- The 'Functor' instance should satisfy
+--
+-- @
+--      'fmap' f x = 'pure' f '<*>' x
+-- @
+--
+-- If @f@ is also a 'Monad', define @'pure' = 'return'@ and @('<*>') = 'ap'@.
+
+class Functor f => Applicative f where
+        -- | Lift a value.
+        pure :: a -> f a
+
+        -- | Sequential application.
+        (<*>) :: f (a -> b) -> f a -> f b
+
+-- | A monoid on applicative functors.
+class Applicative f => Alternative f where
+        -- | The identity of '<|>'
+        empty :: f a
+        -- | An associative binary operation
+        (<|>) :: f a -> f a -> f a
+
+-- instances for Prelude types
+
+instance Applicative Maybe where
+        pure = return
+        (<*>) = ap
+
+instance Alternative Maybe where
+        empty = Nothing
+        Nothing <|> p = p
+        Just x <|> _ = Just x
+
+instance Applicative [] where
+        pure = return
+        (<*>) = ap
+
+instance Alternative [] where
+        empty = []
+        (<|>) = (++)
+
+instance Applicative IO where
+        pure = return
+        (<*>) = ap
+
+instance Applicative ((->) a) where
+        pure = const
+        (<*>) f g x = f x (g x)
+
+instance Monoid a => Applicative ((,) a) where
+        pure x = (mempty, x)
+        (u, f) <*> (v, x) = (u `mappend` v, f x)
+
+-- new instances
+
+newtype Const a b = Const { getConst :: a }
+
+instance Functor (Const m) where
+        fmap _ (Const v) = Const v
+
+instance Monoid m => Applicative (Const m) where
+        pure _ = Const mempty
+        Const f <*> Const v = Const (f `mappend` v)
+
+newtype WrappedMonad m a = WrapMonad { unwrapMonad :: m a }
+
+instance Monad m => Functor (WrappedMonad m) where
+        fmap f (WrapMonad v) = WrapMonad (liftM f v)
+
+instance Monad m => Applicative (WrappedMonad m) where
+        pure = WrapMonad . return
+        WrapMonad f <*> WrapMonad v = WrapMonad (f `ap` v)
+
+instance MonadPlus m => Alternative (WrappedMonad m) where
+        empty = WrapMonad mzero
+        WrapMonad u <|> WrapMonad v = WrapMonad (u `mplus` v)
+
+newtype WrappedArrow a b c = WrapArrow { unwrapArrow :: a b c }
+
+instance Arrow a => Functor (WrappedArrow a b) where
+        fmap f (WrapArrow a) = WrapArrow (a >>> arr f)
+
+instance Arrow a => Applicative (WrappedArrow a b) where
+        pure x = WrapArrow (arr (const x))
+        WrapArrow f <*> WrapArrow v = WrapArrow (f &&& v >>> arr (uncurry id))
+
+instance (ArrowZero a, ArrowPlus a) => Alternative (WrappedArrow a b) where
+        empty = WrapArrow zeroArrow
+        WrapArrow u <|> WrapArrow v = WrapArrow (u <+> v)
+
+-- | Lists, but with an 'Applicative' functor based on zipping, so that
+--
+-- @f '<$>' 'ZipList' xs1 '<*>' ... '<*>' 'ZipList' xsn = 'ZipList' (zipWithn f xs1 ... xsn)@
+--
+newtype ZipList a = ZipList { getZipList :: [a] }
+
+instance Functor ZipList where
+        fmap f (ZipList xs) = ZipList (map f xs)
+
+instance Applicative ZipList where
+        pure x = ZipList (repeat x)
+        ZipList fs <*> ZipList xs = ZipList (zipWith id fs xs)
+
+-- extra functions
+
+-- | A synonym for 'fmap'.
+(<$>) :: Functor f => (a -> b) -> f a -> f b
+f <$> a = fmap f a
+
+-- | Replace the value.
+(<$) :: Functor f => a -> f b -> f a
+(<$) = (<$>) . const
+ 
+-- | Sequence actions, discarding the value of the first argument.
+(*>) :: Applicative f => f a -> f b -> f b
+(*>) = liftA2 (const id)
+ 
+-- | Sequence actions, discarding the value of the second argument.
+(<*) :: Applicative f => f a -> f b -> f a
+(<*) = liftA2 const
+ 
+-- | A variant of '<*>' with the arguments reversed.
+(<**>) :: Applicative f => f a -> f (a -> b) -> f b
+(<**>) = liftA2 (flip ($))
+
+-- | Lift a function to actions.
+-- This function may be used as a value for `fmap` in a `Functor` instance.
+liftA :: Applicative f => (a -> b) -> f a -> f b
+liftA f a = pure f <*> a
+
+-- | Lift a binary function to actions.
+liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
+liftA2 f a b = f <$> a <*> b
+
+-- | Lift a ternary function to actions.
+liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
+liftA3 f a b c = f <$> a <*> b <*> c
+
+-- | One or none.
+optional :: Alternative f => f a -> f (Maybe a)
+optional v = Just <$> v <|> pure Nothing
+
+-- | One or more.
+some :: Alternative f => f a -> f [a]
+some v = some_v
+  where many_v = some_v <|> pure []
+        some_v = (:) <$> v <*> many_v
+
+-- | Zero or more.
+many :: Alternative f => f a -> f [a]
+many v = many_v
+  where many_v = some_v <|> pure []
+        some_v = (:) <$> v <*> many_v
hunk ./lib/applicative/Control/Arrow.hs 1
+-----------------------------------------------------------------------------
+-- |
+-- Module      :  Control.Arrow
+-- Copyright   :  (c) Ross Paterson 2002
+-- License     :  BSD-style (see the LICENSE file in the distribution)
+--
+-- Maintainer  :  ross@soi.city.ac.uk
+-- Stability   :  experimental
+-- Portability :  portable
+--
+-- Basic arrow definitions, based on
+--      /Generalising Monads to Arrows/, by John Hughes,
+--      /Science of Computer Programming/ 37, pp67-111, May 2000.
+-- plus a couple of definitions ('returnA' and 'loop') from
+--      /A New Notation for Arrows/, by Ross Paterson, in /ICFP 2001/,
+--      Firenze, Italy, pp229-240.
+-- See these papers for the equations these combinators are expected to
+-- satisfy.  These papers and more information on arrows can be found at
+-- <http://www.haskell.org/arrows/>.
+
+module Control.Arrow (
+                -- * Arrows
+                Arrow(..), Kleisli(..),
+                -- ** Derived combinators
+                returnA,
+                (^>>), (>>^),
+                -- ** Right-to-left variants
+                (<<^), (^<<),
+                -- * Monoid operations
+                ArrowZero(..), ArrowPlus(..),
+                -- * Conditionals
+                ArrowChoice(..),
+                -- * Arrow application
+                ArrowApply(..), ArrowMonad(..), leftApp,
+                -- * Feedback
+                ArrowLoop(..)
+        ) where
+
+import Prelude hiding (id,(.))
+import qualified Prelude
+
+import Control.Monad
+import Control.Monad.Fix
+import Control.Category
+
+infixr 5 <+>
+infixr 3 ***
+infixr 3 &&&
+infixr 2 +++
+infixr 2 |||
+infixr 1 ^>>, >>^
+infixr 1 ^<<, <<^
+
+-- | The basic arrow class.
+--   Any instance must define either 'arr' or 'pure' (which are synonyms),
+--   as well as 'first'.  The other combinators have sensible
+--   default definitions, which may be overridden for efficiency.
+
+class Category a => Arrow a where
+
+        -- | Lift a function to an arrow: you must define either this
+        --   or 'pure'.
+        arr :: (b -> c) -> a b c
+        arr = pure
+
+        -- | A synonym for 'arr': you must define one or other of them.
+        pure :: (b -> c) -> a b c
+        pure = arr
+
+        -- | Send the first component of the input through the argument
+        --   arrow, and copy the rest unchanged to the output.
+        first :: a b c -> a (b,d) (c,d)
+
+        -- | A mirror image of 'first'.
+        --
+        --   The default definition may be overridden with a more efficient
+        --   version if desired.
+        second :: a b c -> a (d,b) (d,c)
+        second f = arr swap >>> first f >>> arr swap
+                        where   swap ~(x,y) = (y,x)
+
+        -- | Split the input between the two argument arrows and combine
+        --   their output.  Note that this is in general not a functor.
+        --
+        --   The default definition may be overridden with a more efficient
+        --   version if desired.
+        (***) :: a b c -> a b' c' -> a (b,b') (c,c')
+        f *** g = first f >>> second g
+
+        -- | Fanout: send the input to both argument arrows and combine
+        --   their output.
+        --
+        --   The default definition may be overridden with a more efficient
+        --   version if desired.
+        (&&&) :: a b c -> a b c' -> a b (c,c')
+        f &&& g = arr (\b -> (b,b)) >>> f *** g
+
+{-# RULES
+"identity"
+                arr id = id
+"compose/arr"   forall f g .
+                (arr f) . (arr g) = arr (f . g)
+"first/arr"     forall f .
+                first (arr f) = arr (first f)
+"second/arr"    forall f .
+                second (arr f) = arr (second f)
+"product/arr"   forall f g .
+                arr f *** arr g = arr (f *** g)
+"fanout/arr"    forall f g .
+                arr f &&& arr g = arr (f &&& g)
+"compose/first" forall f g .
+                (first f) . (first g) = first (f . g)
+"compose/second" forall f g .
+                (second f) . (second g) = second (f . g)
+ #-}
+
+-- Ordinary functions are arrows.
+
+instance Arrow (->) where
+        arr f = f
+        first f = f *** id
+        second f = id *** f
+--      (f *** g) ~(x,y) = (f x, g y)
+--      sorry, although the above defn is fully H'98, nhc98 can't parse it.
+        (***) f g ~(x,y) = (f x, g y)
+
+-- | Kleisli arrows of a monad.
+
+newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }
+
+instance Monad m => Category (Kleisli m) where
+        id = Kleisli return
+        (Kleisli f) . (Kleisli g) = Kleisli (\b -> g b >>= f)
+
+instance Monad m => Arrow (Kleisli m) where
+        arr f = Kleisli (return . f)
+        first (Kleisli f) = Kleisli (\ ~(b,d) -> f b >>= \c -> return (c,d))
+        second (Kleisli f) = Kleisli (\ ~(d,b) -> f b >>= \c -> return (d,c))
+
+-- | The identity arrow, which plays the role of 'return' in arrow notation.
+
+returnA :: Arrow a => a b b
+returnA = arr id
+
+-- | Precomposition with a pure function.
+(^>>) :: Arrow a => (b -> c) -> a c d -> a b d
+f ^>> a = arr f >>> a
+
+-- | Postcomposition with a pure function.
+(>>^) :: Arrow a => a b c -> (c -> d) -> a b d
+a >>^ f = a >>> arr f
+
+-- | Precomposition with a pure function (right-to-left variant).
+(<<^) :: Arrow a => a c d -> (b -> c) -> a b d
+a <<^ f = a <<< arr f
+
+-- | Postcomposition with a pure function (right-to-left variant).
+(^<<) :: Arrow a => (c -> d) -> a b c -> a b d
+f ^<< a = arr f <<< a
+
+class Arrow a => ArrowZero a where
+        zeroArrow :: a b c
+
+instance MonadPlus m => ArrowZero (Kleisli m) where
+        zeroArrow = Kleisli (\x -> mzero)
+
+class ArrowZero a => ArrowPlus a where
+        (<+>) :: a b c -> a b c -> a b c
+
+instance MonadPlus m => ArrowPlus (Kleisli m) where
+        Kleisli f <+> Kleisli g = Kleisli (\x -> f x `mplus` g x)
+
+-- | Choice, for arrows that support it.  This class underlies the
+--   @if@ and @case@ constructs in arrow notation.
+--   Any instance must define 'left'.  The other combinators have sensible
+--   default definitions, which may be overridden for efficiency.
+
+class Arrow a => ArrowChoice a where
+
+        -- | Feed marked inputs through the argument arrow, passing the
+        --   rest through unchanged to the output.
+        left :: a b c -> a (Either b d) (Either c d)
+
+        -- | A mirror image of 'left'.
+        --
+        --   The default definition may be overridden with a more efficient
+        --   version if desired.
+        right :: a b c -> a (Either d b) (Either d c)
+        right f = arr mirror >>> left f >>> arr mirror
+                        where   mirror (Left x) = Right x
+                                mirror (Right y) = Left y
+
+        -- | Split the input between the two argument arrows, retagging
+        --   and merging their outputs.
+        --   Note that this is in general not a functor.
+        --
+        --   The default definition may be overridden with a more efficient
+        --   version if desired.
+        (+++) :: a b c -> a b' c' -> a (Either b b') (Either c c')
+        f +++ g = left f >>> right g
+
+        -- | Fanin: Split the input between the two argument arrows and
+        --   merge their outputs.
+        --
+        --   The default definition may be overridden with a more efficient
+        --   version if desired.
+        (|||) :: a b d -> a c d -> a (Either b c) d
+        f ||| g = f +++ g >>> arr untag
+                        where   untag (Left x) = x
+                                untag (Right y) = y
+
+{-# RULES
+"left/arr"      forall f .
+                left (arr f) = arr (left f)
+"right/arr"     forall f .
+                right (arr f) = arr (right f)
+"sum/arr"       forall f g .
+                arr f +++ arr g = arr (f +++ g)
+"fanin/arr"     forall f g .
+                arr f ||| arr g = arr (f ||| g)
+"compose/left"  forall f g .
+                left f >>> left g = left (f >>> g)
+"compose/right" forall f g .
+                right f >>> right g = right (f >>> g)
+ #-}
+
+instance ArrowChoice (->) where
+        left f = f +++ id
+        right f = id +++ f
+        f +++ g = (Left . f) ||| (Right . g)
+        (|||) = either
+
+instance Monad m => ArrowChoice (Kleisli m) where
+        left f = f +++ arr id
+        right f = arr id +++ f
+        f +++ g = (f >>> arr Left) ||| (g >>> arr Right)
+        Kleisli f ||| Kleisli g = Kleisli (either f g)
+
+-- | Some arrows allow application of arrow inputs to other inputs.
+
+class Arrow a => ArrowApply a where
+        app :: a (a b c, b) c
+
+instance ArrowApply (->) where
+        app (f,x) = f x
+
+instance Monad m => ArrowApply (Kleisli m) where
+        app = Kleisli (\(Kleisli f, x) -> f x)
+
+-- | The 'ArrowApply' class is equivalent to 'Monad': any monad gives rise
+--   to a 'Kleisli' arrow, and any instance of 'ArrowApply' defines a monad.
+
+newtype ArrowMonad a b = ArrowMonad (a () b)
+
+instance ArrowApply a => Monad (ArrowMonad a) where
+        return x = ArrowMonad (arr (\z -> x))
+        ArrowMonad m >>= f = ArrowMonad (m >>>
+                        arr (\x -> let ArrowMonad h = f x in (h, ())) >>>
+                        app)
+
+-- | Any instance of 'ArrowApply' can be made into an instance of
+--   'ArrowChoice' by defining 'left' = 'leftApp'.
+
+leftApp :: ArrowApply a => a b c -> a (Either b d) (Either c d)
+leftApp f = arr ((\b -> (arr (\() -> b) >>> f >>> arr Left, ())) |||
+                 (\d -> (arr (\() -> d) >>> arr Right, ()))) >>> app
+
+-- | The 'loop' operator expresses computations in which an output value is
+--   fed back as input, even though the computation occurs only once.
+--   It underlies the @rec@ value recursion construct in arrow notation.
+
+class Arrow a => ArrowLoop a where
+        loop :: a (b,d) (c,d) -> a b c
+
+instance ArrowLoop (->) where
+        loop f b = let (c,d) = f (b,d) in c
+
+instance MonadFix m => ArrowLoop (Kleisli m) where
+        loop (Kleisli f) = Kleisli (liftM fst . mfix . f')
+                where   f' x y = f (x, snd y)
hunk ./lib/applicative/Control/Category.hs 1
+-----------------------------------------------------------------------------
+-- |
+-- Module      :  Control.Category
+-- Copyright   :  (c) Ashley Yakeley 2007
+-- License     :  BSD-style (see the LICENSE file in the distribution)
+--
+-- Maintainer  :  ashley@semantic.org
+-- Stability   :  experimental
+-- Portability :  portable
+
+-- http://hackage.haskell.org/trac/ghc/ticket/1773
+
+module Control.Category where
+
+import Prelude hiding (id,(.))
+import qualified Prelude
+
+infixr 9 .
+infixr 1 >>>, <<<
+
+-- | A class for categories.
+--   id and (.) must form a monoid.
+class Category cat where
+        -- | the identity morphism
+        id :: cat a a
+
+        -- | morphism composition
+        (.) :: cat b c -> cat a b -> cat a c
+
+{-# RULES
+"identity/left" forall p .
+                id . p = p
+"identity/right"        forall p .
+                p . id = p
+"association"   forall p q r .
+                (p . q) . r = p . (q . r)
+ #-}
+
+instance Category (->) where
+        id = Prelude.id
+        (.) = (Prelude..)
+
+-- | Right-to-left composition
+(<<<) :: Category cat => cat b c -> cat a b -> cat a c
+(<<<) = (.)
+
+-- | Left-to-right composition
+(>>>) :: Category cat => cat a b -> cat b c -> cat a c
+f >>> g = g . f
hunk ./lib/applicative/Data/Foldable.hs 1
+{-# LANGUAGE CPP #-}
+-----------------------------------------------------------------------------
+-- |
+-- Module      :  Data.Foldable
+-- Copyright   :  Ross Paterson 2005
+-- License     :  BSD-style (see the LICENSE file in the distribution)
+--
+-- Maintainer  :  ross@soi.city.ac.uk
+-- Stability   :  experimental
+-- Portability :  portable
+--
+-- Class of data structures that can be folded to a summary value.
+--
+-- Many of these functions generalize "Prelude", "Control.Monad" and
+-- "Data.List" functions of the same names from lists to any 'Foldable'
+-- functor.  To avoid ambiguity, either import those modules hiding
+-- these names or qualify uses of these function names with an alias
+-- for this module.
+
+module Data.Foldable (
+        -- * Folds
+        Foldable(..),
+        -- ** Special biased folds
+        foldr',
+        foldl',
+        foldrM,
+        foldlM,
+        -- ** Folding actions
+        -- *** Applicative actions
+        traverse_,
+        for_,
+        sequenceA_,
+        asum,
+        -- *** Monadic actions
+        mapM_,
+        forM_,
+        sequence_,
+        msum,
+        -- ** Specialized folds
+        toList,
+        concat,
+        concatMap,
+        and,
+        or,
+        any,
+        all,
+        sum,
+        product,
+        maximum,
+        maximumBy,
+        minimum,
+        minimumBy,
+        -- ** Searches
+        elem,
+        notElem,
+        find
+        ) where
+
+import Prelude hiding (foldl, foldr, foldl1, foldr1, mapM_, sequence_,
+                elem, notElem, concat, concatMap, and, or, any, all,
+                sum, product, maximum, minimum)
+import qualified Prelude (foldl, foldr, foldl1, foldr1)
+import Control.Applicative
+import Control.Monad (MonadPlus(..))
+import Data.Maybe (fromMaybe, listToMaybe)
+import Data.Monoid
+
+#ifdef __NHC__
+import Control.Arrow (ArrowZero(..)) -- work around nhc98 typechecker problem
+#endif
+
+#ifdef __GLASGOW_HASKELL__
+import GHC.Exts (build)
+#endif
+
+-- | Data structures that can be folded.
+--
+-- Minimal complete definition: 'foldMap' or 'foldr'.
+--
+-- For example, given a data type
+--
+-- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
+--
+-- a suitable instance would be
+--
+-- > instance Foldable Tree
+-- >    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.
+--
+class Foldable t where
+        -- | Combine the elements of a structure using a monoid.
+        fold :: Monoid m => t m -> m
+        fold = foldMap id
+
+        -- | Map each element of the structure to a monoid,
+        -- and combine the results.
+        foldMap :: Monoid m => (a -> m) -> t a -> m
+        foldMap f = foldr (mappend . f) mempty
+
+        -- | Right-associative fold of a structure.
+        --
+        -- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@
+        foldr :: (a -> b -> b) -> b -> t a -> b
+        foldr f z t = appEndo (foldMap (Endo . f) t) z
+
+        -- | Left-associative fold of a structure.
+        --
+        -- @'foldl' f z = 'Prelude.foldl' f z . 'toList'@
+        foldl :: (a -> b -> a) -> a -> t b -> a
+        foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
+
+        -- | A variant of 'foldr' that has no base case,
+        -- and thus may only be applied to non-empty structures.
+        --
+        -- @'foldr1' f = 'Prelude.foldr1' f . 'toList'@
+        foldr1 :: (a -> a -> a) -> t a -> a
+        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)
+
+        -- | A variant of 'foldl' that has no base case,
+        -- and thus may only be applied to non-empty structures.
+        --
+        -- @'foldl1' f = 'Prelude.foldl1' f . 'toList'@
+        foldl1 :: (a -> a -> a) -> t a -> a
+        foldl1 f xs = fromMaybe (error "foldl1: empty structure")
+                        (foldl mf Nothing xs)
+          where mf Nothing y = Just y
+                mf (Just x) y = Just (f x y)
+
+-- instances for Prelude types
+
+instance Foldable Maybe where
+        foldr f z Nothing = z
+        foldr f z (Just x) = f x z
+
+        foldl f z Nothing = z
+        foldl f z (Just x) = f z x
+
+instance Foldable [] where
+        foldr = Prelude.foldr
+        foldl = Prelude.foldl
+        foldr1 = Prelude.foldr1
+        foldl1 = Prelude.foldl1
+
+-- | 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
+  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
+  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
+  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
+  where f' x k z = f z x >>= k
+
+-- | Map each element of a structure to an action, evaluate
+-- these actions from left to right, and ignore the results.
+traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
+traverse_ f = foldr ((*>) . f) (pure ())
+
+-- | 'for_' is 'traverse_' with its arguments flipped.
+for_ :: (Foldable t, Applicative f) => t a -> (a -> f b) -> f ()
+{-# INLINE for_ #-}
+for_ = flip traverse_
+
+-- | Map each element of a structure to a monadic action, evaluate
+-- these actions from left to right, and ignore the results.
+mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
+mapM_ f = foldr ((>>) . f) (return ())
+
+-- | 'forM_' is 'mapM_' with its arguments flipped.
+forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()
+{-# INLINE forM_ #-}
+forM_ = flip mapM_
+
+-- | Evaluate each action in the structure from left to right,
+-- and ignore the results.
+sequenceA_ :: (Foldable t, Applicative f) => t (f a) -> f ()
+sequenceA_ = foldr (*>) (pure ())
+
+-- | Evaluate each monadic action in the structure from left to right,
+-- and ignore the results.
+sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()
+sequence_ = foldr (>>) (return ())
+
+-- | The sum of a collection of actions, generalizing 'concat'.
+asum :: (Foldable t, Alternative f) => t (f a) -> f a
+{-# INLINE asum #-}
+asum = foldr (<|>) empty
+
+-- | The sum of a collection of actions, generalizing 'concat'.
+msum :: (Foldable t, MonadPlus m) => t (m a) -> m a
+{-# INLINE msum #-}
+msum = foldr mplus mzero
+
+-- These use foldr rather than foldMap to avoid repeated concatenation.
+
+-- | List of elements of a structure.
+toList :: Foldable t => t a -> [a]
+#ifdef __GLASGOW_HASKELL__
+toList t = build (\ c n -> foldr c n t)
+#else
+toList = foldr (:) []
+#endif
+
+-- | The concatenation of all the elements of a container of lists.
+concat :: Foldable t => t [a] -> [a]
+concat = fold
+
+-- | Map a function over all the elements of a container and concatenate
+-- the resulting lists.
+concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
+concatMap = foldMap
+
+-- | 'and' returns the conjunction of a container of Bools.  For the
+-- result to be 'True', the container must be finite; 'False', however,
+-- results from a 'False' value finitely far from the left end.
+and :: Foldable t => t Bool -> Bool
+and = getAll . foldMap All
+
+-- | 'or' returns the disjunction of a container of Bools.  For the
+-- result to be 'False', the container must be finite; 'True', however,
+-- results from a 'True' value finitely far from the left end.
+or :: Foldable t => t Bool -> Bool
+or = getAny . foldMap Any
+
+-- | Determines whether any element of the structure satisfies the predicate.
+any :: Foldable t => (a -> Bool) -> t a -> Bool
+any p = getAny . foldMap (Any . p)
+
+-- | Determines whether all elements of the structure satisfy the predicate.
+all :: Foldable t => (a -> Bool) -> t a -> Bool
+all p = getAll . foldMap (All . p)
+
+-- | The 'sum' function computes the sum of the numbers of a structure.
+sum :: (Foldable t, Num a) => t a -> a
+sum = getSum . foldMap Sum
+
+-- | The 'product' function computes the product of the numbers of a structure.
+product :: (Foldable t, Num a) => t a -> a
+product = getProduct . foldMap Product
+
+-- | The largest element of a non-empty structure.
+maximum :: (Foldable t, Ord a) => t a -> a
+maximum = foldr1 max
+
+-- | The largest element of a non-empty structure with respect to the
+-- given comparison function.
+maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
+maximumBy cmp = foldr1 max'
+  where max' x y = case cmp x y of
+                        GT -> x
+                        _  -> y
+
+-- | The least element of a non-empty structure.
+minimum :: (Foldable t, Ord a) => t a -> a
+minimum = foldr1 min
+
+-- | The least element of a non-empty structure with respect to the
+-- given comparison function.
+minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
+minimumBy cmp = foldr1 min'
+  where min' x y = case cmp x y of
+                        GT -> y
+                        _  -> x
+
+-- | Does the element occur in the structure?
+elem :: (Foldable t, Eq a) => a -> t a -> Bool
+elem = any . (==)
+
+-- | 'notElem' is the negation of 'elem'.
+notElem :: (Foldable t, Eq a) => a -> t a -> Bool
+notElem x = not . elem x
+
+-- | The 'find' function takes a predicate and a structure and returns
+-- the leftmost element of the structure matching the predicate, or
+-- 'Nothing' if there is no such element.
+find :: Foldable t => (a -> Bool) -> t a -> Maybe a
+find p = listToMaybe . concatMap (\ x -> if p x then [x] else [])
hunk ./lib/applicative/Data/Traversable.hs 1
+-----------------------------------------------------------------------------
+-- |
+-- Module      :  Data.Traversable
+-- Copyright   :  Conor McBride and Ross Paterson 2005
+-- License     :  BSD-style (see the LICENSE file in the distribution)
+--
+-- Maintainer  :  ross@soi.city.ac.uk
+-- Stability   :  experimental
+-- Portability :  portable
+--
+-- Class of data structures that can be traversed from left to right,
+-- performing an action on each element.
+--
+-- See also
+--
+--  * /Applicative Programming with Effects/,
+--    by Conor McBride and Ross Paterson, online at
+--    <http://www.soi.city.ac.uk/~ross/papers/Applicative.html>.
+--
+--  * /The Essence of the Iterator Pattern/,
+--    by Jeremy Gibbons and Bruno Oliveira,
+--    in /Mathematically-Structured Functional Programming/, 2006, and online at
+--    <http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/#iterator>.
+--
+-- Note that the functions 'mapM' and 'sequence' generalize "Prelude"
+-- functions of the same names from lists to any 'Traversable' functor.
+-- To avoid ambiguity, either import the "Prelude" hiding these names
+-- or qualify uses of these function names with an alias for this module.
+
+module Data.Traversable (
+        Traversable(..),
+        for,
+        forM,
+        fmapDefault,
+        foldMapDefault,
+        ) where
+
+import Prelude hiding (mapM, sequence, foldr)
+import qualified Prelude (mapM, foldr)
+import Control.Applicative
+import Data.Foldable (Foldable())
+import Data.Monoid (Monoid)
+
+-- | Functors representing data structures that can be traversed from
+-- left to right.
+--
+-- Minimal complete definition: 'traverse' or 'sequenceA'.
+--
+-- Instances are similar to 'Functor', e.g. given a data type
+--
+-- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
+--
+-- a suitable instance would be
+--
+-- > instance Traversable Tree
+-- >    traverse f Empty = pure Empty
+-- >    traverse f (Leaf x) = Leaf <$> f x
+-- >    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r
+--
+-- This is suitable even for abstract types, as the laws for '<*>'
+-- imply a form of associativity.
+--
+-- The superclass instances should satisfy the following:
+--
+--  * In the 'Functor' instance, 'fmap' should be equivalent to traversal
+--    with the identity applicative functor ('fmapDefault').
+--
+--  * In the 'Foldable' instance, 'Data.Foldable.foldMap' should be
+--    equivalent to traversal with a constant applicative functor
+--    ('foldMapDefault').
+--
+class (Functor t, Foldable t) => Traversable t where
+        -- | Map each element of a structure to an action, evaluate
+        -- these actions from left to right, and collect the results.
+        traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
+        traverse f = sequenceA . fmap f
+
+        -- | Evaluate each action in the structure from left to right,
+        -- and collect the results.
+        sequenceA :: Applicative f => t (f a) -> f (t a)
+        sequenceA = traverse id
+
+        -- | Map each element of a structure to a monadic action, evaluate
+        -- these actions from left to right, and collect the results.
+        mapM :: Monad m => (a -> m b) -> t a -> m (t b)
+        mapM f = unwrapMonad . traverse (WrapMonad . f)
+
+        -- | Evaluate each monadic action in the structure from left to right,
+        -- and collect the results.
+        sequence :: Monad m => t (m a) -> m (t a)
+        sequence = mapM id
+
+-- instances for Prelude types
+
+instance Traversable Maybe where
+        traverse f Nothing = pure Nothing
+        traverse f (Just x) = Just <$> f x
+
+instance Traversable [] where
+        traverse f = Prelude.foldr cons_f (pure [])
+          where cons_f x ys = (:) <$> f x <*> ys
+
+        mapM = Prelude.mapM
+
+-- general functions
+
+-- | 'for' is 'traverse' with its arguments flipped.
+for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)
+{-# INLINE for #-}
+for = flip traverse
+
+-- | 'forM' is 'mapM' with its arguments flipped.
+forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b)
+{-# INLINE forM #-}
+forM = flip mapM
+
+-- | This function may be used as a value for `fmap` in a `Functor` instance.
+fmapDefault :: Traversable t => (a -> b) -> t a -> t b
+fmapDefault f = getId . traverse (Id . f)
+
+-- | This function may be used as a value for `Data.Foldable.foldMap`
+-- in a `Foldable` instance.
+foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
+foldMapDefault f = getConst . traverse (Const . f)
+
+-- local instances
+
+newtype Id a = Id { getId :: a }
+
+instance Functor Id where
+        fmap f (Id x) = Id (f x)
+
+instance Applicative Id where
+        pure = Id
+        Id f <*> Id x = Id (f x)
hunk ./lib/applicative/applicative.cabal 1
+Name: applicative
+Version: 1.0
+Exposed-Modules: Control.Applicative,
+                 Control.Arrow,
+                 Control.Category,
+                 Data.Foldable,
+                 Data.Traversable
+
hunk ./lib/base/base.cabal 60
-                 System
-                 Text.Show.Functions
+                 Control.Monad.Fix,
+                 Data.Function,
+                 System,
+                 Text.Show.Functions,