Haskell from First Principles - Chapter 15 - 'Mem' Exercise

exercise.md

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

Here's what we know so far:

newtypes

newtype Mem s a =
  Mem {
      runMem :: s -> (a, s)
  }

The newtype Mem is a product type with special record syntax. It's a type that contains one value, a function with the signature

s -> (a, s).

This syntax is equivalent to defining Mem with a data constructor that accepts a function, along with a helper function to pull the value out:

newtype Mem s a = Mem (s -> (a, s))
runMem (Mem f) = f

The State monad

The function signature s -> (a, s) is a state monad. It's used to pass state around and update it when need be. I liked this example from Learn You a Haskell... that implemented a basic stack that you could pop and push numbers onto:

type Stack = [Int]  
  
pop :: Stack -> (Int,Stack)  
pop (x:xs) = (x,xs)  
  
push :: Int -> Stack -> ((),Stack)  
push a xs = ((),a:xs) 

monoids, mempty and mappend

We want to define a Monoid instance so we have a reliable way of associating two Mem values with one another.

To do that, we need to define mempty as the identity of Mem, just as 0 is the identity of addition.

We also need to define mappend so that the act of associating two Mem values will produce a new Mem value:

myFirstMem <> mySecondMem

My first question is about implementing mempty, since this seems like a logical place to start.

Our Mem type ultimately stores a tuple of (a, s), where a and s could be different types. So when we're talking about what identity looks like for both those types, it seems to me like we should delegate to the type itself:

  mempty = Mem $ \s -> (mempty, mempty)

... except I don't think that works, because we've specified in our instance declaration that only a needs to have an instance of Monoid.

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
• Record sugar
• Function type class instances
• Tuples are weird

Wait, tuples are weird? Yep. We'll probably bump into this in the Functor chapter a bit more, but here's a preview:

instance Functor ((,) a) where
    fmap f (x,y) = (x, f y)

Monoid

My first question is about implementing mempty

This is the definition from the book for reference

instance Monoid a => Monoid (Mem s a) where
  mempty  = undefined
  mappend = undefined

we've specified in our instance declaration that only a [is a] monoid

Good observation! We only have a constraint on a, and know nothing about s. This is similar to something that we've seen before: without a constraint, what do we know about the function foo :: s -> s? A lot or a little, depending on your perspective :P It can only be id. So what satisfies \s -> (mempty, ____) given what we know about its type?

Veering Totally Off Topic

A Couple Minor Terminology Corrections

The function signature s -> (a, s) is a state monad

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.

The newtype Mem is a product type

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, but 1 is just a number.

-- Product with no type variables
data MyProd = MyProd Int String

Let's desugar and break down the signature of Mem:

newtype Mem s a = Mem { runMem :: s -> (a, s) }
newtype Mem s a = Mem (s -> (a, s))
                    -- ^^^^^^^^^^^
                    -- function type

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:

(a, s)
(,) a s

Coproducts

Sums (coproducts) look very similar: Either Int String. But inside we have something different:

data Either a b = Left a | Right b

So what's the simplest way to tell if it's a product or coproduct? Usually just look for a | on the right side :P

A Tiny Bit of Category Theory

Totally optional, but possibly interesting to some.

Products look like this:

A <----  A x B  ----> B

Where those arrows are "projecting" values out. As a more concrete example:

fst :: (Int, String) -> Int
snd :: (Int, String) -> String

 Int  <--fst--  (Int, String)  --snd--> String

A sum is a "coproduct". The "co-" prefix means to reverse the arrows:

A ---->  A + B  <---- B

Here we don't have any projection functions, since we can only acquire one side on its own at a time. Concretely:

(constructors lowercased for clarity in diagram)

left  :: Int    -> Either Int String
right :: String -> Either Int String

Int --left-->  Either Int String  <--right-- String

Side Note

If you really want to interpret a type as a product, you can do this:

data Alone             = Alone             Int
data AloneProduct      = AloneProduct      Int ()
data OtherAloneProduct = OtherAloneProduct ()  Int

...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!

