Converting a 'streaming' monad into a list
Hi everyone... it's my newbie post! I am trying to create a monad which allows computations to output data to a stream. (Probably such a thing already exists, but it's a good problem for my current skill level in Haskell) For example: streamDemo = do output 1 output 2 output 5 makelist streamDemo -- [1,2,5] I modelled my implementation around the state monad, but with a different execution model: class (Monad m) => MonadStream w m | m -> w where output :: w -> m () run :: m a -> s -> (s -> w -> s) -> s -- basically foldl on the stream values makelist m = reverse $ run m [] (flip (:)) -- s is the type of the object to stream, r is the return type type StreamFunc s r = forall b. b -> (b -> s -> b) -> (r,b) newtype Stream s r = Stream { run' :: StreamFunc s r } instance Monad (Stream s) where return r = Stream (\s _ -> (r,s)) Stream m >>= k = Stream (\s f -> let (r,s') = (m s f) in run' (k r) s' f) instance (MonadStream w) (Stream w) where output w = Stream (\s f -> ((),f s w)) run m st f = snd $ run' m st f What I don't like is how makelist comes out. It feels wrong to need to use reverse, and that also means that infinite streams completely fail to work. But I think it's impossible to fix with the "foldl"-style "run". Is there a better implementation of "makelist" possible with my current definition of "run"? If not, what type should "run" have so that it can work correctly? As an example, I want to fix the implementation to make the following code work: fibs :: Stream Integer () fibs = fibs' 0 1 where fibs' x y = output y >> fibs' y (x+y) fiblist :: [Integer] fiblist = makelist fibs take 5 fiblist -- [1,1,2,3,5], but currently goes into an infinite loop Thanks, -- ryan
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Ryan Ingram wrote:
Hi everyone... it's my newbie post!
I am trying to create a monad which allows computations to output data to a stream. (Probably such a thing already exists, but it's a good problem for my current skill level in Haskell)
For example: streamDemo = do output 1 output 2 output 5 makelist streamDemo -- [1,2,5] I modelled my implementation around the state monad, but with a different execution model:
class (Monad m) => MonadStream w m | m -> w where output :: w -> m () run :: m a -> s -> (s -> w -> s) -> s -- basically foldl on the stream values makelist m = reverse $ run m [] (flip (:))
-- s is the type of the object to stream, r is the return type type StreamFunc s r = forall b. b -> (b -> s -> b) -> (r,b) newtype Stream s r = Stream { run' :: StreamFunc s r } instance Monad (Stream s) where return r = Stream (\s _ -> (r,s)) Stream m >>= k = Stream (\s f -> let (r,s') = (m s f) in run' (k r) s' f) instance (MonadStream w) (Stream w) where output w = Stream (\s f -> ((),f s w)) run m st f = snd $ run' m st f
What I don't like is how makelist comes out. It feels wrong to need to use reverse, and that also means that infinite streams completely fail to work. But I think it's impossible to fix with the "foldl"-style "run". Is there a better implementation of "makelist" possible with my current definition of "run"? If not, what type should "run" have so that it can work correctly?
As an example, I want to fix the implementation to make the following code work: fibs :: Stream Integer () fibs = fibs' 0 1 where fibs' x y = output y >> fibs' y (x+y) fiblist :: [Integer] fiblist = makelist fibs
take 5 fiblist -- [1,1,2,3,5], but currently goes into an infinite loop
As you might have guessed, reversing the list also forces it, thus making infinite lists impossible and long lists will perform badly. The trick is when you run the 'output' function to return that element and _then_ do the rest of the computation. What does this sounds like? That's right, the continuation monad! :) It's not as scary as it might sound like, it can basically be implemented with two one-liner functions (wow!). I've taken the liberty of writing your monad, except without the classes and instances: import Control.Monad.Cont type Stream r a = Cont [r] a output :: r -> Stream r () output r = Cont $ \c -> r : c () makelist :: Stream r () -> [r] makelist m = runCont m (const []) fibs :: Num n => Stream n () fibs = fibs' 0 1 where fibs' x y = output x >> fibs' y (x+y) fiblist :: [Integer] fiblist = makelist fibs So, the output function returns its argument, then the result of the rest of the computation. makelist provides a stop to the continuation with the empty list. You recognize fibs and fiblist from your code. Is this what you where looking for? You can see the monad transformer version of this technique in the yet to be released library Binary ByteString: http://www.haskell.org/~kolmodin/code/bbs/src/Data/ByteString/Binary/EncM.hs Cheers, Lennart Kolmodin -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.5 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFFllwn4txYG4KUCuERAo/UAJ9nXeGnaONCI4BDSn7YZIUFryB0VQCbBJpL lxw7HG17Yx0aPJXQ12gWPtA= =IEjs -----END PGP SIGNATURE-----
I am trying to create a monad which allows computations to output data to a stream. (Probably such a thing already exists, but it's a good problem for my current skill level in Haskell)
For example: streamDemo = do output 1 output 2 output 5 makelist streamDemo -- [1,2,5]
The trick is when you run the 'output' function to return that element and _then_ do the rest of the computation. What does this sounds like? That's right, the continuation monad! :) It's not as scary as it might sound like, it can basically be implemented with two one-liner functions (wow!).
Well, I am pretty scared because the intended functionality is provided by good old MonadWriter: output x = tell [x] streamDemo :: Writer [Integer] () streamDemo = do tell 1 tell 2 tell 5 execWriter streamDemo == [1,2,5] assuming an (instance Monoid [a] where ..) If you want the "stream based" implementation for lists, as
type StreamFunc s r = forall b. b -> (b -> s -> b) -> (r,b)
suggests, you can always use a (Writer (List a) c) with the following Monoid implementation: newtype List a = List (forall b . b -> (b -> a -> b) -> b) instance Monoid (List a) where mempty = List (curry fst) f `mappend` g = \one succ -> f (g one succ) succ I think that the types (StreamFunc s r) and (Writer (List s) r) are isomorphic (modulo some _|_).
What I don't like is how makelist comes out. It feels wrong to need to use reverse, and that also means that infinite streams completely fail to work. But I think it's impossible to fix with the "foldl"-style "run". Is there a better implementation of "makelist" possible with my current definition of "run"? If not, what type should "run" have so that it can work correctly?
Last but not least, you can simulate foldr with foldl foldr f b xs = foldl (\b' x -> b' . f x) id xs b and vice versa. This is an implementation of difference lists, essentially a continuation passing style. Personally, I prefer the word 'dual' because one passes from b to it's dual (b -> r) for suitable r. Unfortunately, the translation makelist m = runm' (:) [] where runm' f b = (run m) id (\b' x -> b' . f x) b does not work on infinite lists because foldl does not return a result before the whole list is traversed, "tail recursion" is to be blamed. You should give "run" the meaning of (foldr) and not that of (foldl) as the latter can be recovered from the former but not the other way round. Regards, apfelmus
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 apfelmus@quantentunnel.de wrote:
I am trying to create a monad which allows computations to output data to a stream. (Probably such a thing already exists, but it's a good problem for my current skill level in Haskell) For example: streamDemo = do output 1 output 2 output 5 makelist streamDemo -- [1,2,5] The trick is when you run the 'output' function to return that element and _then_ do the rest of the computation. What does this sounds like? That's right, the continuation monad! :) It's not as scary as it might sound like, it can basically be implemented with two one-liner functions (wow!).
Well, I am pretty scared because the intended functionality is provided by good old MonadWriter:
As you rightfully should..
output x = tell [x]
streamDemo :: Writer [Integer] () streamDemo = do tell 1 tell 2 tell 5
execWriter streamDemo == [1,2,5]
assuming an (instance Monoid [a] where ..)
Oh, the Writer has much nicer properties than I thought. Lets have a look at the implementation (from GHC source) newtype Writer w a = Writer { runWriter :: (a, w) } instance (Monoid w) => Monad (Writer w) where return a = Writer (a, mempty) m >>= k = Writer $ let (a, w) = runWriter m (b, w') = runWriter (k a) in (b, w `mappend` w') instance Monoid [a] where mempty = [] mappend = (++) Oh, I see it clearer now. The first (++) will be used to join the first output with the rest, thus lazily returning the first one. It also seems to (suprise!) perform better than the continuation solution. Does it always return elements in O(1) ? Cheers, Lennart Kolmodin -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.5 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFFlpeY4txYG4KUCuERAk/7AKC5BPweztpGfbj4tA6ckyOkG8PikwCfWHK0 PRd2S36VQQ0Ztsj8qLl8VkY= =j8rL -----END PGP SIGNATURE-----
Oh, the Writer has much nicer properties than I thought.
But WriterT is not lazy enough. So I put a lazier version up on the wiki: http://haskell.org/haskellwiki/New_monads/LazyWriterT And I actually tried the same streaming generator type problem when I started Haskell, and my results with Writer and Cont are on the old wiki: http://haskell.org/hawiki/PythonGenerator -- Chris
On Sat, Dec 30, 2006 at 10:31:30PM +0000, Chris Kuklewicz wrote:
But WriterT is not lazy enough. So I put a lazier version up on the wiki:
Interesting. Writer is lazy but WriterT Identity isn't. I imagine that both lazy and strict variants would be useful. Same for State/StateT.
Ross Paterson wrote:
On Sat, Dec 30, 2006 at 10:31:30PM +0000, Chris Kuklewicz wrote:
But WriterT is not lazy enough. So I put a lazier version up on the wiki:
Interesting. Writer is lazy but WriterT Identity isn't. I imagine that both lazy and strict variants would be useful. Same for State/StateT.
Is there a compelling reason why I should want a "strict" version? Here, strictness only means that the pattern match on (,) may fail which implies that the pair is _|_ anyway. Strictness here does *not* mean that the stuff written out is evaluated strictly, only that the pair constructor is matched by a refutable pattern. In other words, is there an example where one would prefer (foo (a,b) = ...) over (foo ~(a,b) = ...) for reasons of time and space? If not, then I think it's a bug. Regards, apfelmus
hi, On 12/30/06, Ross Paterson <ross@soi.city.ac.uk> wrote:
On Sat, Dec 30, 2006 at 10:31:30PM +0000, Chris Kuklewicz wrote:
But WriterT is not lazy enough. So I put a lazier version up on the wiki:
Interesting. Writer is lazy but WriterT Identity isn't. I imagine that both lazy and strict variants would be useful. Same for State/StateT.
this is because of the pattern matching on pairs in the do notation (in the definition of bind). in the writer monad the definition uses let. it can be fixed by using ~ in the do notation and the extra lazyness is useful when working with mfix. in my library i have also experimented with various combinations of seq (on output) and ~ to reduce the number of space leaks but i am not sure which is the best solution yet. -iavor
hi, you might find the "backward" state monad interesting. here is the basic idea: newtype S s a = S (s -> (a,s)) instance Monad (S s) where return a = S (\s -> (a,s)) S m >>= k = S (\s1 -> let (a,s3) = m s2 (b,s2) = run s1 (k a) in (b,s3)) put x = S (\s -> ((),x:s)) run s (S m) = m s test = snd $ run [] $ do put 'x' put 'y' undefined hope this helps -iavor On 12/30/06, Ryan Ingram <ryani.spam@gmail.com> wrote:
Hi everyone... it's my newbie post!
I am trying to create a monad which allows computations to output data to a stream. (Probably such a thing already exists, but it's a good problem for my current skill level in Haskell)
For example:
streamDemo = do output 1 output 2 output 5
makelist streamDemo -- [1,2,5]
I modelled my implementation around the state monad, but with a different execution model:
class (Monad m) => MonadStream w m | m -> w where output :: w -> m () run :: m a -> s -> (s -> w -> s) -> s -- basically foldl on the stream values makelist m = reverse $ run m [] (flip (:))
-- s is the type of the object to stream, r is the return type type StreamFunc s r = forall b. b -> (b -> s -> b) -> (r,b) newtype Stream s r = Stream { run' :: StreamFunc s r } instance Monad (Stream s) where return r = Stream (\s _ -> (r,s)) Stream m >>= k = Stream (\s f -> let (r,s') = (m s f) in run' (k r) s' f) instance (MonadStream w) (Stream w) where output w = Stream (\s f -> ((),f s w)) run m st f = snd $ run' m st f
What I don't like is how makelist comes out. It feels wrong to need to use reverse, and that also means that infinite streams completely fail to work. But I think it's impossible to fix with the "foldl"-style "run". Is there a better implementation of "makelist" possible with my current definition of "run"? If not, what type should "run" have so that it can work correctly?
As an example, I want to fix the implementation to make the following code work: fibs :: Stream Integer () fibs = fibs' 0 1 where fibs' x y = output y >> fibs' y (x+y)
fiblist :: [Integer] fiblist = makelist fibs
take 5 fiblist -- [1,1,2,3,5], but currently goes into an infinite loop
Thanks, -- ryan _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
participants (6)
-
apfelmus＠quantentunnel.de -
Chris Kuklewicz -
Iavor Diatchki -
Lennart Kolmodin -
Ross Paterson -
Ryan Ingram