*tuple*, it is a

*function that returns a tuple*.

I'm going to start with a version that does not change the state. Here is the first version of the code.

-module(state_monad).

-export([unit/1, bind/2]).

unit(A) ->

fun(X) ->

{A, X}

end.

bind(M, K) ->

fun(X) ->

{A, Y} = M(X),

{B, Z} = (K(A))(Y),

{B, Z}

end.

Right,

**unit/1**now takes an un-monadic value

**A**and returns a

*function*that takes a

*state*

**X**and returns the value in a tuple with the state X.

And now

**bind/2**takes a monadic value

**M**- which will be a

*function*- plus a function

**K**that is going to be applied to the value inside the monadic value. What does

**bind/2**return? It returns a

*function*that takes a state

**X**and returns a tuple

**{B, Z}**where

**B**is a new value and

**Z**is a new state.

So first this function that we are going to return has to open up the monadic value M - and how to do this? M is a function that takes a state, so we execute the function M(X) with the state X and we get out the value, A, and the state Y that has been packed inside:

{A, Y} = M(X)

So now we have to apply our function F to the value A because that is what bind is for: and this gives us a monadic value, ie a function that takes a state as argument - that is we execute K(A) to get the function then apply it to Y, which looks like this - (K(A))(Y).

{B, Z} = (K(A))(Y):

This now returns the new tuple {B, Z} as required.

Now to try this here is the evaluator code that uses the state monad, without doing anything with the state:

-module(eval_sm).

-export([eval/1]).

-export([answer/0, error/0]).

-import(state_monad, [unit/1, bind/2]).

% Evaluator with state monad

eval({con, A}) ->

unit(A);

eval({dv, T, U}) ->

bind(eval(T), fun(A) ->

bind(eval(U), fun(B) ->

unit(A div B)

end)

end).

answer() ->

{dv, {dv, {con, 1972}, {con, 2}}, {con, 23}}.

error() ->

{dv, {con, 1}, {con, 0}}.

If I now compile these and load them up and blithely

**eval(answer)**I get this:

Eshell V5.10.2 (abort with ^G)

1> l(eval_sm).

{module,eval_sm}

2> eval_sm:eval(eval_sm:answer()).

#Fun<state_monad.1.81552699>

3>

Evaluating returns a

*function*not a

*value*. To make this work fully I need to call this function, passing some state:-

3> (eval_sm:eval(eval_sm:answer()))("some state").

{42,"some state"}

That's it, I get the actual answer 42 in wraps with the state that I passed in at the top.

To make this actually do something we now need to add a function that will change the state. We add a function

**tick/0**which returns a function that takes a state (we are now assuming this is going to be a number) and returns a tuple containing a dummy value and the state now incremented:

tick() ->

fun(X) ->

{ok, X+1}

end.

This goes in the state monad code so we will need to export it.

The objective is to count how many times we execute a division. So in the evaluator, when we perform a division operation instead of just calling this:

unit(A div B)

we do this:

bind(tick(), fun(E)-> unit(A div B) end)

That is we bind the tick() function onto a function we invent on the spot to do the division. We need a dummy parameter E in there - well I think we do, I'm not an Erlang lawyer - which just gives us a warning from the compiler.

It does however give the right answer - now I pass 0 as my initial state and it gets incremented:

1> l(eval_sm).

{module,eval_sm}

2> (eval_sm:eval(eval_sm:answer()))(0).

{42,2}

3>

42 is the answer to the evaluation and 2 is the final value of the state.

This is the final code:

-module(state_monad).

-export([unit/1, bind/2]).

-export([tick/0]).

unit(A) ->

fun(X) ->

{A, X}

end.

bind(M, K) ->

fun(X) ->

{A, Y} = M(X),

{B, Z} = (K(A))(Y),

{B, Z}

end.

tick() ->

fun(X) ->

{ok, X+1}

end.

-module(eval_sm).

-export([eval/1]).

-export([answer/0, error/0]).

-import(state_monad, [unit/1, bind/2, tick/0]).

% Evaluator with state monad

eval({con, A}) ->

unit(A);

eval({dv, T, U}) ->

bind(eval(T), fun(A) ->

bind(eval(U), fun(B) ->

bind(tick(), fun(E)-> unit(A div B) end)

end)

end).

answer() ->

{dv, {dv, {con, 1972}, {con, 2}}, {con, 23}}.

error() ->

{dv, {con, 1}, {con, 0}}.

Some doodling with pencil and paper will be required before I'm sure I see why that works. I take my hat off to the people who thought of this stuff.

## No comments:

## Post a Comment