Faster filterF, filterNotByte
[packages/old-time.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 : portable
11 --
12 -- The Monoid class with various general-purpose instances.
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 Dual(..),
24 Endo(..),
25 All(..),
26 Any(..),
27 Sum(..),
28 Product(..)
29 ) where
30
31 import Prelude
32
33 -- ---------------------------------------------------------------------------
34 -- | The monoid class.
35 -- A minimal complete definition must supply 'mempty' and 'mappend',
36 -- and these should satisfy the monoid laws.
37
38 class Monoid a where
39 mempty :: a
40 -- ^ Identity of 'mappend'
41 mappend :: a -> a -> a
42 -- ^ An associative operation
43 mconcat :: [a] -> a
44
45 -- ^ Fold a list using the monoid.
46 -- For most types, the default definition for 'mconcat' will be
47 -- used, but the function is included in the class definition so
48 -- that an optimized version can be provided for specific types.
49
50 mconcat = foldr mappend mempty
51
52 -- Monoid instances.
53
54 instance Monoid [a] where
55 mempty = []
56 mappend = (++)
57
58 instance Monoid b => Monoid (a -> b) where
59 mempty _ = mempty
60 mappend f g x = f x `mappend` g x
61
62 instance Monoid () where
63 -- Should it be strict?
64 mempty = ()
65 _ `mappend` _ = ()
66 mconcat _ = ()
67
68 instance (Monoid a, Monoid b) => Monoid (a,b) where
69 mempty = (mempty, mempty)
70 (a1,b1) `mappend` (a2,b2) =
71 (a1 `mappend` a2, b1 `mappend` b2)
72
73 instance (Monoid a, Monoid b, Monoid c) => Monoid (a,b,c) where
74 mempty = (mempty, mempty, mempty)
75 (a1,b1,c1) `mappend` (a2,b2,c2) =
76 (a1 `mappend` a2, b1 `mappend` b2, c1 `mappend` c2)
77
78 instance (Monoid a, Monoid b, Monoid c, Monoid d) => Monoid (a,b,c,d) where
79 mempty = (mempty, mempty, mempty, mempty)
80 (a1,b1,c1,d1) `mappend` (a2,b2,c2,d2) =
81 (a1 `mappend` a2, b1 `mappend` b2,
82 c1 `mappend` c2, d1 `mappend` d2)
83
84 instance (Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) =>
85 Monoid (a,b,c,d,e) where
86 mempty = (mempty, mempty, mempty, mempty, mempty)
87 (a1,b1,c1,d1,e1) `mappend` (a2,b2,c2,d2,e2) =
88 (a1 `mappend` a2, b1 `mappend` b2, c1 `mappend` c2,
89 d1 `mappend` d2, e1 `mappend` e2)
90
91 -- lexicographical ordering
92 instance Monoid Ordering where
93 mempty = EQ
94 LT `mappend` _ = LT
95 EQ `mappend` y = y
96 GT `mappend` _ = GT
97
98 -- | The dual of a monoid, obtained by swapping the arguments of 'mappend'.
99 newtype Dual a = Dual { getDual :: a }
100
101 instance Monoid a => Monoid (Dual a) where
102 mempty = Dual mempty
103 Dual x `mappend` Dual y = Dual (y `mappend` x)
104
105 -- | The monoid of endomorphisms under composition.
106 newtype Endo a = Endo { appEndo :: a -> a }
107
108 instance Monoid (Endo a) where
109 mempty = Endo id
110 Endo f `mappend` Endo g = Endo (f . g)
111
112 -- | Boolean monoid under conjunction.
113 newtype All = All { getAll :: Bool }
114 deriving (Eq, Ord, Read, Show, Bounded)
115
116 instance Monoid All where
117 mempty = All True
118 All x `mappend` All y = All (x && y)
119
120 -- | Boolean monoid under disjunction.
121 newtype Any = Any { getAny :: Bool }
122 deriving (Eq, Ord, Read, Show, Bounded)
123
124 instance Monoid Any where
125 mempty = Any False
126 Any x `mappend` Any y = Any (x || y)
127
128 -- | Monoid under addition.
129 newtype Sum a = Sum { getSum :: a }
130 deriving (Eq, Ord, Read, Show, Bounded)
131
132 instance Num a => Monoid (Sum a) where
133 mempty = Sum 0
134 Sum x `mappend` Sum y = Sum (x + y)
135
136 -- | Monoid under multiplication.
137 newtype Product a = Product { getProduct :: a }
138 deriving (Eq, Ord, Read, Show, Bounded)
139
140 instance Num a => Monoid (Product a) where
141 mempty = Product 1
142 Product x `mappend` Product y = Product (x * y)