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

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!