[Haskell] Re: Converting a 'streaming' monad into a list

Lennart Kolmodin kolmodin at dtek.chalmers.se
Sat Dec 30 11:45:12 EST 2006

Hash: SHA1

apfelmus at 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) ?

  Lennart Kolmodin
Version: GnuPG v1.4.5 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org


More information about the Haskell mailing list