[Haskell-beginners] How to solve this using State Monad?
Henry Lockyer
henry.lockyer at ntlworld.com
Thu May 31 12:58:47 CEST 2012
Hi kak - ok, my mistake - I interpreted your "candidate for the state monad", and "Please note that I wish your solution to use the Control.Monad.State"
too literally. Arrows may point the way forward for you then ;-)
I have a suspicion that if the State monad doesn't make sense yet, then Arrows will not be more obvious,
they look like a kind of more generalised monadic structure (though I don't understand them myself yet)
- but maybe a better fit to your problem will in fact make them clearer for you.
Regarding the State monad: I think it may be slightly unfortunate that it gets introduced as THE state monad (I guess Ertugrul may
agree here...) and the initial examples, like the favourite random number generation example, do not make it immediately obvious how
you might apply it more widely. I certainly experienced a little head-scratching before realising I could simply use things like
"charfunc c = state (stateMC c)".
Another thing that can cause some initial confusion is the fact that the standard implementation seems to have changed since some of the
educational texts were written, so you may find yourself in Hoogle looking at monad transformers before you feel quite ready for them ;-)
Also the standard solution does not export the value constructor so, unlike some examples that you may see, you can only use "State" for
type definitions and you need to use "state" to create an actual value. I think it is a good idea, as Ertugrul suggested, to write your
own state monad instance, and it avoids these 'noise factors' from the library implem.
/Henry
On 31 May 2012, at 05:29, kak dod wrote:
> Hello Ertugrul,
>
> 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.
>
> 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.
>
> 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.
>
> 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.)
>
> Thanks Henry for your example, it has helped me a lot.
>
>
> On Thu, May 31, 2012 at 6:12 AM, Henry Lockyer <henry.lockyer at ntlworld.com> wrote:
> I hear you Ertugrul ;-)
>
> I interpret that kak is struggling to understand the State monad, not find the best solution for a DFA,
> so telling him about something else which is not the State monad will probably not help him too much
> at this point...
>
> Your propaganda is working on me though ! :-)
> I haven't looked at the arrows area at all so far, but I'm interested in state handling solutions
> so I see I need to move it up my reading list!
> Thanks/ Henry
>
> On 30 May 2012, at 23:25, Ertugrul Söylemez wrote:
>
> > Again to promote the automaton arrow, Henry's "aha!" DFA in the
> > automaton arrow:
> >
> > aha :: Auto Char Char
> > aha = aha' 0
> > where
> > aha' :: Int -> Auto Char Char
> > aha' s =
> > Auto $ \input ->
> > case (s, input) of
> > (0, 'a') -> ('Y', aha' 1)
> > (1, 'h') -> ('Y', aha' 2)
> > (2, 'a') -> ('Y', aha' 3)
> > (3, '!') -> ('*', pure ' ')
> > _ -> ('N', aha' 0)
> >
> > Again the state monad is /not/ suitable for automata. State-based
> > automata can't be routed/composed, while Auto-based automata can be
> > routed/composed easily. You can feed the output of the 'aha' automaton
> > into another automaton, etc. For example you could have these:
> >
> > -- | Produce a list of outputs forever (cycling).
> > produce :: [b] -> Auto a b
> > produce = produce' . cycle
> > where
> > produce' (x:xs) = Auto (const (x, produce' xs))
> >
> > -- | Produce "aha!aha!aha!aha!..."
> > produceAha :: Auto a Char
> > produceAha = produce "aha!"
> >
> > Then you could compose the two easily:
> >
> > aha . produceAha
> >
> > I almost feel stupid writing these long explanations, just to see them
> > getting ignored ultimately. The automaton arrow is one of the most
> > useful and most underappreciated concepts for state in Haskell.
> >
> >
> > Greets,
> > Ertugrul
> >
> >
> > Ertugrul Söylemez <es at ertes.de> wrote:
> >
> >> 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.
> >
> > --
> > nightmare = unsafePerformIO (getWrongWife >>= sex)
> > http://ertes.de/
> > _______________________________________________
> > Beginners mailing list
> > Beginners at haskell.org
> > http://www.haskell.org/mailman/listinfo/beginners
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120531/c6c7bfbe/attachment.htm>
More information about the Beginners
mailing list