State-passing

In the previous chapter, we discussed the type State s a for computations that pass a state of type s and return a result of type a:

Control.Monad.State
newtype State s a = State { runState :: s -> (a,s) }

We have used this type to add memoization to the Fibonacci function:

fib :: Integer -> State (Map Integer Integer) Integer
fib n = State (\ s ->
  case Map.lookup n s of
    Just f  -> (f, s)
    Nothing -> let (f, s') = runState (fib' n) s
               in  (f, insert n f s'))
  where
    fib' n
      | n < 2     = pure 1
      | otherwise = (+) <$> fib (n-1) <*> fib (n-2)

A benefit of using the State s a newtype is that it abstracts the actual representation...