Week 8, Ch 12, Monoids
Ch 12: Monoids
Copyright By PowCoder代写 加微信 powcoder
University of the Fraser Valley
COMP 481: Functional and Logic Programming
• Wrapping an Existing Type Into a
• Using `newtype` to Make Type Class Instances
• On `newtype` and Laziness
• Type Keywords Review
• Getting Back to Monoids
• The Monoid Laws
• A Few Monoids
• Multiply and Sum
• Any and All
• The Ordering Monoid
• `Maybe` the Monoid
• Folding with Monoids
Programming
There are two paradigms in programming that contrast
each other, which you now know:
• procedural programming
• uses functions and stores data within arrays
• object-oriented programming
• arranges data as fields within a hierarchy of objects
Functional programming is very much like procedural
programming, but to an extreme.
• arranging data into arrays allows for fast access to it during execution
• access to data within a hierarchy of objects can be slow,
because of stepping through pointers to get to it
Haskell has efficiency of arranging data apart from objects.
• the way we have used types up to this point follows more
like object-oriented programming design
• record syntax is not as efficient as another typing design we will learn
(Unity 3D is in the process of implementing an Entity Component
System for Data Oriented Technology Stack to pack data into arrays)
— Wrapping an Existing Type Into a —
Behaviours
We have seen in the last chapter the two ways that lists can
implement the `<*>` operation:
1. with every nested function in the first list applied to every possible
element of the second list
2. with `ZipList` each nested function of the first list applied to its
corresponding element of the second list
The issue with `ZipList` is that it is implemented with the
`data` keyword:
data ZipList a = ZipList { getZipList :: [a] }
For object-oriented-like design, Haskell wraps and unwraps
the nested `a` and `[a]` types each time in use of `ZipList`.
• this is not as efficient as it could be
Haskell also has the `newtype` keyword for defining types so
that Haskell treats the definition with its underlying type.
• the efficiency is tailored specifically to be used
with implementations of functors and applicatives
• this is because the `newtype` keyword
only allows exactly one constructor
• also, the constructor can have up to only one field
(in a record, if desired)
newtype with Functor Example (Simranjit Singh)
newtype Score a b =
Score { getScore :: (String, b) }
deriving Show
instance Functor (Score c) where
fmap f (Score (x, y)) = Score (x,f y)
— examples
p1 = Score (“James”, 1)
p2 = Score (“Anna”, 4)
p3 = Score (“Drew”, 8)
ghci> getScore p1
(“James”, 1)
ghci> (+3) <$> p1
Score {getScore = (“James”,4)}
— Using `newtype` to Make Type Class Instances —
Parameters
To implement functor on a constructor with two
parameters so that functions `fmap` on its first parameter:
newtype Pair b a = Pair { getPair :: (a, b) } deriving (Show)
instance Functor (Pair b) where
fmap g (Pair (x, y)) = Pair (g x, y)
• note the swap in the constructor for `Pair b a` and the
record `getPair :: (a, b)`
Parameters
More parameters can be involved, and this time suppose
we wanted to use the function on the second parameter:
newtype Triple a c b = Triple { getTriple :: (a, b, c) } deriving
instance Functor (Triple a c) where
fmap g (Triple (x, y, z)) = Triple (x, g y, z)
Try `fmap` on a `Pair` and a `Triple` with some function. For
ghci> getPair (fmap reverse (Pair (“london calling”, 3)))
(“gnillac nodnol”,3)
There is no change in the internal representation for
Haskell with `Pair` or `Triple`.
• they only allow us to implement another way to use `fmap`
(as an example) with pairs and 3-tuples.
• we could create yet more `newtype` and implementations
for pairs and 3-tuples if we wanted
— On `newtype` and Laziness —
Haskell being lazy means it will only evaluate expressions
until it absolutely must (e.g.: to print a result to output).
• only calculations that are necessary are performed, and no others
• trying to evaluate an `undefined` value (a special keyword)
will make Haskell throw an exception
ghci> undefined
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
error, called at libraries\base\GHC\Err.hs:75:14 in base:GHC.Err
undefined, called at
however, notice how `undefined` can go unevaluated just
fine when other calculations are the focus:
ghci> head [1,2,3,undefined,5,6]
`newtype` allows structures to be more lazy than `data`
because there is only exactly one constructor.
• Haskell must evaluate the parameters to determine which value
constructor implementation matches with use of `data`
• the `newtype` value constructor implementation must only have the
one version, so evaluation can be deferred
data CoolBool = CoolBool { getCoolBool :: Bool } deriving (Show)
helloMe :: CoolBool -> String
helloMe (CoolBool _) = “hello!”
helloMe undefined
*** Exception: Prelude.undefined
Demonstration
of newtype
Exit interactive session and reenter to define the next
newtype CoolBool = CoolBool { getCoolBool :: Bool } deriving
helloMe :: CoolBool -> String
helloMe (CoolBool _) = “hello!”
ghci> helloMe undefined
• the `(CoolBool _)` did not need to evaluate `undefined`
Altogether, the difference between `data` and `newtype` is:
• make completely new types with `data`
• make other versions of types with `newtype`
— Type Keywords Review —
The `type` keyword is just used to create synonyms.
• e.g.: `type IntList = [Int]`
• it makes descriptions more readable, like function signatures
ghci> ([1,2,3] :: IntList) ++ ([1,2,3] :: [Int])
[1,2,3,1,2,3]
• recall we created another name for the list association
`[(String,String)]` as a `PhoneBook`
Implementations
The `newtype` will create a completely separate type:
newtype CharList = CharList { getCharList :: [Char] } deriving
• `CharList` values cannot have `++` applied with
other `[Char]` values because the two types are different
• two `CharList` values cannot be concatenated with `++`, since `++` is
not even implemented for `CharList`
• it is possible to convert from `CharList` to `[Char]` apply `++` and convert back
• `newtype` record syntax provides the field `getCharList` as conversion function
• none of the `[Char]` instance implementations are inherited to
`CharList` for any of the involved type classes
• you will need to derive or manually write them
Three Kinds of
Implementation
Consider using `newtype` over `data` when you only have
one value constructor.
The three canonical rules to follow are as follows:
1. If you only need more readability—the `type` synonym will do
2. If an already existing type needs to be wrapped and implemented
as an instance of a type class—the `newtype` keyword will do
3. If a completely new type is needed—the `data` keyword will do
— Getting Back to Monoids —
Type Class
So we can implement instances of different type classes.
We have seen and learned of their usefulness:
• `Eq`, `Ord`, `Functor`, `Applicative`, etc.
There is yet another type class that is fairly involved and
powerful, called `Monoid`:
• a `Monoid` describes a combination of
• a binary function
• with an identity value
An example:
ghci> [1,2,3] ++ []
ghci> [] ++ [1,2,3]
• above, the binary function is `++`, and the identity element is `[]`
• notice the identity element leaves the other operand unchanged,
regardless of which side it is applied
Can you think of other examples?
`Monoid` implementation is as follows:
class Monoid m where
mempty :: m
mappend :: m -> m -> m
mconcat :: [m] -> m
mconcat = foldr mappend mempty
• `mempty` describes the polymorphic constant that should act as the
identity element
• `mappend` is a misnomer, and should be some associative binary
• `mconcat` is implemented by default to take a list and forms one
monoid value using `mappend` between its elements
• `mconcat` can have its default implementation changed depending on `m`
— The Monoid Laws —
The following three laws involving `Monoid` are not
implemented in Haskell by default…
— left identity —
mempty `mappend` x = x
— right identity —
x `mappend` mempty = x
— associativity —
(x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)
…so you will need to check your own implementations
when you create instances!
Associativity
The last law requires a `Monoid` instance to ensure order
of evaluation of `mappend` operations do not matter:
• once we implement last law, we can get away with writing
x `mappend` y `mappend` z
Part of the reason we want to guarantee such laws hold:
• we then do not have to change our understanding of a
computational result based on order of operations
— A Few Monoids —
Implementing a
We saw the example of `[]` and `++` function as a `Monoid`
instance, which has the following implementation:
instance Monoid [a] where
mempty = []
mappend = (++)
• the implementation of an instance of `Monoid` requires a concrete
type, so note the use of `[a]` and not `[]`
• (requirement since version `build-4.11.0.0` for `Semigroup` to be a
superclass of a `Monoid`, but we leave this for a bit later)
ghci> [1,2,3] `mappend` [4,5,6]
[1,2,3,4,5,6]
ghci> (“one” `mappend` “two”) `mappend` “three”
“onetwothree”
ghci> “one” `mappend` (“two” `mappend` “three”)
“onetwothree”
ghci> “one” `mappend` “two” `mappend` “three”
“onetwothree”
ghci> “ping” `mappend` mempty
ghci> mconcat [[1,2],[3,6],[9]]
[1,2,3,6,9]
ghci> mempty :: [a]
Details on
(monoid behaviour)
• we needed a type annotation in the last expression, because Haskell
would not be able to infer any type for it without giving `:: [a]`
• it is more general to write `[a]` than `[Int]` or `[String]`,
since lists could contain all its elements of any one type
• the expression `mconcat [[1,2],[3,6],[9]]` demonstrates
how `++` is used between elements
The above examples demonstrated how `++` and `[]`
satisfy the associativity and identity laws.
Commutativity
• there is no requirement to satisfy any commutativity laws
• swapping order of elements in a `++` operation will be different
• ghci> “tick” ++ “tock”
• “ticktock“
• ghci> “tock” ++ “tick”
• “tocktick”
• other monoids could be commutative over `mappend`:
can you think of one?
• to be commutative, the result of the binary operation must be
the same, regardless of order,
for every pair of possible operands
— Multiply and Sum —
Understand that both
• `+` and `0` is a monoid
• as well as `*` and `1` are a different monoid.
Recap: we can treat the same kind of thing with different
implementations of type classes by repurposing them with `newtype`.
We want to see the different implementations for the two
monoids, but the Haskell language has had an update since
version `base-4.11.0.0`:
• any `Monoid` must also be a `Semigroup` instance
• `Semigroup` means that the associativity should be implemented
and expected before implementing `Monoid`
We start with `Multiply`:
newtype Multiply a = Multiply { getMultiply :: a }
deriving (Eq, Ord, Read, Show, Bounded)
instance Num a => Semigroup (Multiply a) where
(Multiply x) <> (Multiply y) = Multiply (x * y)
instance (Num a) => Monoid (Multiply a) where
mempty = Multiply 1
mappend = (<>)
Now we can try the following operations using `<>`:
ghci> getMultiply $ Multiply 3 <> Multiply 9
ghci> getMultiply $ Multiply 3 <> mempty
ghci> getMultiply $ Multiply 3 <> Multiply 4 <> Multiply 2
ghci> getMultiply . mconcat . map Multiply $ [3,4,2]
`Sum` as a
Practice implementing `Sum` similarly to `Multiply`.
You will need to think about what the identity element is
that corresponds to the operation of binary addition.
• once you get it implemented, test it with the following:
ghci> getSum $ Sum 2 <> Sum 9
ghci> getSum $ mempty <> Sum 3
ghci> getSum . mconcat . map Sum $ [1, 2, 3]
— Any and All —
We can work with `Bool` values and its common operations
for our own monoids as well (like operators OR and AND).
• convince yourself of the `mempty` definition for the implementation
where `<>` takes on the binary operation of OR:
newtype Any = Any { getAny :: Bool }
deriving (Eq, Ord, Read, Show, Bounded)
instance Semigroup (Any) where
(Any x) <> (Any y) = Any (x || y)
instance Monoid Any where
mempty = Any False
mappend = (<>)
And give the following a try:
ghci> getAny $ Any True <> Any False
ghci> getAny $ mempty <> Any True
ghci> getAny . mconcat . map Any $ [False, False, False, True]
ghci> getAny $ mempty <> mempty
Can you implement another `<>` for the AND operator?
• it should have the following results:
ghci> getAll $ mempty <> All True
ghci> getAll $ mempty <> All False
ghci> getAll . mconcat . map All $ [True, True, True]
ghci> getAll . mconcat . map All $ [True, True, False]
— The Ordering Monoid —
The following slides are merely a demonstration of how to
mix restrictions on comparing between `String` values.
• we have the three possible results of comparing integers:
ghci> 1 `compare` 2
ghci> 2 `compare` 2
ghci> 3 `compare` 2
• (could implement for `Char` as well)
Although it may not seem as if it would be possible to
define `Monoid` behaviour over the three ordering values,
it is already done so:
instance Monoid Ordering where
mempty = EQ
LT `mappend` _ = LT
EQ `mappend` y = y
GT `mappend` _ = GT
• you can check that the `mempty` acts like the identity on the other
ordering values
Comparison
The following might be a way we want to compare strings:
lengthCompare :: String -> String -> Ordering
lengthCompare x y =
(length x `compare` length y) `mappend`
(x `compare` y)
• the above will compare whether the first string `x`
is shorter or larger and return that result
• but if the two strings `x` and `y` are the same length,
they will be further compared alphabetically
ghci> lengthCompare “zen” “ants”
ghci> lengthCompare “zen” “ant”
Comparison
We might want to design an a more refined scheme.
Further refine comparison to check between `x` and `y` by
number of vowels before alphabetic comparison:
lengthCompare :: String -> String -> Ordering
lengthCompare x y =
(length x `compare` length y) `mappend`
(vowels x `compare` vowels y) `mappend`
(x `compare` y)
where vowels = length . filter (`elem` “aeiou”)
See how the above refinement of ordering affects results
with use of `lengthCompare`:
ghci> lengthCompare “zen” “anna”
ghci> lengthCompare “zen” “ana”
ghci> lengthCompare “zen” “ann”
This is only one example of how to apply `Monoids` in a
non-trivial way toward creating your own orderings.
— `Maybe` the Monoid —
Already implemented is the use of `Maybe` as a monoid
(and a semigroup).
• the nested elements can also be instances of `Monoid` and
`Semigroup`, so the implementations look like the following:
instance Semigroup a => Semigroup (Maybe a) where
(Just x) <> Nothing = Just x
Nothing <> (Just y) = Just y
(Just x) <> (Just y) = Just (x <> y)
instance Monoid a => Monoid (Maybe a) where
mempty = Nothing
mappend = (<>)
• notice how `x <> y` nests in right evaluation of a `Just` element
Give the following a try:
ghci> Nothing <> Just “andy”
Just “andy”
ghci> Just LT <> Nothing
ghci> Just (Sum 3) <> Just (Sum 4)
Just (Sum {getSum = 7})
• we can use `Maybe` values with nested values for types previously
defined to work with `Monoid` on their own, such as `Sum`
The above implementation of `Maybe` is very useful:
• for working with binary computations in the nested elements when
we do not care that some of the `Maybe` values are `Nothing`
• since they are absorbed during calculations as an identity
And `Maybe` values with nested element not a monoid?
• grab the values without worrying about nested operations
Create `newtype First` as implementation of `Maybe`:
newtype First a = First { getFirst :: Maybe a }
deriving (Eq, Ord, Read, Show)
instance Semigroup (First a) where
First (Just x) <> _ = First (Just x)
First Nothing <> x = x
instance Monoid (First a) where
mempty = First Nothing
mappend = (<>)
`First` as
This way, we can work with the first element that is not
`First Nothing` given some operations with `<>`:
ghci> getFirst $ First (Just ‘a’) <> First (Just ‘b’)
ghci> getFirst $ First Nothing <> First (Just ‘b’)
ghci> getFirst $ First (Just ‘a’) <> First Nothing
ghci> getFirst . mconcat . map First $ [Nothing, Just 9, Just 10]
The `Data.Monoid` module already has a `Last` data type
implemented that works similarly
It always evaluates to the rightmost non-`Nothing` value:
ghci> import Data.Monoid as M
ghci> getLast . mconcat . map Last $ [Nothing, Just 9, Just 10]
• note that Haskell cn imply the package prefix for unique names
— Folding with Monoids —
The `foldr` function:
• used to have different version found in the `Data.Foldable` module
• allows us similar operations on other types that act similar to lists
• it is now just implemented into the `Prelude` default version
• the default only used to work on lists
Trees are analog to lists where we could practice folding:
• observe we can fold over anything deemed instance of `Foldable`
ghci> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
Just a quick reminder demo:
ghci> foldr (*) 1 [1,2,3]
In this example, the first parameter is a binary operation:
• the second parameter is the starting accumulator value
• the third parameter is the list we want to fold
A few more examples:
ghci> foldl (+) 2 (Just 9)
ghci> foldl (||) False (Just True)
When folding right, whatever function we pass must have:
• its first parameter as the next input list element
• its second parameter as the accumulator
Something that is a bit weird, but works, because of
monoid behaviour:
ghci> foldl (||) False (Nothing)
ghci> foldl (||) True (Nothing)
ghci> foldl (&&) False (Nothing)
ghci> foldl (&&) True (Nothing)
• the above I just remember as the fold as acting on the identity
We make another type an instance of `Foldable` with the
tree data structure we had previously defined:
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)
To make something foldable, we must implement a
function called `foldMap`, which is described with the type:
foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m
• the above can be broken down into:
• `(a -> m)` as a function for input nested element type `a` to an
element that can be operated on as a monoid `m`
• the data structure `t a` we would like to fold
• the final result of the fold `m` for one monoid value
Implementing
for `Tree`
We need to implement `foldMap` function for our trees:
instance Foldable Tree where
foldMap g EmptyTree = mempty
foldMap g (Node x l r) =
foldMap g l <>
g x <>
foldMap g r
• the above implements the fold as an in-order traversal
• a tree that is empty just evaluates to the monoid `mempty` value
• this way, when the recursive `foldMap` reaches empty leaf nodes, they
resolve as identity oper
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com