[Haskell-cafe] Monad transformers [Stacking monads]

[Daniel Fischer]

Am Dienstag, 7. Oktober 2008 22:09 schrieb Andrew Coppin:
> Daniel Fischer wrote:
> > Am Dienstag, 7. Oktober 2008 20:27 schrieb Andrew Coppin:
> >> Basically, the core code is something like
> >>
> >>   raw_bind :: (Monad m) => [[x]] -> (x -> m (ResultSet y)) -> m
> >> (ResultSet y)
> >>   raw_bind [] f = return empty
> >>   raw_bind (xs:xss) f = do
> >>     rsYs <- mapM f xs
> >>     rsZ <- raw_bind xss f
> >>     return (foldr union (cost rsZ) rsYs)
> >>
> >> As you can see, this generates all of rsZ before attempting to return
> >> anything to the caller. And I'm really struggling to see any way to
> >> avoid that.
> >
> > Maybe it is as simple as
> >
> > raw_bind (xs:xss) f = do
> >      rsYs <- mapM f xs
> >      ~rsZ <- raw_bind xss f
> >      return (foldr union (cost rsZ) rsYs)
> >
> > then rsZ should only be evaluated when it's needed
>
> Ooo... "lazy pattern matching"? Can somebody explain to me, _very
> slowy_, exactly what that means?
>
> If I'm doing this right, it seems that
>
>   rsZ <- raw_bind xss f
>   ...
>
> desugards to
>
>   raw_bind xss f >>= \rsZ -> ...
>
> If I'm not mistaken, the rsZ variable shouldn't be evaluated until
> needed *anyway*, so what is lazy pattern matching buying me here?

That depends on how your Monad (and union) is implemented, it may or may not 
make a difference. I must admit that I didn't really look at the code you 
posted, so I don't know what would be the case here. It was just an easy 
thing to try which *might* help.
I will take a look, can't guarantee any result.

>
> Also, suppose I stack ResultSetT on top of IO. In that case, "f" is
> allowed to perform externally-visible I/O operations. If there really
> *is* a way to delay the execution of certain calls until the data is
> needed... well that doesn't look right somehow. In fact, it looks like
> what I'm trying to do *should* be impossible. :-/ Oh dear...

To delay computations in IO until needed, you can use unsafeInterleaveIO:


uiSeq :: [IO Int] -> IO [Int]
uiSeq [] = do
    putStrLn "End of list"
    return []
uiSeq (a:as) = do
    x <- a
    putStrLn $ "got the value " ++ show x
    xs <- unsafeInterleaveIO $ uiSeq as
    return (x:xs)

verbRet :: Int -> IO Int
verbRet k = do
    putStrLn $ "Returning " ++ show k
    return k

*Main> fmap (take 3) $ uiSeq [verbRet k | k <- [1 .. 10]]
Returning 1
got the value 1
[1Returning 2
got the value 2
,2Returning 3
got the value 3
,3]
*Main> fmap (take 3) $ sequence [verbRet k | k <- [1 .. 10]]
Returning 1
Returning 2
Returning 3
Returning 4
Returning 5
Returning 6
Returning 7
Returning 8
Returning 9
Returning 10
[1,2,3]

But unsafeInterleaveIO doesn't have its first six letters without a reason, so 
be careful when you want to use it (in general, don't).
And of course you can't use it in generic monad transformer code, you might 
however be able to use

class Monad m => LazyMonad m where
	lazyBind :: m a -> (a -> m b) -> m b
	lazySequence :: [m a] -> m [a]

instance LazyMonad IO where
	lazyBind  ma f = do
            a <- unsafeInterleaveIO ma
            f a
        lazySequence [] = return []
	lazySequence (a:as) = do
	    x <- a
	    xs <- unsafeInterleaveIO $ lazySequence as
	    return (x:xs)