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