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