ArchiveOrangemail archive

The Haskell Cafe


haskell-cafe.haskell.org
(List home) (Recent threads) (40 other Haskell lists)

Subscription Options

  • RSS or Atom: Read-only subscription using a browser or aggregator. This is the recommended way if you don't need to send messages to the list. You can learn more about feed syndication and clients here.
  • Conventional: All messages are delivered to your mail address, and you can reply. To subscribe, send an email to the list's subscribe address with "subscribe" in the subject line, or visit the list's homepage here.
  • Moderate traffic list: up to 30 messages per day
  • This list contains about 113,698 messages, beginning Oct 2000
  • 12 messages added yesterday
Report the Spam
This button sends a spam report to the moderator. Please use it sparingly. For other removal requests, read this.
Are you sure? yes no

(state) monad and CPS

Ad
jean-christophe mincke 1257884233Tue, 10 Nov 2009 20:17:13 +0000 (UTC)
Hello,

I would like to get some advice about state monad (or any other monad I
guess) and CPS.

Let's take a simple exemple (see the code below)

'walk' is a function written in CPS that compute the number of nodes &
leaves in a tree. It use a counter which is explicitly passed through calls.
'walk2' is does the same using the state monad but is not written in CPS

Is it possible to write a function 'walk3' written in CPS and using the
state monad?

Thank you

Regards

J-C


module M where

import Control.Monad.State

data Node =
     Node (Node, Int, Node)
    |Leaf Int
    |Empty
    deriving (Show)

walk Empty acc k = k acc
walk (Leaf _) acc k = k (acc+1)
walk (Node (l, _, r)) acc k = let k1 acc = walk r acc k
                              in
                              walk l (acc+1) k1


nb = Node (Leaf 1, 2, Leaf 3)
nd = Node (nb, 4, Empty)

nh = Node (Empty, 8, Leaf 9)
ng = Node (Leaf 6, 7, nh)

ne = Node (nd, 5, ng)

r = walk ne 0 id

walk2 Empty = return ()
walk2 (Leaf _ ) = do acc <- get
                     put (acc+1)
                     return ()
walk2 (Node (l, _, r)) = do acc <- get
                            put (acc+1)
                            walk2 l
                            walk2 r
                            return ()


r2 = runState (walk2 ne) 0
Gregory Crosswhite 1257886056Tue, 10 Nov 2009 20:47:36 +0000 (UTC)
Yes;  check out the module "Control.Monad.Cont", which has a monad for  
continuation passing style.

In particular, note that most of the monads in Control.Monad.* are  
"stackable" in that there is a version of the monad which you can  
stack on top of an existing monad.  So for example, you could use  
ContT to stack the CPS monad on top of the State monad, or StateT to  
stack the State monad on top of the CPS monad.

Hope this helps,
Greg
On Nov 10, 2009, at 12:18 PM, jean-christophe mincke wrote: > Hello, > > I would like to get some advice about state monad (or any other > monad I guess) and CPS. > > Let's take a simple exemple (see the code below) > > 'walk' is a function written in CPS that compute the number of nodes > & leaves in a tree. It use a counter which is explicitly passed > through calls. > 'walk2' is does the same using the state monad but is not written in > CPS > > Is it possible to write a function 'walk3' written in CPS and using > the state monad? > > Thank you > > Regards > > J-C > > > module M where > > import Control.Monad.State > > data Node = > Node (Node, Int, Node) > |Leaf Int > |Empty > deriving (Show) > > walk Empty acc k = k acc > walk (Leaf _) acc k = k (acc+1) > walk (Node (l, _, r)) acc k = let k1 acc = walk r acc k > in > walk l (acc+1) k1 > > > nb = Node (Leaf 1, 2, Leaf 3) > nd = Node (nb, 4, Empty) > > nh = Node (Empty, 8, Leaf 9) > ng = Node (Leaf 6, 7, nh) > > ne = Node (nd, 5, ng) > > r = walk ne 0 id > > walk2 Empty = return () > walk2 (Leaf _ ) = do acc <- get > put (acc+1) > return () > walk2 (Node (l, _, r)) = do acc <- get > put (acc+1) > walk2 l > walk2 r > return () > > > r2 = runState (walk2 ne) 0 > > _______________________________________________ > Haskell-Cafe mailing list > > http://www.haskell.org/mailman/listinfo/haske...
Ryan Ingram 1257919683Wed, 11 Nov 2009 06:08:03 +0000 (UTC)
Something like this should work:

newtype ContState r s a = ContState { runCS :: s -> (a -> s -> r) -> r }

instance Monad (ContState r s) where
    return a = ContState $ \s k -> k a s
    m >>= f = ContState $ \s0 k -> runCS m s $ \a s1 -> runCS (f a) s1 k

instance MonadState s (ContState r s) where
    get = ContState $ \s k -> k s s
    put s = ContState $ \_ k -> k () s

instance MonadCont (ContState r s) where
    callCC f = ContState $ \s0 ka -> runCS (f $ \a -> ContState $ \s1
kb -> ka a s1) s0 ka

There's a design choice as to whether the inner continuation should be
called with s0 or s1; it depends if you want the continuation from
callCC to abort any state changes or preserve them up to that point.

  -- ryan
