Writing foldl as foldr confusion

convert foldl to foldr
foldl foldr

I know there are other posts about this, but mine is slightly different.

I have a function that performs the task of foldl, using foldr. I have the solution given to me, but would like help understanding.

foldlTest:: (b -> a -> b) -> [a] -> (b -> b)

foldlTest f xs = foldr (\x r b -> r (f b x))
                (\b -> b)
                xs

And It is called using something like this:

foldlTest (-) [1,2,3] 10 = -4


First thing I understand is that my function takes in 2 arguments, but 3 are given in the above test case. This means that the 10 will take part in a lambda expression I assume.

1) Does the 10 take the place of the b in b -> b? (then the b would be the initial accumulator value)

What I don't understand is what the (\x r b -> r (f b x)) part does.

2) What is the value of each of the variables? I am very confused about this lambda function.

3) What exactly does the lambda function do and how is it different from a regular foldr?

Writing foldl using foldr, Writing foldl using foldr. l foldl foldr vs foldr1 haskell foldrl haskell foldr id The above code confused me a lot, and somebody called dps rewrote it with a  Foldable is a so-called Type class and says that the type t must implement the Foldable interface, as long as it does nothing matters.. The first argument is a function which takes two arguments, the so-called accumulator which contains the already calculated result until this stage and the current element of the Foldable which is processed now.

The answer you've been given (not the one on SO, the one you cited in your question) seems to be more difficult than necessary. I assume it is intended to teach you some aspects of folds, but apparently this is not working well. I try to show what's happening and in the process answer your questions.

3) What exactly does the lambda function do and how is it different from a regular foldr?

The whole thing just builds a left fold (foldl) out of a right fold (foldr) and flips the last two arguments. It is equivalent to

foldTest f = flip (foldr (flip f))
foldTest f = flip (foldl f)

and it does so in a rather obscure way, by accumulating a function and does the flipping via a lambda.

1) Does the 10 take the place of the b in b -> b? (then the b would be the initial accumulator value) What I don't understand is what the (\x r b -> r (f b x)) part does.

Yes, correct. The 10 takes to role of the initial accumulator of a left fold.

2) What is the value of each of the variables? I am very confused about this lambda function.

To get an intuition as to what is happening, I find it helpful to do the actual lambda calculus step by step:

foldTest (-) [1,2,3] 10
foldTest (-) (1:(2:(3:[]))) 10

-- remember the definition of foldTest which is given in a point-free way
foldlTest f xs = foldr (\x r b -> r (f b x)) (\b -> b) xs

-- add the hidden parameter and you get
foldlTest f xs b' = (foldr (\x r b -> r (f b x)) (\b -> b) xs) b'

-- apply that definition with f = (-), xs = (1:(2:(3:[]))), b' = 10
(foldr (\x r b -> r ((-) b x)) (\b -> b) (1:(2:(3:[])))) 10
(foldr (\x r b -> r (b - x)) (\b -> b) (1:(2:(3:[])))) 10

-- the inner lambda function is curried, thus we can write it as
-- \x r (\b -> r (b - x)), which is equivalent but will be handy later on.
(
  foldr (\x r -> (\b -> r (b - x))) (\b -> b) (1:(2:(3:[])))
) 10

-- keep in mind foldr is defined as
foldr f' b'' []      = b''
foldr f' b'' (x:xs') = f' x (foldr f' b'' xs')

-- apply second row of foldr with f' = (\x r -> (\b -> r (b - x))),
-- b'' = (\b -> b), x = 1 and xs' = (2:(3:[]))
(
  (\x r -> (\b -> r (b - x))) 1 (foldr (\x r -> (\b -> r (b - x))) (\b -> b) (2:(3:[])))
) 10

-- apply accumulation lambda for the first time with x = 1,
-- r = foldr (\x r -> (\b -> r (b - x))) (\b -> b) (2:(3:[])) gives
(
  \b -> (foldr (\x r -> (\b -> r (b - x))) (\b -> b) (2:(3:[]))) (b - 1)
) 10

-- now we repeat the process for the inner folds
(
  \b -> (
    foldr (\x r -> (\b -> r (b - x))) (\b -> b) (2:(3:[]))
  ) (b - 1)
) 10
(
  \b -> (
    (\x r -> (\b -> r (b - x))) 2 (foldr (\x r -> (\b -> r (b - x))) (\b -> b) (3:[]))
  ) (b - 1)
) 10
(
  \b -> (
    \b -> (foldr (\x r -> (\b -> r (b - x))) (\b -> b) (3:[])) (b - 2)
  ) (b - 1)
) 10
(
  \b -> (
    \b -> (
      foldr (\x r -> (\b -> r (b - x))) (\b -> b) (3:[])
    ) (b - 2)
  ) (b - 1)
) 10
(
  \b -> (
    \b -> (
      (\x r -> (\b -> r (b - x))) 3 (foldr (\x r -> (\b -> r (b - x))) (\b -> b) [])
    ) (b - 2)
  ) (b - 1)
) 10
(
  \b -> (
    \b -> (
      \b -> (foldr (\x r -> (\b -> r (b - x))) (\b -> b) [])) (b - 3)
    ) (b - 2)
  ) (b - 1)
) 10
(
  \b -> (
    \b -> (
      \b -> (
        foldr (\x r -> (\b -> r (b - x))) (\b -> b) []
      ) (b - 3)
    ) (b - 2)
  ) (b - 1)
) 10

