[project @ 2005-02-26 12:14:54 by panne]
[packages/random.git] / Data / Monoid.hs
1 -----------------------------------------------------------------------------
2 -- |
3 -- Module : Data.Monoid
4 -- Copyright : (c) Andy Gill 2001,
5 -- (c) Oregon Graduate Institute of Science and Technology, 2001
6 -- License : BSD-style (see the file libraries/base/LICENSE)
7 --
8 -- Maintainer : libraries@haskell.org
9 -- Stability : experimental
10 -- Portability : non-portable (requires extended type classes)
11 --
12 -- Declaration of the Monoid class, and instances for list and functions.
13 --
14 -- Inspired by the paper
15 -- /Functional Programming with Overloading and
16 -- Higher-Order Polymorphism/,
17 -- Mark P Jones (<http://www.cse.ogi.edu/~mpj/>)
18 -- Advanced School of Functional Programming, 1995.
19 -----------------------------------------------------------------------------
20
21 module Data.Monoid (
22 Monoid(..)
23 ) where
24
25 import Prelude
26 import Data.Map ( Map )
27 import qualified Data.Map as Map hiding ( Map )
28 import Data.IntMap ( IntMap )
29 import qualified Data.IntMap as IntMap hiding ( IntMap )
30 import Data.Set ( Set )
31 import qualified Data.Set as Set hiding ( Set )
32 import Data.IntSet ( IntSet )
33 import qualified Data.IntSet as IntSet hiding ( IntSet )
34
35 -- ---------------------------------------------------------------------------
36 -- | The monoid class.
37 -- A minimal complete definition must supply 'mempty' and 'mappend',
38 -- and these should satisfy the monoid laws.
39
40 class Monoid a where
41 mempty :: a
42 -- ^ Identity of 'mappend'
43 mappend :: a -> a -> a
44 -- ^ An associative operation
45 mconcat :: [a] -> a
46
47 -- ^ Fold a list using the monoid.
48 -- For most types, the default definition for 'mconcat' will be
49 -- used, but the function is included in the class definition so
50 -- that an optimized version can be provided for specific types.
51
52 mconcat = foldr mappend mempty
53
54 -- Monoid instances.
55
56 instance Monoid [a] where
57 mempty = []
58 mappend = (++)
59
60 instance Monoid (a -> a) where
61 mempty = id
62 mappend = (.)
63
64 instance Monoid () where
65 -- Should it be strict?
66 mempty = ()
67 _ `mappend` _ = ()
68 mconcat _ = ()
69
70 instance (Monoid a, Monoid b) => Monoid (a,b) where
71 mempty = (mempty, mempty)
72 (a1,b1) `mappend` (a2,b2) =
73 (a1 `mappend` a2, b1 `mappend` b2)
74
75 instance (Monoid a, Monoid b, Monoid c) => Monoid (a,b,c) where
76 mempty = (mempty, mempty, mempty)
77 (a1,b1,c1) `mappend` (a2,b2,c2) =
78 (a1 `mappend` a2, b1 `mappend` b2, c1 `mappend` c2)
79
80 instance (Monoid a, Monoid b, Monoid c, Monoid d) => Monoid (a,b,c,d) where
81 mempty = (mempty, mempty, mempty, mempty)
82 (a1,b1,c1,d1) `mappend` (a2,b2,c2,d2) =
83 (a1 `mappend` a2, b1 `mappend` b2,
84 c1 `mappend` c2, d1 `mappend` d2)
85
86 instance (Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) =>
87 Monoid (a,b,c,d,e) where
88 mempty = (mempty, mempty, mempty, mempty, mempty)
89 (a1,b1,c1,d1,e1) `mappend` (a2,b2,c2,d2,e2) =
90 (a1 `mappend` a2, b1 `mappend` b2, c1 `mappend` c2,
91 d1 `mappend` d2, e1 `mappend` e2)
92
93 -- lexicographical ordering
94 instance Monoid Ordering where
95 mempty = EQ
96 LT `mappend` _ = LT
97 EQ `mappend` y = y
98 GT `mappend` _ = GT
99
100 instance (Ord k) => Monoid (Map k v) where
101 mempty = Map.empty
102 mappend = Map.union
103 mconcat = Map.unions
104
105 instance Ord a => Monoid (IntMap a) where
106 mempty = IntMap.empty
107 mappend = IntMap.union
108 mconcat = IntMap.unions
109
110 instance Ord a => Monoid (Set a) where
111 mempty = Set.empty
112 mappend = Set.union
113 mconcat = Set.unions
114
115 instance Monoid IntSet where
116 mempty = IntSet.empty
117 mappend = IntSet.union
118 mconcat = IntSet.unions