Confused by "Init / Base" in foldr / foldl (Racket)

Question

I am close to understanding foldr and foldl , but not quite there.

I understand that foldr is basically an implementation of the execution stack of some function in the list from right to left.

So for foldr :

 (define (fn-for-lon lon) (cond [(empty? lon) 0] [else (+ (first lon) (fn-for-lon (rest lon))])) 

It is basically the equivalent of:

 (foldr + 0 lon) 

And I understand that foldl is basically a tail-recursive, battery-powered version that goes from left to right.

So for foldl :

 (define (fn-for-lon lon0) (local [(define (fn-for-lon lon acc) (cond [(empty? lon) acc] [else (fn-for-lon (rest lon) (+ acc (first lon)))] (fn-for-lon lon0))) 

It is basically the equivalent of:

 (foldl + 0 lon) 

But what happens when you enter two variables? I tried to read this topic, but I just can’t understand, because no one talks about what happens behind the scenes.

I am really confused by whether the second argument is “basic” or “init”, or whether it depends only on whether one or two variables are taken in the function. In the foldl example that I gave, this is apparently the value of init acc (which I suppose is ultimately the base value), but in foldr this will be the main case. Is it just because I only use the operator for proc?

 (foldr (lambda (ab) (cons (add1 a) b)) empty (list 1 2 3 4)) 

Something like the above, I really lose all understanding. I understand what to do, but not quite what is happening in the background. It makes me lose track of more complex issues.

Is it the same and b is just empty ? Temporarily press b on (rest lon) ?

 (define (fn-for-lon lon) (cond [(empty? lon) empty] [else (cons (add1 (first lon)) (fn-for-lon (rest lon)))])) 

Answer 1

Take a look at the actual foldl from Racket:

  (define foldl (case-lambda [(f init l) (check-fold 'foldl f init l null) (let loop ([init init] [ll]) (if (null? l) init (loop (f (car l) init) (cdr l))))] [(f init l . ls) (check-fold 'foldl f init l ls) (let loop ([init init] [ls (cons l ls)]) (if (pair? (car ls)) ; `check-fold' ensures all lists have equal length (loop (apply f (mapadd car ls init)) (map cdr ls)) init))])) 

We see two cases: the first case (f init l) exists for efficiency. If only one list l , we get a quick version of foldl .

The second case (f init l . ls) is the one you need. Before we look at this, we need to first look at the mapadd helper function.

The call (mapadd fl last) apply f to all elements of the list l and will not result in `last.

Example:

 > (mapadd sqr '(1 2 3 4) 42) '(1 4 9 16 42) 

mapadd definition:

  (define (mapadd fl last) (let loop ([ll]) (if (null? l) (list last) (cons (f (car l)) (loop (cdr l)))))) 

Back to the (f init l . ls) case of foldl .

Removing error checking comes down to

  (let loop ([init init] [ls (cons l ls)]) (if (pair? (car ls)) (loop (apply f (mapadd car ls init)) (map cdr ls)) init))])) 

The initial init value is associated with a variable (also called) init , which is used to accumulate the result. The ls variable is when the loop begins to snap to the list of all lists with which foldl is foldl . Please note that these lists are the same length. The loop continues until all the lists in ls are empty. The test (pair? (car ls)) checks if the first list is empty, but remember that the lists are the same length.

Now init is replaced with (apply f (mapadd car ls init)) . This call first takes the first element of each list and agrees to the current value of init . Then f is applied.

Consider this example: (foldl + 0 '(1 2) '(10 11)) , which evaluates to 24. Here

  f = + init = 0 ls = ((1 2) (10 11)) 

AND

  > (mapadd car '((1 2) (10 11)) 0) '(1 10 0) 

So

  > (apply + (mapadd car '((1 2) (10 11)) 0)) 11 

In the next round we will see

  f = + init = 11 ls = ((2) (11)) 

And (apply + (mapadd car ls init) will be evaluated to 24.

An alternative way to explain the example is (foldl + 0 '(1 2) '(10 11)) .

 (define init 0) (for ([x (in-list '( 1 2))] ; x and y loop in parallel [y (in-list '(10 11))]) (set! init (apply + (list xy init)))) ; accumulate result in init init 

The complication in the foldl implementation is that it is not known how many lists are used.

UPDATE

When foldl is used in practice, it is best to think of foldl in terms of its specification, rather than its implementation.

This is how foldl indicated when called with two lists.

Call:

  (foldl f x0 (cons a0 (cons a1 (cons a2 '()))) (cons b0 (cons b1 (cons b2 '())))) 

evaluated the same way

 (f a2 b2 (f a1 b1 (f a0 b0 x0))) 

does.

As a check, we can try:

 > (foldl (λ args (cons 'f args)) 'x0 (cons 'a0 (cons 'a1 (cons 'a2 '()))) (cons 'b0 (cons 'b1 (cons 'b2 '())))) '(f a2 b2 (f a1 b1 (f a0 b0 x0))) 

Note that (λ args (cons 'f args)) is a function that simply adds the character f to its argument list.

Answer 2

The second argument to foldl and foldr always init . Your provided function should always take 2 arguments if you go through one list, and the second argument to this function is the accumulated value ( init initially, and then the return value of the previous call to your function).

(In your previous use cases, + you can think of it as the same as (lambda (ab) (+ ab)) . In this case, a is a list item and b is an accumulated value.)

When you call foldl or foldr with N lists, your provided function should take N + 1 arguments; the first N arguments correspond to the next element from each list, and the last argument is the accumulated value ( init initially, and then the return value of the previous call to your function).

---

Would it help you to understand if I provided (my own) options for foldl and foldr ? Here they are:

 (define foldl (case-lambda ;; one list [(func init lst) (let loop ([result init] [rest lst]) (if (null? rest) result (loop (func (car rest) result) (cdr rest))))] ;; multiple lists [(func init list1 . list2+) (let loop ([result init] [rests (cons list1 list2+)]) (if (ormap null? rests) result (loop (apply func (append (map car rests) (list result))) (map cdr rests))))])) (define foldr (case-lambda ;; one list [(func init lst) (let recur ([rest lst]) (if (null? rest) init (func (car rest) (recur (cdr rest)))))] ;; multiple lists [(func init list1 . list2+) (let recur ([rests (cons list1 list2+)]) (if (ormap null? rests) init (apply func (append (map car rests) (list (recur (map cdr rests)))))))])) 

Answer 3

The folds really help us, not confuse us. They capture a specific recursion pattern for sequential reuse. Folds are defined abstractly, and they are most easily understood abstractly. The only reason to understand the specifics of your language folds implementation is to make sure that the implementation is valid.

Whenever we have a specific recursion pattern (entry in equational pseudo-code),

 foo(xs) = matches xs with Empty -> zero Cons(head,tail) -> comb(head, foo(tail)) 

where we combine the list title with the recursive result of calling foo at the tail of the list, we have a (right) fold, and calling foo(xs) is the same as calling foldr(comb, zero, xs) . How exactly this is implemented in our language of choice does not matter.

As you can see, the union function (operator or something else) should take the "current element" of the list as the first argument, and the recursive result as the last. Only when there are no more elements in the list, the zero value is used instead of the recursive result, initiating the chain of comb calculations performed on the return trip from the case of the recursion base, Empty .

So, when reading the definitions of folding, we always consider the first argument of the union function as "the current element , mentally, and the last as the " recursive result of processing the rest of the list ".

Why is this wording about the "current" element? Because, presenting our list [a,b,c,...,n] , the call to foldr(comb, z, [a,b,c,...,n]) matches the above pattern in the same way as call

 comb(a, foldr(comb, z, [b,c,d,...,n])) == comb(a, comb(b, comb(c, ......, comb(n, z)......))) 

This, in a certain sense, is the definition of the right times on lists, aka, the catamorphism of a list.

Racket adds to this the ability to simultaneously stack multiple lists in parallel. Naturally, the arrangement of the arguments to the union function remains unchanged. all arguments, but the latter correspond to the current elements, each of each argument list; and the last argument is a recursive result to combine them.

A similar but different pattern

 bar(xs) = matches xs with Empty -> zero Cons(head,tail) -> comb(head, tail, bar(tail)) 

which is known as parametrism (see maplist vs. mapcar in Common Lisp).

Since both capture recursions, zero corresponds to the base case of inductive data definition, we recurs to:

 List of 'a = Empty or Cons('a, List of 'a) 

Starting from the base case, we get a double pattern, creating a value before the recursive call, aot after it, as mentioned above, with

 baz(zero, xs) = matches xs with Empty -> zero Cons(head,tail) -> baz( comb(head, zero), tail) 

which you will recognize as the left fold (and zero no longer the base value), but the value that is built on the go is ndash; or accumulates, and finally returns when the Empty event occurs).

So, this is just the difference between (1+(2+(3+...(n+0)...))) with the right button and (...(((0+1)+2)+3)...+n) , on the left _{(showing it with the help, the order of the arguments is reversed, for the essence of the view)} . One result will be the same as the other when (+) is an associative operation. Which, for numbers, is.

See also this answer .