-- Now the first line of foldr's definition comes in to play
(
  \b -> (
    \b -> (
      \b -> (
        \b -> b
      ) (b - 3)
    ) (b - 2)
  ) (b - 1)
) 10

-- applying those lambdas gives us
(
  \b -> (
    \b -> (
      \b -> (
        \b -> b
      ) (b - 3)
    ) (b - 2)
  ) (b - 1)
) 10

-- So we can see that the foldTest function built another function
-- doing what we want:
(\b -> (\b -> (\b -> (\b -> b) (b - 3)) (b - 2)) (b - 1)) 10
(\b -> (\b -> (\b -> b) (b - 3)) (b - 2)) (10 - 1)
(\b -> (\b -> b) (b - 3)) ((10 - 1) - 2)
(\b -> b) (((10 - 1) - 2) - 3)
(((10 - 1) - 2) - 3)
((9 - 2) - 3)
(7 - 3)
4

Writing foldl using foldr - haskell - php, You can write it with a lambda if you want: foldl f a bs = foldr (\b g x -> g (f x b)) id bs uses 3 parameters, I'm complelely confused This is confusing and magical! Remember, both foldl and foldr are curried, so that we can leave out the list argument and write val sum = foldl (fn (x,a) => x+a) 0 val concat = foldr (fn (x,a) => x^a) "" We can do even better.

By the definition of foldlTest, we have

foldlTest (-) xs b = foldr g n xs b
    where
    n     b = b
    g x r b = r (b - x)

By the definition of foldr, we have

foldr  g  n  [x,y,z]     =  g x (foldr  g  n  [y,z])

but also

foldr  g  n  [x,y,z]  b  =  g x (foldr  g  n  [y,z])  b      -- (1)
                                 ---- r -----------
                         =       foldr  g  n  [y,z]  (b-x)

(when used "inside" the foldlTest), and so, by repeated application of (1),

                         =  g y (foldr  g  n  [z])   (b-x)
                         =       foldr  g  n  [z]   ((b-x)-y)
                         =  g z (foldr  g  n  [] )  ((b-x)-y)
                         =       foldr  g  n  []   (((b-x)-y)-z)
                         =                 n       (((b-x)-y)-z)
                         =                         (((b-x)-y)-z)

Thus an expression which is equivalent to the left fold is built by the right fold straight up, because g is tail recursive. And thus

foldlTest (-)  [1,2,3]  10
--             [x,y,z]  b
==
(((10 - 1) - 2) - 3)) 
==
foldl  (-)  10  [1,2,3]

and so we see that no, the b in the n = (\b -> b) does not accept the 10, but rather it accepts the whole expression equivalent to the left fold that has been built by the right fold.

But yes, 10 is the initial accumulator value in the expression equivalent of the left fold, as intended, that has been built by the right fold.

Real World Haskell: Code You Can Believe In, Like foldl, foldr takes a function and a base case (what to do when the input foldr step [] xs where step x ys = f x : ys In fact, we can even write foldl using foldr! foldl(:Goal, +List1, +List2, +List3, +List4, +V0, -V) Fold a list, using arguments of the list as left argument. The foldl family of predicates is defined by:

Someone asked me to derive foldl from foldr: is there a better way , It is not true that either foldl or foldr process the list "in reverse", and I wish people From my searches, most writing I could find about type-level programming in  Fold functions come in different kinds, the two main linear ones are foldl and foldr. foldl. foldl, for "fold left", is left associative. Think of foldl as "fold from the left" (image courtesy of Wikipedia): Let ⊗ be a variable bound to the function of two arguments f in the diagram above. The foldl function can be defined as follows:

The usual type signatures for foldl and foldr are confusing : haskell, The usual type signatures for foldl and foldr are confusing. Here are the type signatures given for foldl and foldr in the Prelude: Hey, I'm just starting to learn Haskell and I was interested in eventually writing a simple algo trader with it. Usually the choice is between foldr and foldl', since foldl and foldl' are the same except for their strictness properties, so if both return a result, it must be the same. foldl' is the more efficient way to arrive at that result because it doesn't build a huge thunk.

Chapter 4. Functional programming, Usually, when we define or apply a function in Haskell, we write the name of the single quote can be easy to miss, which can lead to confusion on the part of readers. Perhaps surprisingly, though, we can write filter as a fold, using foldr . Note that it is not necessary to pass the list itself when defining functions over lists using foldr or foldl. The problem with your solution is that you drop the head of the list and then apply the map over the list and this is why the head of the list is missing when the result is shown.

Comments
  • It's hard for me to follow most of the details (I'm barely beyond beginner at Haskell myself), but I can offer some pointers. Firstly, foldTest has its last 2 arguments flipped in comparison to foldl, and then the final argument (the initial accumulator, of type b) has been "left out" - so it's given in a form where it takes a fold function and a list, and results in a b -> b function. And it constructs this function by (right) folding over the list - so the initial accumulator value must itself be a function, which is what r is in the lambda. And b is its argument.
  • Um, I'm getting foldlTest (-) [1,2,3] 10 = 4 (positive). Same result from foldl (-) 10 [1, 2, 3], and foldr (flip (-)) 10 [1, 2, 3]. And in general (for finite lists) foldl f z xs = foldr (flip f) z xs. Note (flip (flip f)) === f.
  • I realise I've been a bit circular here, in that I've worked backwards from the implementation of the lambda to what its type must be, then tried to imagine what the implementation might be based on the type. So really you can (and arguably should!) ignore that particular section where I say there are only 2 non-trivial ways to implement it, and skip to the details as to how the actual lambda given implements foldl. I did say this would be rambling!