{-# LANGUAGE TypeOperators #-}

type (+) = Either

Left 1 :: Int + String

Right (Left 1) :: String + (Int + Char)

What the heck. I can't post emoji like "thumbs up" or "wink" in gists because the encoding is too big?! The original version of that post had more encouraging emoji, I swear :P

Thanks for the thoughtful comments! You've put me on the right track for mempty, here's what I've got now:

instance Monoid a => Monoid (Mem s a) where
  mempty  = Mem $ \s -> (mempty, s)

This feels correct, because we're delegating to mempty for the value of a, and we're just returning s unchanged, similar to an identity function. Now I can prove that mempty is behaving in isolation:

runMem mempty 9 :: ([Int], Int)
-- ([],9)

runMem mempty "hi" :: (Sum Int, String)
(Sum {getSum = 0},"hi")

Ok, on to mappend!

I know I'll have two Mems, each with a function inside, so I can destructure that in the argument:

  mappend (Mem f) (Mem f') = undefined

Now, each function has the same signature s -> (a, s), so I'll need to create a new function that combines the output of f and f' into a new tuple. I don't think I can use straight-up function composition because the output of one function can't be used as the input for the next.

mempty = Mem $ \s -> (mempty, s)

:thumbsup:

I don't think I can use straight-up function composition because the output of one function can't be used as the input for the next.

That's right! There's some unwrapping and threading of arguments involved. Here's one step as a hint:

-- You have: Mem f
let (a', s') = f s

Or, well.. you can always use the point free style... but it may be torturous. Better to do it with arguments in this case.

let (a', s') = f s

I didn't realize you could destructure in a normal assignment like that - very cool!

I'm getting very, very close now 😁 I've figured it out! 🎉

🦆 Rubber ducking is awesome - I started typing this message to organize my thoughts before taking a break for the day, but as I was typing it out I realized how I could solve it!

We have to accomplish the following:

1. Write a new function which mappend will ultimately return;
2. Apply the argument that this new function accepts to both functions that we're passing into mappend;
3. Destructure the resulting tuples and gather up our two a values and our two s values;
4. mappend both a values, since they're both guaranteed to be monoidal (yay, laws!)
5. Compose both s values*.

• The last step took me the longest to figure out. But then, I started thinking about how if you ignore part of the tuple, we're really dealing with a plain 'ol composable function:

-- before:
\s -> (a, s + 1)

-- after:
\s -> s + 1

If we can ignore the tuple and make the function return just one value, then we can compose things together!

All that's left is to take the new function we wrote, and wrap it up in a nice Mem package 🗃️

Drumroll please... 🥁 🥁 🥁

---

The solution (here be spoilers)

instance Monoid a => Monoid (Mem s a) where
  mempty                   = Mem $ \s -> (mempty, s)
  mappend (Mem f) (Mem f') = Mem $ \s -> (fst (f s) <> fst (f' s), snd . f . snd . f' $ s)

-- hooray, it passes!
-- > main
--    ("hi",1)
--    ("hi",1)
--    ("",0)
--    True
--    True

I used fst and snd to handle the tuples:

let tuple = ("hello", 0)

fst tuple -- "hello"
snd tuple -- "hello"

For what it's worth, I started with this parenthetical monstrosity, but it really helped me work through what I needed to do:

    Mem $ \s -> ((fst (f s)) <> (fst (f' s)), (snd (f (snd (f' s)))))

---

Now that I've figured it out, I'd love to hear if there's a more idiomatic way of writing this instance, I'm curious about other implementations!

Thanks again for your help, @expede! You gave me the perfect level of hints to lead me towards the solution without giving too much away 👌 👌

Improved readability (here be spoilers)

Let's use some intermediate variables. This means the same thing, and is really just there for readability. It's slightly more operational, but that's clearer here. There may be some minor differences in what the compiler infers for performance stuff, but I'm too lazy to dig into it that far :P The version below is the canonical form.

instance Monoid a => Monoid (Mem s a) where
  mempty = Mem $ \s -> (mempty, s)
  mappend (Mem f) (Mem g) =
      Mem $ \s -> 
        let 
          (a, t) = g s
          (b, u) = f t
        in     
          (a <> b, u)

-- Alternate variable naming, depending on how many ticks you like to track

  mappend (Mem f) (Mem f') =
    Mem $ \s -> 
      let 
        (a' , s' ) = f' s
        (a'', s'') = f  s'
      in
        (a' <> a'', s'')

-- Alternate naming to help follow in English

  mappend (Mem secondFun) (Mem firstFun) =
    Mem $ \state -> 
      let 
        (firstValue, intermediateState) = firstFun state
        (secondValue, finalState) = secondFun intermediateState
      in
        (firstValue <> secondValue, finalState)

Nice, those look great 👍 I see how you're threading the state through from both functions before returning the final result, that makes a lot of sense!