Data/Traversable.hs

   1 -----------------------------------------------------------------------------
   2 -- |
   3 -- Module      :  Data.Traversable
   4 -- Copyright   :  Conor McBride and Ross Paterson 2005
   5 -- License     :  BSD-style (see the LICENSE file in the distribution)
   6 --
   7 -- Maintainer  :  ross@soi.city.ac.uk
   8 -- Stability   :  experimental
   9 -- Portability :  portable
  10 --
  11 -- Class of data structures that can be traversed from left to right,
  12 -- performing an action on each element.
  13 --
  14 -- See also
  15 --
  16 --  * /Applicative Programming with Effects/,
  17 --    by Conor McBride and Ross Paterson, online at
  18 --    <http://www.soi.city.ac.uk/~ross/papers/Applicative.html>.
  19 --
  20 --  * /The Essence of the Iterator Pattern/,
  21 --    by Jeremy Gibbons and Bruno Oliveira,
  22 --    in /Mathematically-Structured Functional Programming/, 2006, and online at
  23 --    <http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/#iterator>.
  24 --
  25 -- Note that the functions 'mapM' and 'sequence' generalize "Prelude"
  26 -- functions of the same names from lists to any 'Traversable' functor.
  27 -- To avoid ambiguity, either import the "Prelude" hiding these names
  28 -- or qualify uses of these function names with an alias for this module.
  29
  30 module Data.Traversable (
  31         Traversable(..),
  32         fmapDefault,
  33         foldMapDefault,
  34         ) where
  35
  36 import Prelude hiding (mapM, sequence, foldr)
  37 import qualified Prelude (mapM, foldr)
  38 import Control.Applicative
  39 import Data.Foldable (Foldable())
  40 import Data.Monoid (Monoid)
  41 import Data.Array
  42
  43 -- | Functors representing data structures that can be traversed from
  44 -- left to right.
  45 --
  46 -- Minimal complete definition: 'traverse' or 'sequenceA'.
  47 --
  48 -- Instances are similar to 'Functor', e.g. given a data type
  49 --
  50 -- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
  51 --
  52 -- a suitable instance would be
  53 --
  54 -- > instance Traversable Tree
  55 -- >    traverse f Empty = pure Empty
  56 -- >    traverse f (Leaf x) = Leaf <$> f x
  57 -- >    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r
  58 --
  59 -- This is suitable even for abstract types, as the laws for '<*>'
  60 -- imply a form of associativity.
  61 --
  62 -- The superclass instances should satisfy the following:
  63 --
  64 --  * In the 'Functor' instance, 'fmap' should be equivalent to traversal
  65 --    with the identity applicative functor ('fmapDefault').
  66 --
  67 --  * In the 'Foldable' instance, 'Data.Foldable.foldMap' should be
  68 --    equivalent to traversal with a constant applicative functor
  69 --    ('foldMapDefault').
  70 --
  71 class (Functor t, Foldable t) => Traversable t where
  72         -- | Map each element of a structure to an action, evaluate
  73         -- these actions from left to right, and collect the results.
  74         traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
  75         traverse f = sequenceA . fmap f
  76
  77         -- | Evaluate each action in the structure from left to right,
  78         -- and collect the results.
  79         sequenceA :: Applicative f => t (f a) -> f (t a)
  80         sequenceA = traverse id
  81
  82         -- | Map each element of a structure to an monadic action, evaluate
  83         -- these actions from left to right, and collect the results.
  84         mapM :: Monad m => (a -> m b) -> t a -> m (t b)
  85         mapM f = unwrapMonad . traverse (WrapMonad . f)
  86
  87         -- | Evaluate each monadic action in the structure from left to right,
  88         -- and collect the results.
  89         sequence :: Monad m => t (m a) -> m (t a)
  90         sequence = mapM id
  91
  92 -- instances for Prelude types
  93
  94 instance Traversable Maybe where
  95         traverse f Nothing = pure Nothing
  96         traverse f (Just x) = Just <$> f x
  97
  98 instance Traversable [] where
  99         traverse f = Prelude.foldr cons_f (pure [])
 100           where cons_f x ys = (:) <$> f x <*> ys
 101
 102         mapM = Prelude.mapM
 103
 104 instance Ix i => Traversable (Array i) where
 105         traverse f arr = listArray (bounds arr) <$> traverse f (elems arr)
 106
 107 -- general functions
 108
 109 -- | This function may be used as a value for `fmap` in a `Functor` instance.
 110 fmapDefault :: Traversable t => (a -> b) -> t a -> t b
 111 fmapDefault f = getId . traverse (Id . f)
 112
 113 -- | This function may be used as a value for `Data.Foldable.foldMap`
 114 -- in a `Foldable` instance.
 115 foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
 116 foldMapDefault f = getConst . traverse (Const . f)
 117
 118 -- local instances
 119
 120 newtype Id a = Id { getId :: a }
 121
 122 instance Functor Id where
 123         fmap f (Id x) = Id (f x)
 124
 125 instance Applicative Id where
 126         pure = Id
 127         Id f <*> Id x = Id (f x)