Functor instance of State

Question

instance Functor (State s) where
 fmap f (State g) = State $ \s0 -> 
 let (a, s1) = g s0
 in (f a, s1)

It is implementation of Functor for State. I cannot understand how does it work? Especially, g is used as it would be a function but on my eye it is not a function. It is just object ( perhaps function) but I cannot understand why it is function. After all, it should be some state so it can for example Int

Please make clear.

• Bakuriu: Usually you have State s a = State (s -> (s, a)) so indeed g is a function with type s -> (s, a) (i.e. it takes a state and produces a result (a in this case) and a new state (s1)). This Functor instance simply applies f to the result of the computation before returning the value.
• mb14: The name state is indeed confusing and the state is a monad itself. What is a monad is something which access and or modify a state.

Answer 1

It looks like your state type looks like:

data State s a = State (s -> (a ,s))

so your fmap function should have type:

fmap :: (a -> b) -> (State s a) -> (State s b)

when you match on the input state value in

fmap f (State g) = State $ \s0 -> 

g is a function s -> (a, s) and you need to construct one of type s -> (b, s).

(a, s1) = g s0

applies the input state to the existing stateful computation, binding a to the result and s1 to the new state. It then applies f to a to obtain the mapped result value in

(f a, s1)

while the state returned from g is unchanged.

• Zeta: "while the state is unchanged." is somewhat ambiguous. "while the state originally returned by g is unchanged" could be better.