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

[Lennart Kolmodin]

-----BEGIN PGP SIGNED MESSAGE-----
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) ?

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