Question about foldl function in Racket. (Functional programming)

Question

So I have this line of code:

(foldl cons '() '(1 2 3 4))

And the output I get when I run it is this:

'(4 3 2 1)

Can you please explain to me why I don’t get '(1 2 3 4) instead?

I read the documentation but I am still a bit confused about how foldl works. Also if I wanted to define foldl how would I specify in Racket that the function can take a variable amount of lists as arguments?

Thanks!

Will Ness Will Ness · Accepted Answer · 2020-01-30T21:11:14

Yes. By the definition of left fold, the combining function is called with the first element of the list and the accumulated result so far, and the result of that call is passed (as the new, updated accumulated result so far) to the recursive invocation of foldl with the same combining function and the rest of the list:

(foldl  cons                          '()   '(1 2 3))
=
(foldl  cons                  (cons 1 '())    '(2 3))
=
(foldl  cons          (cons 2 (cons 1 '()))     '(3))
=
(foldl  cons  (cons 3 (cons 2 (cons 1 '())))     '())
=
              (cons 3 (cons 2 (cons 1 '())))

And when the list is empty, the accumulated result so far is returned as the final result.

To your second question, variadic functions in Scheme are specified with the dot . in the argument list, like so:

(define (fold-left f acc . lists)
  (if (null? (first lists))            ;; assume all have same length
      acc
      (apply fold-left                 ;; recursive call
             f
             (apply f  (append (map first lists)   ;; combine first elts
                               (list acc)))        ;;  with result so far
             (map rest lists))))       ;; the rests of lists

Indeed,

(fold-left (lambda (a b result)
             (* result (- a b)))
           1
           '(1 2 3)
           '(4 5 6))

returns -27.

Question about foldl function in Racket. (Functional programming)

1 Answers