# Foldl as foldr alternative

### From HaskellWiki

(Difference between revisions)

(add skipping foldl (and foldr, for comparison)) |
(add a stricter, more general variant for foldlWhile, foldl'Breaking) |
||

Line 138: | Line 138: | ||

cons x r | t x = f x r | cons x r | t x = f x r | ||

| otherwise = r | | otherwise = r | ||

+ | </haskell> | ||

+ | |||

+ | Another variation is (a more strict and more general) | ||

+ | |||

+ | <haskell> | ||

+ | 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 | ||

</haskell> | </haskell> |

## Latest revision as of 14:21, 3 January 2018

This page explains howfoldl

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 of

foldl

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