This gist and its comments are a way of working through an exercise problem found in Chapter 15 of the Haskell Book.
Here's the code from the exercise. Our job is to implement the mempty
and mappend
functions, which are presented here as undefined
:
module Chap15Ex where
import Data.Monoid
newtype Mem s a =
Mem {
runMem :: s -> (a, s)
}
instance Monoid a => Monoid (Mem s a) where
mempty = undefined
mappend = undefined
f' :: Mem Integer String
f' = Mem $ \s -> ("hi", s + 1)
main = do
let rmzero = runMem mempty 0
rmleft = runMem (f' <> mempty) 0
rmright = runMem (mempty <> f') 0
print $ rmleft -- ("hi, 1)
print $ rmright -- ("hi", 1)
print $ (rmzero :: (String, Int)) -- ("", 0)
print $ rmleft == runMem f' 0 -- True
print $ rmright == runMem f' 0 -- True
Thanks for setting this up, @alextaylor000 ! I'm not totally certain how much of the solutions to give as hints. I'm going to err on the side of "hey did you notice this thing WINK WINK". If I'm being too cryptic and need more of a hint, just let me know!
As mentioned at lunch, this is pretty tricky at first. There's a bunch of unintuitive stuff happening here.
newtypes
Wait, tuples are weird? Yep. We'll probably bump into this in the
Functor
chapter a bit more, but here's a preview:Monoid
This is the definition from the book for reference
Good observation! We only have a constraint on
a
, and know nothing abouts
. This is similar to something that we've seen before: without a constraint, what do we know about the functionfoo :: s -> s
? A lot or a little, depending on your perspective :P It can only beid
. So what satisfies\s -> (mempty, ____)
given what we know about its type?Veering Totally Off Topic
A Couple Minor Terminology Corrections
Close. This isn't a monad yet, in the same way that integers by themselves aren't monoids. We'll get to that in a couple chapters π I realize that at lunch I said "you'll get familiar with this, because it's the signature of the State Monad", which is true... but it's missing a couple things first.
Records aren't automatically products. We can't just look at the layout of the left side and count the type variables; it's really the right side that matters.
Mem
only has one field, so there's no product. Using an integer analogy,1 * 2
is a product, but1
is just a number.Let's desugar and break down the signature of
Mem
:Now, there is a product deep inside this type: the tuple! You just have to manage to get inside the function by passing an argument to
runMem
to expose it. The intuition is probably clear, but to show this notationally:Coproducts
Sums (coproducts) look very similar:
Either Int String
. But inside we have something different:So what's the simplest way to tell if it's a product or coproduct? Usually just look for a
|
on the right side :PA Tiny Bit of Category Theory
Totally optional, but possibly interesting to some.
Products look like this:
Where those arrows are "projecting" values out. As a more concrete example:
A sum is a "coproduct". The "co-" prefix means to reverse the arrows:
Here we don't have any projection functions, since we can only acquire one side on its own at a time. Concretely:
Side Note
If you really want to interpret a type as a product, you can do this:
...and then just ignore the
()
. There are cases for this, but they're generally in the "clever" camp.Fun with Notation
It's unfair that products have an operator (
,
), but sums don't. So let's fix it!