fold-left(3scm)

✨ fold-left, fold-right — list iteration and recursion operators ✨

okay bestie, so we're in the Scheme Programmer's Manual 🎀 and today's main characters are fold-left and fold-right. yes, THE fold girls. let's get into it 💅

---

🦋 LIBRARY 🦋

(import (rnrs))                     ;R6RS
(import (rnrs lists))               ;R6RS

two ways to get in, both iconic, both R6RS. pick your fave 🫶

---

🌸 SYNOPSIS 🌸

(fold-left combine nil list1 list2 ... listn)
(fold-right combine nil list1 list2 ... listn)

that's the whole vibe check right there ✨

---

💖 DESCRIPTION 💖

so these procedures apply combine to elements of the lists — fold-left goes left to right, fold-right goes right to left. simple. slay.

they also pass it an argument called the accumulator (iykyk), which starts out as nil and gets updated to whatever combine returns after each application. it's giving main character energy, honestly — the accumulator is literally the whole personality of the fold 😭

the difference, bestie: fold-left passes the accumulator as the first argument to combine, and fold-right passes it as the last argument. the other arguments are the elements from the lists — like, the first time combine gets called it gets the first (or last) element from each list, then the second (or second to last) element from each list, etc. combine should return a single value: the new accumulator. no cap 🔥

when the lists have been exhausted, you get the accumulator back. which implies — and this is important — nil is returned immediately if the lists are empty. like, immediately immediately 💀

combine is always called in the same dynamic environment as fold-left or fold-right itself. and it should not mutate the list arguments. don't do that. we don't do that here 🙈

---

🧚 IMPLEMENTATION NOTES 🧚

implementation responsibilities, aka the homework your Scheme implementation has to do:

• the implementation should check that the lists all have the same length
• the implementation must check the restrictions on combine to the extent performed by applying it as described
• an implementation may check whether combine is an appropriate argument before applying it

that's the whole list. you're welcome ✨

---

🍓 RETURN VALUES 🍓

these procedures return a single value: the last accumulator value. one value. single. not a list, not a vibe, one value 💅

---

🌈 EXAMPLES 🌈

okay this is the fun part, buckle up 🎢

(fold-left + 0 '(1 2 3 4 5))
    =>  15

(fold-left (lambda (a e) (cons e a)) '()
           '(1 2 3 4 5))
    =>  (5 4 3 2 1)

(fold-left (lambda (count x)
             (if (odd? x) (+ count 1) count))
           0
           '(3 1 4 1 5 9 2 6 5 3))
    =>  7

(fold-left (lambda (max-len s)
             (max max-len (string-length s)))
           0
           '("longest" "long" "longer"))
    =>  7

(fold-left cons '(q) '(a b c))
    =>  ((((q) . a) . b) . c)

(fold-left + 0 '(1 2 3) '(4 5 6))
    =>  21

now the flip side, fold-right era 💫

(fold-right + 0 '(1 2 3 4 5))
    =>  15

(fold-right cons '() '(1 2 3 4 5))
    =>  (1 2 3 4 5)

(fold-right (lambda (x l)
              (if (odd? x) (cons x l) l))
            '()
            '(3 1 4 1 5 9 2 6 5))
    =>  (3 1 1 5 9 5)

(fold-right cons '(q) '(a b c))
    =>  (a b c q)

(fold-right + 0 '(1 2 3) '(4 5 6))
    =>  21

and then there's this absolute legend of an example, where they do side effects to show you the order 👀

;; Side-effects in fold are not pretty,
;; but this should highlight the differences
;; between fold-left and fold-right.

(fold-left (lambda (acc x)
             (write (list acc x))
             (newline)
             (+ acc x))
           0
           '(1 2 3 5 7 11))
  -> (0 1)
  -> (1 2)
  -> (3 3)
  -> (6 5)
  -> (11 7)
  -> (18 11)
    => 29

(fold-right (lambda (x acc)
              (write (list x acc))
              (newline)
              (+ x acc))
            0
            '(1 2 3 5 7 11))
  -> (11 0)
  -> (7 11)
  -> (5 18)
  -> (3 23)
  -> (2 26)
  -> (1 28)
    => 29

see?? SAME ANSWER, DIFFERENT ORDER 🔥🔥 29 both times but the journey is completely different. that's the whole point, bestie.

---

👑 APPLICATION USAGE 👑

these are higher-order procedures that express list iteration and recursion. they're often more compact and expressive than writing the corresponding code without them — which is a very polite way of saying "stop writing the long version, use the fold, it's cuter" 💅✨

---

💀 COMPATIBILITY 💀

these procedures are unique to R6RS, but equivalents can be found in SRFI-1. so if you're on another Scheme, don't panic, just go find the SRFI-1 version 🫶

---

🎀 ERRORS 🎀

this procedure can raise exceptions with the following condition types:

• &assertion (R6RS) — the wrong number of arguments was passed, or an argument was outside its domain. in particular, the lists should all have the same length and combine must be a procedure. it should accept one more argument than there are lists and return a single value.

yeah. read the last sentence twice, it's the one that gets people 😭

---

🦋 SEE ALSO 🦋

• map(3scm)
• let(7scm)
• do(7scm)

go read those next, they're all in the same friend group 💜

---

⭐ STANDARDS ⭐

R6RS

---

🌸 HISTORY 🌸

these procedures appear in SRFI-1 under the names fold and fold-right, where they are respectively referred to as "[t]he fundamental list iterator" and "[t]he fundamental list recursion operator". like, literal royalty 👑✨

---

🫶 AUTHORS 🫶

this page is part of the scheme-manpages project. it includes materials from the RnRS documents. more information can be found at https://github.com/schemedoc/manpages/.

---

aww okay that's the whole page bestie, hope you ate 💖

and finally, the cute sign-off: this masterpiece dropped on 2023-08-11 and it lives at the bottom of the page as fold-left(3scm) — that's the footer, that's the lore, that's the end 🎀✨🦋