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

[Ertugrul Söylemez]

Hello there kak,

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

> So, you Monad gurus over here can consider me a block-head, but let me
> assure you people that I am a sincere person trying to learn this
> beautiful but difficult concept.

no worries.  Monads aren't particularly complicated.  The common mistake
is to try to understand "monads" instead of particular monads.  If you
understand Maybe, Either, State and Reader, you effectively understand
what monads are about.

State monads are best understood by looking at their definition:

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

For every type 's' the type 'State s' is a monad, a so-called state
monad.  It represents a function from a value of type 's' (commonly
called the "state") to a tuple of two values, the result and a new value
of type 's'.

Whenever you have a function of this type:

    myFunc :: S -> (A, S)

you could just as well write it as:

    myFunc :: State S A

They are entirely equivalent, except that the State variant encapsulates
the function in a newtype constructor.  Now just go ahead and write the
Monad instance for the State type yourself.  Remember that State is a
family of monads, not a monad itself:

    instance Monad (State s)

Now to your actual problem:  I doubt that you really want a state monad.
As said, a state monad is just the type for functions of the above type.
It is well possible to encode DFAs that way, but it will be inconvenient
and probably not what you want.

I would go for a different approach:  There is an arrow that is exactly
for this kind of computations:  the automaton arrow.  Its definition is
this:

    newtype Auto a b = Auto (a -> (b, Auto a b))

It takes an input value of type 'a' and gives a result of type 'b' along
with a new version of itself.  Here is a simple counter:

    counter :: Int -> Auto Int Int
    counter x = Auto (\dx -> (x, counter (x + dx)))

In the first instant this automaton returns the argument (x).  The next
automaton will be counter (x + dx), where dx is the automaton's input.

What is useful about the automaton arrow is that it encodes an entirely
different idea of state:  local state.  Every automaton has its own
local state over which it has complete control.  There is an equivalent
way to define the automaton arrow:

    data Auto a b = forall s. Auto ((a, s) -> (b, s))

You can see how this looks a lot like state monads, but the state is
local to the particular automaton.  You can then connect automata
together using Category, Applicative and/or Arrow combinators.

The automaton arrow is implemented in the 'arrows' library.  It has a
slightly scarier type, because it is an automaton transformer.  In that
library the type Auto (->) is the automaton arrow.


Greets,
Ertugrul

-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/
-------------- 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/20120528/628e5472/attachment.pgp>