C regex library bits have moved to the regex-posix package

[haskell-directory.git] / Data / Traversable.hs

diff --git a/Data/Traversable.hs b/Data/Traversable.hs
index f8fca1b..6754094 100644 (file)
--- a/Data/Traversable.hs
+++ b/Data/Traversable.hs
@@ -10,9 +10,16 @@
 --
 -- Class of data structures that can be traversed from left to right.
 --
--- See also /Applicative Programming with Effects/,
--- by Conor McBride and Ross Paterson, online at
--- <http://www.soi.city.ac.uk/~ross/papers/Applicative.html>.
+-- 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>.
 
 module Data.Traversable (
        Traversable(..),
@@ -20,10 +27,10 @@ module Data.Traversable (
        foldMapDefault,
        ) where
 
-import Prelude hiding (mapM, sequence)
-import qualified Prelude (mapM)
+import Prelude hiding (mapM, sequence, foldr)
+import qualified Prelude (mapM, foldr)
 import Control.Applicative
-import Data.Foldable (Foldable)
+import Data.Foldable (Foldable())
 import Data.Monoid (Monoid)
 import Data.Array
 
@@ -46,6 +53,15 @@ import Data.Array
 -- 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.
@@ -74,7 +90,7 @@ instance Traversable Maybe where
        traverse f (Just x) = Just <$> f x
 
 instance Traversable [] where
-       traverse f = foldr cons_f (pure [])
+       traverse f = Prelude.foldr cons_f (pure [])
          where cons_f x ys = (:) <$> f x <*> ys
 
        mapM = Prelude.mapM