(List home) (Recent threads) (40 other Haskell lists)

**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 115,458 messages, beginning Oct 2000
- 7 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

Ad

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

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, GregOn 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...

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. -- ryanOn 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... > >

Excerpts from jean-christophe mincke's message of Tue Nov 10 21:18:34 +0100 2009: > Hello, Hello,Here is to remarks somewhat off topic: [...]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. [...]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,> 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

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

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-COn 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... >

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

Excerpts from wren ng thornton's message of Thu Nov 12 08:17:41 +0100 2009: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...> 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