How do non-binary foldl and foldr work in Racket?

Question

I'm familiar with the underlying workings and differences of foldl and foldr over a single list. However, in Racket, you can use folds on multiple lists. For example, you can find the difference of elements in two lists by writing

; (mapMinus '(3 4) '(1 2)) => '(2 2)
(define (mapMinus lst0 lst1)
  (foldl (λ (hd0 hd1 acc) (cons (- hd0 hd1) acc)) '() lst0 lst1))

How exactly do Racket's implementations of foldl and foldr work to handle multiple lists? The Racket source code for foldl is available on GitHub here, but I don't know Chez Scheme well enough to understand it.

I don't grok your question. Do you need help understanding the code in your post, or the code in the linked `foldl` procedure from Chez Scheme? or do you ask about `fold`s that apply to multiple lists in general? — Óscar López, Feb 27 '20 at 20:34
Are you asking about the behavior of `foldl` and how to use it with multiple lists, or are you asking about how to implement an arbitrary-arity `foldl` function yourself? — Alex Knauth, Feb 27 '20 at 20:36
I'm sorry about the confusion! I was just writing that function as an example of Racket using fold over multiple lists to make it obvious this was a question about Racket's unique folds rather than a question about how folds work in general. — BrainFRZ, Feb 27 '20 at 21:33

Óscar López · Accepted Answer · 2020-02-27T23:12:56.933

A fold that operates over multiple lists simply applies its lambda element-wise on all of the lists, simultaneously. Perhaps a simplified implementation (with no error checking, etc.) of it will make things clearer; let's compare a standard implementation of foldr (which IMHO is slightly simpler to understand than foldl):

(define (foldr proc init lst)
  (if (null? lst)
      init
      (proc (car lst)
            (foldr proc init (cdr lst)))))

With an implementation that accepts multiple lists:

(define (foldr proc init . lst) ; lst is a list of lists
  (if (null? (car lst)) ; all lists assumed to be of same length
      init
      ; use apply because proc can have any number of args
      (apply proc
             ; append, list are required for building the parameter list
             ; in the right way so it can be passed to (apply proc ...)
             (append (map car lst)
                     ; use apply again because it's a variadic procedure
                     (list (apply foldr proc init (map cdr lst)))))))

All the extra code in the multi-list version is for applying proc to multiple elements at the same time, getting the current element of each list (map car lst) and advancing over all the lists (map cdr lst).

Also the implementation needs to take into account that the procedure operates over a variable number of lists, assuming that the provided lambda receives the correct number of arguments (number of input lists + 1). It works as expected:

(foldr (lambda (e1 e2 acc)
         (cons (list e1 e2) acc))
       '()
       '(1 2 3)
       '(4 5 6))

=> '((1 4) (2 5) (3 6))

score 1 · Answer 2 · answered Feb 27 '20 at 22:38

I think what you really are asking is how to create a variadic function in Scheme/Racket. The answer is given at https://docs.racket-lang.org/guide/define.html, but let me just give you a quick example:

(define (foo a b . xs)
  (+ a b (length xs)))

would be equivalent to

def foo(a, b, *xs):
  return a + b + len(xs)

in Python. xs here is a list value containing the rest of the arguments.

The second piece of puzzle is, how to apply a variadic function with a list value. For that, you can use apply. Read more at https://docs.racket-lang.org/guide/application.html#%28part._apply%29. Again, here's a quick example:

(define (foo a b c) (+ a b c))
(apply foo 1 '(2 3))
;; equivalent to (foo 1 2 3)

would be equivalent to

def foo(a, b, c): return a + b + c
foo(1, *[2, 3]) ;; equivalent to foo(1, 2, 3)

With these, creating a fold that accepts multiple arguments is just a programming exercise:

(define (my-fold proc accum required-first-list . list-of-optional-lists)
  ... IMPLEMENT FOLD HERE ...)

Note that if you read the source code of Racket (which uses Chez Scheme), you will see that it uses case-lambda instead of defining the function directly. case-lambda is just a way to make the code more efficient for common usage of fold (i.e., a fold with only one list).

How do non-binary foldl and foldr work in Racket?

2 Answers2