Reducing Haskell expressions

Question

Hi I am a Haskell newbie and mostly reading from LYAH and Hutton. Recently I came across this snippet where the Functor instance of a State monad, expressed as:

instance Functor (State st) where
    fmap f m = State $ \st -> let (a, s) = runState m st in (f a, s)

This can be reduced to:

instance Functor (State st) where 
    fmap f m = State $ (\(a,s) -> (f a,s)) . runState m

Can anyone explain the workflow behind this reduction?

Also what are some good resources/advice on how to learn such reduction techniques?

Answer 1

If any of the concepts I bring up (such as lambda functions) are unclear, read about them in LYAH and play around a little with them in ghci. Then come back to this reply again and everything should clear up a bit!

One thing that might be confusing if you are coming from other programming languages is that in Haskell, you can take a function such as

runState

and add one argument

runState m

and it will still be a valid function. If you then add a second argument, like so:

runState m st

it will finally compute a value. This means that if runState is a function of two arguments, then runState m is a function of one argument and can be treated like any other function of one argument.

---

The important bit in your example is

\st -> let (a, s) = runState m st in (f a, s)

which can be turned into

(\(a,s) -> (f a,s)) . runState m

using the operator for function composition, (.).

---

The first step to understanding how that is possible is recognising that a let…in expression can be rewritten in a lambda form. This means that

let y = f x in expr

can be written as

(\y -> expr) (f x)

Both of those lines will bind the name y to the value of f x, which is really all we need of a let…in expression.

If you apply that knowledge to

\st -> let (a, s) = runState m st in (f a, s)

you will see that it can be rewritten as

\st -> (\(a, s) -> (f a, s)) (runState m st)

and we're halfway there!

---

The definition of function composition is this:

f . g = \x -> f (g x)

This means that any time you have something that looks like \x -> f (g x) you can replace it with just f . g.

Well, in this case we do have something that looks like that! If we say that

f = \(a, s) -> (f a, s)
g = runState m
x = st

We see that

\st -> (\(a, s) -> (f a, s)) (runState m st)
\x  -> f                     (g          x)

is no more than function composition waiting to happen. So we can turn it into

f . g

which was, with our definitions of f and g,

f                     . g
(\(a, s) -> (f a, s)) . (runState m)

and you are allowed to drop the parentheses around runState m.