On Tue, Nov 10, 2009 at 12:18 PM, jean-christophe mincke wrote: > Hello, > > I would like to get some advice about state monad (or any other monad I > guess) and CPS. > > Let's take a simple exemple (see the code below) > > 'walk' is a function written in CPS that compute the number of nodes & > leaves in a tree. It use a counter which is explicitly passed through calls. > 'walk2' is does the same using the state monad but is not written in CPS > > Is it possible to write a function 'walk3' written in CPS and using the > state monad? > > Thank you > > Regards > > J-C > > > module M where > > import Control.Monad.State > > data Node = > Node (Node, Int, Node) > |Leaf Int > |Empty > deriving (Show) > > walk Empty acc k = k acc > walk (Leaf _) acc k = k (acc+1) > walk (Node (l, _, r)) acc k = let k1 acc = walk r acc k > in > walk l (acc+1) k1 > > > nb = Node (Leaf 1, 2, Leaf 3) > nd = Node (nb, 4, Empty) > > nh = Node (Empty, 8, Leaf 9) > ng = Node (Leaf 6, 7, nh) > > ne = Node (nd, 5, ng) > > r = walk ne 0 id > > walk2 Empty = return () > walk2 (Leaf _ ) = do acc <- get > put (acc+1) > return () > walk2 (Node (l, _, r)) = do acc <- get > put (acc+1) > walk2 l > walk2 r > return () > > > r2 = runState (walk2 ne) 0 > > > _______________________________________________ > Haskell-Cafe mailing list > > http://www.haskell.org/mailman/listinfo/haske... > >
Nicolas Pouillard 1257947928Wed, 11 Nov 2009 13:58:48 +0000 (UTC)
Excerpts from jean-christophe mincke's message of Tue Nov 10 21:18:34 +0100 2009:
> Hello,
Hello,
> I would like to get some advice about state monad (or any other monad I > guess) and CPS.
Here is to remarks somewhat off topic: [...]
> walk Empty acc k = k acc > walk (Leaf _) acc k = k (acc+1) > walk (Node (l, _, r)) acc k = let k1 acc = walk r acc k > in > walk l (acc+1) k1
Remember that by default laziness and accumulators does not fits well together. Here you are probably building a chain of thunks. Making acc a strict argument (using !acc) or using 'seq' (acc `seq` ...) will cure this. [...]
> do acc <- get > put (acc+1) > ...
Since this pattern occurs often 'modify' is a combination of get and put: do modify (+1) ... About your CPS question, you should have a look at the 'transformers' package, in particular the Control.Monad.Trans.Cont [1] module. [1]: http://hackage.haskell.org/packages/archive/t... Best regards,
wren ng thornton 1258010164Thu, 12 Nov 2009 07:16:04 +0000 (UTC)
Nicolas Pouillard wrote: > Excerpts from jean-christophe mincke's message of Tue Nov 10 21:18:34 +0100 2009: >> do acc <- get >> put (acc+1) >> ... > > Since this pattern occurs often 'modify' is a combination of get and put: > > do modify (+1) > ...
Though the caveat about laziness applies here as well. modify is famously lazy which can lead to space leaks and stack overflows. Better would be to define and use your own strict version: modify' f = get >>= \x -> put $! f x
jean-christophe mincke 1258013164Thu, 12 Nov 2009 08:06:04 +0000 (UTC)
Hello,

Thank everybody for the answers.

I must admit that I did not really emphasize the goal behind my initial
question. Which is better expressed this way:

'walk' is written is CPS and is tail recursive. Unless I am wrong , if the
continuation monad  is used, the recursive calls to 'walk' are no longer in
tail position.

So my initial question was rather: is it possible to use the state monad and
keeping the code tail recursive?

I do not master all the subtilities of lazy evaluation yet and perhaps  tail
recursivity does not have the same importance (or does not offer the same
guarantees) in a lazy language as it does in a strict language.
But I am facing a similar problem with workflows in F# (F#'s monads).

Thank you

Regards

J-C
On Thu, Nov 12, 2009 at 8:17 AM, wren ng thornton wrote: > Nicolas Pouillard wrote: > >> Excerpts from jean-christophe mincke's message of Tue Nov 10 21:18:34 >> +0100 2009: >> >>> do acc <- get >>> put (acc+1) >>> ... >>> >> >> Since this pattern occurs often 'modify' is a combination of get and put: >> >> do modify (+1) >> ... >> > > Though the caveat about laziness applies here as well. modify is famously > lazy which can lead to space leaks and stack overflows. Better would be to > define and use your own strict version: > > modify' f = get >>= \x -> put $! f x > > -- > Live well, > ~wren > > _______________________________________________ > Haskell-Cafe mailing list > > http://www.haskell.org/mailman/listinfo/haske... >
Heinrich Apfelmus 1258020333Thu, 12 Nov 2009 10:05:33 +0000 (UTC)
jean-christophe mincke wrote: > I do not master all the subtilities of lazy evaluation yet and perhaps tail > recursivity does not have the same importance (or does not offer the same > guarantees) in a lazy language as it does in a strict language.
Yep, that's the case. With lazy evaluation, tail recursion is less important. Also, code that looks tail recursive in a strict language will actually not be tail recursive in Haskell. A well-known example is the definition foldl and applied in the fashion of foldl (+) 0 [0..10] Regards, apfelmus
Nicolas Pouillard 1258018039Thu, 12 Nov 2009 09:27:19 +0000 (UTC)
Excerpts from wren ng thornton's message of Thu Nov 12 08:17:41 +0100 2009:
> Nicolas Pouillard wrote: > > Excerpts from jean-christophe mincke's message of Tue Nov 10 21:18:34 +0100 2009: > >> do acc <- get > >> put (acc+1) > >> ... > > > > Since this pattern occurs often 'modify' is a combination of get and put: > > > > do modify (+1) > > ... > > Though the caveat about laziness applies here as well. modify is > famously lazy which can lead to space leaks and stack overflows. Better > would be to define and use your own strict version: > > modify' f = get >>= \x -> put $! f x
However if you want a strict state you should better use Control.Monad.State.Strict [1]. Finally I'm wondering if [1] is strict enough... [1]: http://www.haskell.org/ghc/docs/latest/html/l...
Home | About | Privacy