# Foldl as foldr alternative

### From HaskellWiki

This page explains how can be written using . Yes, there is already such a page! This one explains it differently.
looks like this:
never changes in the recursion. It turns out things will be simpler later if we pull it out:

. Haskell programmers like curry, so it's natural to see as —that is, to see as a function that takes a list and returns the result of folding into the list starting with an accumulator value of . This perspective, however, is the
is a function that takes an accumulator and uses it as the initial value to fold into . With this shift of perspective, we can rewrite just a little, shifting its second argument into an explicit lambda:
fits the pattern, constructing its result in non-nil case from the list's head element () and the recursive result for its tail ():
takes an element of the list, a function produced by folding over the rest of the list, and the value of an accumulator, , "from the left". It applies to the accumulator and the list element, and passes the result forward to the function it got "on the right".
is the same function as constructed by the here, calling this e.g. for a list scans through the whole list as-if evaluating a nested lambda applied to the initial value of the accumulator,
would do.

function could even be made more clever, and inspect the current element in order to decide whether to will be able to stop early, and thus process even infinite lists:
to decide whether to process or
is of course, trivial:)

foldl

foldr

foldl

foldl :: (a -> x -> r) -> a -> [x] -> r foldl f a [] = a foldl f a (x : xs) = foldl f (f a x) xs

f

foldl :: (a -> x -> r) -> a -> [x] -> r foldl f a list = go a list where go acc [] = acc go acc (x : xs) = go (f acc x) xs

foldr

go acc xs

(go acc) xs

go a

f

a

*wrong one*for what we're trying to do here. So let's change the order of the arguments of the helper:

foldl :: (a -> x -> r) -> a -> [x] -> r foldl f a list = go2 list a where go2 [] acc = acc go2 (x : xs) acc = go2 xs (f acc x)

go2 xs

f

xs

go2

foldl :: (a -> x -> r) -> a -> [x] -> r foldl f a list = go2 list a where go2 [] = \acc -> acc go2 (x : xs) = \acc -> go2 xs (f acc x)

Believe it or not, we're almost done! How is that? Let's parenthesize a bit for emphasis:

foldl f a list = go2 list a where go2 [] = (\acc -> acc) -- nil case go2 (x : xs) = \acc -> (go2 xs) (f acc x) -- construct x (go2 xs)

go2

foldr

x

go2 xs

go2 list = foldr construct (\acc -> acc) list where construct x r = \acc -> r (f acc x)

Substituting this in,

foldl f a list = (foldr construct (\acc -> acc) list) a where construct x r = \acc -> r (f acc x)

construct

x

r

acc

f

r

construct

[x,y,...,z]

(\acc-> (\acc-> (... (\acc-> (\acc -> acc) (f acc z)) ...) (f acc y)) (f acc x)) a

which creates the chain of evaluations as in

(\acc -> acc) (f (... (f (f a x) y) ...) z)

foldl

construct

*process*the list*further*or not. Thus, such a variant offoldl

foldlWhile t f a list = foldr cons (\acc -> acc) list a where cons x r = \acc -> if t x then r (f acc x) else acc

foldl

*skip*the current element, then it's

foldlIf t f a list = foldr cons (\acc -> acc) list a where cons x r = \acc -> if t x then r (f acc x) else r acc

foldr

foldrIf t f a list = foldr cons a list where cons x r | t x = f x r | otherwise = r

Another variation is (a more strict and more general)

foldl'Breaking break reduced reducer acc list = foldr cons (\acc -> acc) list acc where cons x r acc | break acc x = reduced acc x | otherwise = r $! reducer acc x