[Haskell-cafe] generalized, tail-recursive left fold that can

[Roman Cheplyaka]

Thanks, I see now where my mistake was.

Laziness (or call by name) is needed to make the step from

  (\e a z -> a (f z e))
    (head l)
    (foldr (\e a z -> a (f z e)) id (tail l) z)
    (f z (head l))

to

  \z -> foldr (\e a z -> a (f z e)) id (tail l) (f z (head l))

without evaluating foldr further.

Roman
    
* oleg at okmij.org <oleg at okmij.org> [2013-02-20 04:23:34-0000]
> 
> > > That said, to express foldl via foldr, we need a higher-order
> > > fold. There are various problems with higher-order folds, related to
> > > the cost of building closures. The problems are especially severe 
> > > in strict languages or strict contexts. Indeed,
> > > 
> > > foldl_via_foldr f z l = foldr (\e a z -> a (f z e)) id l z
> > > 
> > > first constructs the closure and then applies it to z. The closure has
> > > the same structure as the list -- it is isomorphic to the
> > > list. However, the closure representation of a list takes typically
> > > quite more space than the list. So, in strict languages, expressing
> > > foldl via foldr is a really bad idea. It won't work for big lists.
> >
> > If we unroll foldr once (assuming l is not empty), we'll get
> >
> >   \z -> foldr (\e a z -> a (f z e)) id (tail l) (f z (head l))
> >
> > which is a (shallow) closure. In order to observe what you describe (a
> > closure isomorphic to the list) we'd need a language which does
> > reductions inside closures.
> 
> I should've elaborated this point.
> 
> Let us consider monadic versions of foldr and foldl. First, monads,
> sort of emulate strict contexts, making it easier to see when
> closures are constructed. Second, we can easily add tracing.
> 
> 
> import Control.Monad.Trans
> 
> -- The following is just the ordinary foldr, with a specialized
> -- type for the seed: m z
> foldrM :: Monad m =>
>           (a -> m z -> m z) -> m z -> [a] -> m z
> -- The code below is identical to that of foldr
> foldrM f z [] = z
> foldrM f z (h:t) = f h (foldrM f z t)
> 
> -- foldlM is identical Control.Monad.foldM 
> -- Its code is shown below for reference.
> foldlM, foldlM' :: Monad m =>
>           (z -> a -> m z) -> z -> [a] -> m z
> foldlM f z []    = return z
> foldlM f z (h:t) = f z h >>= \z' -> foldlM f z' t
> 
> t1 = foldlM (\z a -> putStrLn ("foldlM: " ++ show a) >>
>                      return (a:z)) [] [1,2,3]
> 
> {-
> foldlM: 1
> foldlM: 2
> foldlM: 3
> [3,2,1]
> -}
> 
> -- foldlM' is foldlM expressed via foldrM
> foldlM' f z l = 
>     foldrM (\e am -> am >>= \k -> return $ \z -> f z e >>= k)
>            (return return) l >>= \f -> f z
> 
> -- foldrM'' is foldlM' with trace printing
> foldlM'' :: (MonadIO m, Show a) =>
>           (z -> a -> m z) -> z -> [a] -> m z
> foldlM'' f z l = 
>     foldrM (\e am -> liftIO (putStrLn $ "foldR: " ++ show e) >>
>             am >>= \k -> return $ \z -> f z e >>= k)
>            (return return) l >>= \f -> f z
> 
> 
> t2 = foldlM'' (\z a -> putStrLn ("foldlM: " ++ show a) >>
>                        return (a:z)) [] [1,2,3]
> 
> {-
> foldR: 1
> foldR: 2
> foldR: 3
> foldlM: 1
> foldlM: 2
> foldlM: 3
> [3,2,1]
> -}
> 
> 
> As we can see from the trace printing, first the whole list is
> traversed by foldR and the closure is constructed. Only after foldr
> has finished, the closure is applied to z ([] in our case), and
> foldl's function f gets a chance to work. The list is effectively
> traversed twice, which means the `copy' of the list has to be
> allocated -- that is, the closure that incorporates the calls to
> f e1, f e2, etc. 
>