[Haskell-cafe] laziness

jeff p mutjida at gmail.com
Sun Dec 10 03:21:19 EST 2006


Hello,

> If you really want a right fold where the state flows from left to
> right, you could try this:
>
>     foldrSt st f v [] = v st
>     foldrSt st f v (x:xs) =
>         let (st', f') = f st x
>         in f' (foldrSt st' f v xs)
>
In full monadic generality, we could define:

    foldrM f v [] = v
    foldrM f v (x:xs) = do
        f' <- f x
        v' <- foldrM f v xs
        f' v'

    --
    -- test functions
    --
    fooM x = return (\l -> return $ x : l)

    foo1M x = do  --
        st <- get
        put $ st + 1
        return (\l -> return $ (x + st) : l)

and get the following evaluations (with Control.Monad.State imported):

    *Cafe> runState (foldrM fooM (return []) [1..10]) 0
    ([1,2,3,4,5,6,7,8,9,10],0)
    *Cafe> runState (foldrM foo1M (return []) [1..10]) 0
    ([1,3,5,7,9,11,13,15,17,19],10)

Of course replacing [1..10] with [1..] will cause non-termination,
since runState returns the final state as well as the result. However
we also get:

    *Cafe> take 10 $ evalState (foldrM fooM (return []) [1..]) 0
    [1,2,3,4,5,6,7,8,9,10]
    *Cafe> take 10 $ evalState (foldrM foo1M (return []) [1..]) 0
    [1,3,5,7,9,11,13,15,17,19]

since evalState discards the final state.

However, if you really just want to process infinite lists, you should
be using map and filter (or mapM and filterM).

-Jeff


More information about the Haskell-Cafe mailing list