Search code examples
schemeracketfold

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


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.


Solution

  • 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))