[学习笔记-Haskell」Chapter 12 MONOIDS

Chapter 12 MONOIDS

This chapter features another useful and fun type class: Monoid. This type class is for types whose values can be combined together with a binary operation.

Table of Contents1 Wrapping an Existing Type into a New Type1.1 Using newtype to Make Type Class Instances1.2 On newtype Laziness1.3 type vs. newtype vs. data2 About Those Monoids2.1 The Monoid Type Class2.2 The Monoid Laws3 Meet Some Monoids3.1 Lists Are Monoids3.2 Product and Sum3.3 Any and All3.4 The Ordering Monoid3.5 Maybe the Monoid4 Folding with Monoids

The newtype keyword in Haskell is made exactly for cases when we want to just take one type and wrap it in something to present it as another type. In the actual libraries, ZipList a is defined like this:

newtype ZipList a = ZipList { getZipList :: [a] }

we can newtype our tuple in such a way that the second type parameter represents the type of the first component in the tuple

newtype Paire b a = Paire { getPair :: (a,b) }

And now we can make it an instance of Functor so that the function is mapped over the first component.

instance Functor (Pair c) where    fmap f (Pair (x, y)) = Pair (f x, y)

ghci>getPair $ fmap (*100) (Pair (2,3))(200,3)ghci>getPair $ fmap reverse (Pair ("asdf",2))("fdsa",2)

The undefined value in Haskell represents an erroneous computation. If we try to evaluate it (that is, force Haskell to actually compute it) by printing it to the terminal, Haskell will throw a hissy fit (technically referred to as an exception):

ghci>undefined *** Exception: Prelude.undefined

Here's another example.

ghci>head  [32,1,undefined,32,undefined]32

This time,no exception,because Haskell is lazy,when we use head, we don't need to evaluate undefined which is not the "head".

Now consider the following type and a function:

data CoolBool = CoolBool { getCoolBool :: Bool }helloMe :: CoolBool -> StringhelloMe (CoolBool _) = "hello"

Let's test it.

ghci>helloMe (CoolBool True )"hello"ghci>helloMe undefined "*** Exception: Prelude.undefined

Why did this exception happen? Types defined with the data keyword can have multiple value constructors (even though CoolBool has only one). So in order to see if the value given to our function conforms to the (CoolBool _) pattern, Haskell must evaluate the value just enough to see which value constructor was used when we made the value. And when we try to evaluate an undefined value, even a little, an exception is thrown.

Instead of using data keyword, we use newtype.

newtype CoolBool = CoolBool { getCoolBool :: Bool }helloMe :: CoolBool -> StringhelloMe (CoolBool _) = "hello"

Let's test it again.

ghci>helloMe (CoolBool True )"hello"ghci>helloMe undefined "hello"

It worked! Hmmm, why is that? Well, as you’ve learned, when you use newtype, Haskell can internally represent the values of the new type in the same way as the original values. because Haskell knows that types made with the newtype keyword can have only one constructor, it doesn’t need to evaluate the value passed to the function to make sure that the value conforms to the (CoolBool _) pattern, because newtype types can have only one possible value constructor and one field!

At this point, you may be a bit confused about the differences between type, data, and newtype, so let’s review their uses. The type keyword is for making type synonyms. We use type synonyms when we want to make our type signatures more descriptive.

type IntList = [Int]

The newtype keyword is for taking existing types and wrapping them in new types, mostly so it’s easier to make them instances of certain type classes. Suppose we make the following newtype:

newtype CharList = CharList { getCharList :: [Char] }

We can’t use ++ to put together a CharList and a list of type [Char]. We can’t even use ++ to put together two CharList lists, because ++ works only on lists, and the CharList type isn’t a list, even though it could be said that CharList contains a list. We can, however, convert two CharLists to lists, ++ them, and then convert that back to a CharList. In practice, you can think of newtype declarations as data declarations that can have only one constructor and one field. If you catch yourself writ- ing such a data declaration, consider using newtype.

A monoid is made up of an associative binary function and a value that acts as an identity with respect to that function.For example,1 is the identity with respect to *, and [] is the identity with respect to ++. There are a lot of other monoids to be found in the world of Haskell, which is why the Monoid type class exists. Let’s see how the type class is defined:

class Monoid m where  mempty :: m  mappend :: m -> m -> m  mconcat :: [m] -> m  mconcat = foldr mappend mempty

First, we see that only concrete types can be made instances of Monoid, because the m in the type class definition doesn’t take any type parameters.

First,*mempty* represents the identity value for a particular monoid.

Next up, we have mappend, which, as you’ve probably guessed, is the bi- nary function. It takes two values of the same type and returns another value of that same type.

The last function in this type class definition is mconcat. It takes a list of monoid values and reduces them to a single value by using mappend between the list’s elements.

mempty `mappend` x = xx `mappend` mempty = x(x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)

instance Monoid [a] where  mempty = []  mappend = (++)

Notice that we wrote instance Monoid [a] and not instance Monoid [], because Monoid requires a concrete type for an instance.

ghci>[1,2,3] `mappend` mempty [1,2,3]ghci>mempty `mappend` [1,2,3][1,2,3]ghci>"hi" `mappend` ",John""hi,John"ghci>("1" `mappend ` "2") `mappend ` "3""123"ghci>"1" `mappend ` ("2" `mappend ` "3")"123"

We already examined one way for numbers to be considered monoids: Just let the binary function be * and the identity value be 1. Another way for numbers to be monoids is to have the binary function be + and the identity value be 0. With two equally valid ways for numbers to be monoids, which way do we choose? Well, we don’t have to pick. Remember that when there are several ways for some type to be an instance of the same type class, we can wrap that type in a newtype and then make the new type an instance of the type class in a different way. The Data.Monoid module exports two types for this: Product and Sum. Product is defined like this:

newtype Product a = Product { getProduct :: a}                  deriving (Eq, Ord, Read, Show, Bounded)

It's instance for Monoid goes something like this:

instance Num a => Monoid (Product a) where  mempty = Product 1  Product x `mappend` Product y = Product (x*y)

ghci> Product 3 `mappend` Product 5Product {getProduct = 15}ghci>getProduct $ Product 3 `mappend` Product 515ghci>getProduct . mconcat . map Product $ [3,4,5]60

Another type that can act like a monoid in two distinct but equally valid ways is Bool. The first way is to have the function ||, which represents a logical OR, act as the binary function along with False as the identity value. The Any newtype constructor is an instance of Monoid in this fashion. It’s defined like this.

newtype Any = Any { getAny :: Bool }            deriving (Eq, Ord, Read, Show, Bounded)

instance Monoid Any where  mempty = Any False  Any x `mappend` Any y = Any (x || y)

ghci>getAny $ Any True `mappend` Any FalseTrueghci>getAny $ Any False `mappend` Any FalseFalseghci>getAny $ mempty `mappend` memptyFalseghci>getAny $ mempty `mappend` Any TrueTrueghci>getAny $ mempty `mappend` Any FalseFalseghci>getAny . mconcat . map Any $ [False, False, False, True]True

Remember the Ordering type? It’s used as the result when comparing things, and it can have three values: LT, EQ, and GT,

ghci>1 `compare` 2LTghci>2 `compare` 2EQghci>3 `compare` 2GT

Ordering is instance of Monoid too.

instance Monoid Ordering where  mempty = EQ  LT `mappend` _ = LT  EQ `mappend` y = y  GT `mappend` _ = GT

ghci>LT `mappend` GTLTghci>GT `mappend` LTGTghci>mempty `mappend` LTLT

Okay, so how is this monoid useful? Here’s one way to write this:

lengthCompare :: String -> String -> OrderinglengthCompare x y = let a = length x `compare` length y                        b = x `compare` y                    in if a == EQ then b else a

But by employing our understanding of how Ordering is a monoid, we can rewrite this function in a much simpler manner:

lengthCompare :: String -> String -> OrderinglengthCompare x y = (length x `compare` length y) `mappend`                    (x `compare` y)

Let’s take a look at the various ways that Maybe a can be made an instance of Monoid and how those instances are useful. Here’s the instance declaration

instance Monoid a => Monoid (Maybe a) where  mempty = Nothing  Nothing `mappend` m = m  m `mappend` Nothing = m  Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

f we mappend two Just values, the contents of the Justs are mappended and then wrapped back in a Just. We can do this because the class constraint ensures that the type of what’s inside the Just is an in- stance of Monoid.

ghci>Nothing `mappend` Just "andy"Just "andy"ghci>Just LT `mappend` NothingJust LTghci>Just (Sum 3) `mappend` Just (Sum 4)Just (Sum {getSum = 7})

One of the more interesting ways to put monoids to work is to have them help us define folds over various data structures. So far, we’ve done folds over lists, but lists aren’t the only data structure that can be folded over. We can define folds over almost any data structure. Trees especially lend themselves well to folding.

Because there are so many data structures that work nicely with folds, the Foldable type class was introduced. Much like Functor is for things that can be mapped over, Foldable is for things that can be folded up!

It can be found in Data.Foldable, and because it exports functions whose names clash with the ones from the Prelude, it’s best imported qualified.

import qualified Data.Foldable as F

Let’s compare the types of Foldable’s foldr and foldr from Prelude to see how they differ

ghci>:t foldrfoldr :: (a -> b -> b) -> b -> [a] -> bghci>:t F.foldrF.foldr :: F.Foldable t => (a -> b -> b) -> b -> t a -> b

ghci>foldr (*) 1 [1,2,3]6ghci>F.foldr (*) 1 [1,2,3]6

Another data structures that support folds is the Maybe we all know and love!

ghci>F.foldr (+) 2 (Just 9)11ghci>F.foldr (||) False (Just True)Trueghci>foldr (+) 2 (Just 9)error...

Remember the tree data structure from Chapter 7?

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

One way to make a type constructor an instance of Foldable is to just di- rectly implement foldr for it. But another, often much easier way, is to im- plement the foldMap function, which is also a part of the Foldable type class. The foldMap function has the following type:

foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m

This is how we make Tree an instance of Foldable:

instance F.Foldable Tree where  foldMap f EmptyTree = mempty  foldMap f (Node x l r) = F.foldMap f l `mappend`                           f x           `mappend`                           F.foldMap f r

Date: 2013-01-26 19:49:12 CST