[Haskell-beginners] How to solve this using State Monad?

[Ertugrul Söylemez]

kak dod <kak.dod2008 at gmail.com> wrote:

> Thank you very much for your patience with a stupid like me. I am
> going through your comments, part of it is going parallel but I am
> getting something. Sorry for that.

Sorry, I didn't imply that anyone were stupid.  There is a difference
between unexperienced and stupid. =)


> But I am bit confused with the purpose of State Monad now. Is the name
> "State Monad" appropriate to this monad?
> I mean, if it is appropriate then the State Monad must be useful to
> model all types of computations involving state as a dominant part.
> Am I making a mistake here? I guess, I am.

Yes, you are mistaken.  State monads (there are infinitely many of them
(see my original answer)) really model functions of this type:

    S -> (A, S)

Those are functions that take a value of type S (which we call the
state) and give a value of type A as well as a value of type S.  You can
interpret this as modifying state, but in reality it's just an implicit
argument and an implicit result of the same type.

In fact the more experienced you get in Haskell the less compelled you
will be to use a state monad.


> Because it seems from what you have said that the State Monad is
> appropriate only for some types of computations involving state and
> not appropriate for something like DFA which I think is a stateful
> computation.
>
> What I am trying to do is write a Turing Machine simulator in Haskell?
> It's also mainly a state change thing, so if Ertugrul says that State
> Monad is not suitable for DFA simulation, it won't be suitable for TM
> simulation either.

You can of course model your DFA as a function of the following type:

    dfa :: DfaState -> (DfaOutput, DfaState)

or equivalently (they are really the same thing):

    dfa' :: State DfaState DfaOutput

My point is:  It's not very useful.  The problem of the state monad is a
very fundamental one.  As soon as your automaton is parametric it
becomes a function:

    dfaWith :: DfaInput -> State DfaState DfaOutput

Functions in Haskell are opaque.  For every composition of automata you
would have to write an individual loop, because you would have to force
the two individual states to be combined somehow.  This gets more
inconvenient as your automaton library grows.

To allow composition state must be local and the input type must be
explicit.  This is exactly what the automaton arrow does:

    dfa :: Auto DfaInput DfaOutput

You will notice that the state type is gone.  It is now local to 'dfa'
and hidden from outside.  This is how you would make a smart constructor
for Turing machines:

    turing :: TuringMachine i o -> Auto i o

This translation is pretty straightforward.


> So, exactly what type of computations involving what type of states
> are better handled by the State Monad?
> I mean what type of state-computations can be made composible using
> the State Monad and what type of  state-computations cannot be made
> composible using  the State Monad? (As you have pointed out automaton
> cannot be made composible using the State Monad in an elegant manner.)

When you have some kind of application/algorithm argument that only very
deep functions use and sometimes update.  State monads save you from
having to pass around this argument and extract the result explicitly
all the time.  Again this is the full definition of state monads:

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

There is nothing magic going on.  Computations in a state monad are just
functions from 's' to '(a, s').  And there is a simple proof that the
two are equivalent:

    runState :: State s a -> (s -> (a, s))
    state    :: (s -> (a, s)) -> State s a

So there is a one-to-one mapping between the two.


Greets,
Ertugrul

-- 
Key-ID: E5DD8D11 "Ertugrul Soeylemez <es at ertes.de>"
FPrint: BD28 3E3F BE63 BADD 4157  9134 D56A 37FA E5DD 8D11
Keysrv: hkp://subkeys.pgp.net/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120531/ae6cdc6f/attachment.pgp>