add advice on avoiding import ambiguities
[packages/random.git] / 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)