foldl_foldr.lhs

> module FoldlFoldr where

Implementation of `foldl'`

> foldl' :: (b -> a -> b) -> b -> [a] -> b
> foldl' f acc [] = acc
> foldl' f acc (x : xs) =
>     let acc1 = f acc x
>     in acc1 `seq` foldl' f acc1 xs

Extracting common parameters

> foldl'_1 :: (b -> a -> b) -> b -> [a] -> b
> foldl'_1 f acc xs = go acc xs
>     where
>         go acc [] = acc
>         go acc (x : xs) =
>             let acc1 = f acc x
>             in acc1 `seq` go acc1 xs

Realization: The recursion isn't the same at each step. The accumulator is different each time.

(It's not unlike how in a depth-first search you might add a parameter to track the current depth.)

Make the accumulator a parameter of the result to compensate for the fact.

> foldl'_2 :: (b -> a -> b) -> b -> [a] -> b
> foldl'_2 f acc xs = go xs acc
>     where
>         go [] = \acc -> acc
>         go (x : xs) = \acc ->
>             let acc1 = f acc x
>             in acc1 `seq` (go xs) acc1

Now the recursion matches up with the structure of the list, which means that it can be turned into a `foldr`

> foldl'_3 :: (b -> a -> b) -> b -> [a] -> b
> foldl'_3 f acc xs = foldr step initial xs acc
>     where
>         initial = \acc -> acc
>         step x next = \acc ->
>             let acc1 = f acc x
>             in acc1 `seq` next acc1