Understanding State

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Understanding State

Geoffrey Marchant
I'm trying to understand how to use State in a function. I've avoided the
topic for several years because State just never seemed very useful, but I
figure it's time for me to figure it out:
I have the following function

> update :: (a -> (r,a)) -> Int -> [a] -> (r, [a])
> update s 0 (a:as) = let (r,a') = s a in (r,a':as)
> update s i (a:as) = let (r,as') = update s (i-1) as in (r, a:as')

which updates a particular element of a list. Looking at it, I see two parts
of the type signature that look like State types, which leads me to think of
this:

> update' :: State a r -> Int -> State [a] r

Which leads to me writing this:

> update' s 0 = do
>    (a:as) <- get
>    let (r, a') = runState s a
>    put (a':as)
>    return r
> update' s i = do
>    (a:as) <- get
>    put as
>    r <- update' s (i-1)
>    as' <- get
>    put (a:as')
>    return r

Now, this just looks awful. The first half, the base condition, is actually
"running" a State calculation. And the second half sets the state within the
monad twice!

I like the idea of using State because it simplifies the type. When I see (a
-> (b,a)) I say "Wait a second, that's a State calculation, isn't it?" and
then, hopefully, generalize. But I can't write that calculation nearly as
concisely. How do I do this properly?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090710/b855502e/attachment-0001.html
Reply | Threaded
Open this post in threaded view
|

Understanding State

Jan Jakubuv-2
Hello Geoffrey,

when you really want to make the first function parameter (`a -> (r,a)`) a
monad, you can use `r` as the state instead of `a` (and `[a]`). Then both
the first parameter and the result are in the same monad `State r` and you
can write:

    update2 :: State r a -> Int -> [a] -> State r [a]
    update2 sm 0 (a:as) = sm >>= return . (:as)
    update2 sm i (a:as) = update2 sm (i-1) as >>= return . (a:)

Nevertheless in both cases (update' and update2) you need to pass some bogus
initial state (or a value in the case of update') to run the computation. In
this case I would use the `Writer r` monad anyway.

Finally just note that `State a` and `State [a]` are different monads and
they can not be easily used in the same computation (although it's indeed
possible).

Sincerely,
  Jan.


On Thu, Jul 09, 2009 at 10:34:29PM -0600, Geoffrey Marchant wrote:

>
> Which leads to me writing this:
>
> > update' s 0 = do
> >    (a:as) <- get
> >    let (r, a') = runState s a
> >    put (a':as)
> >    return r
> > update' s i = do
> >    (a:as) <- get
> >    put as
> >    r <- update' s (i-1)
> >    as' <- get
> >    put (a:as')
> >    return r
>


--
Heriot-Watt University is a Scottish charity
registered under charity number SC000278.

Reply | Threaded
Open this post in threaded view
|

Understanding State

Jan Jakubuv-2
Hi again,

sorry, now I see that it is not probably what you wanted because the first
monad parameter does not depend on `a`. So better try this version where the
first parameter is not a monad at all:

    update3 :: (a -> (r,a)) -> Int -> [a] -> State r [a]
    update3 f 0 (a:as) = let (r,a') = f a in put r >> return (a':as)
    update3 f i (a:as) = update3 f (i-1) as >>= return . (a:)

Sincerely,
    Jan.


On Fri, Jul 10, 2009 at 10:46:19AM +0100, Jan Jakubuv wrote:

> Hello Geoffrey,
>
> when you really want to make the first function parameter (`a -> (r,a)`) a
> monad, you can use `r` as the state instead of `a` (and `[a]`). Then both
> the first parameter and the result are in the same monad `State r` and you
> can write:
>
>     update2 :: State r a -> Int -> [a] -> State r [a]
>     update2 sm 0 (a:as) = sm >>= return . (:as)
>     update2 sm i (a:as) = update2 sm (i-1) as >>= return . (a:)
>


--
Heriot-Watt University is a Scottish charity
registered under charity number SC000278.

Reply | Threaded
Open this post in threaded view
|

Re: Understanding State

Maurí­cio
> sorry, now I see that it is not probably what you wanted because the first
> monad parameter does not depend on `a`. So better try this version where the
> first parameter is not a monad at all:

Geoffrey,

Maybe you can give us an example on how you intend to use that
code. Any of Jan's examples, or even others, can be a choice
depending on that. For instance, are you going to update a full
list with a single Int parameter, and then update a list many
times with changing parameters? Are you going to take a single
element and update it many times? Where are those Ints and rs
comming from?

Maur?cio