Next: , Up: lists fold   [Index]

23.8.1 Folding usage examples

In the single list argument case, for a list of 4 elements, the return value of a left–folding with R6RS style, is computed as with: 

(fold-left kons knil ell) ≡
  (kons (kons (kons (kons knil
                          (list-ref ell 0))
                    (list-ref ell 1))
              (list-ref ell 2))
        (list-ref ell 3))

while with the “traditional” style: 

(fold kons knil ell) ≡
  (kons (list-ref ell 3)
        (kons (list-ref ell 2)
              (kons (list-ref ell 1)
                    (kons (list-ref ell 0)
                          knil))))

the return value of a right–folding with both R6RS style and “traditional” style, is computed as with: 

(fold-right kons knil ell) ≡
     (fold* kons knil ell) ≡
  (kons (list-ref ell 0)
        (kons (list-ref ell 1)
              (kons (list-ref ell 2)
                    (kons (list-ref ell 3)
                          knil))))

In the multiple list arguments case, for three lists of 4 elements, the return value of a left–folding with R6RS style, is computed as with: 

(fold-left kons knil ell0 ell1 ell2) ≡
  (kons (kons (kons (kons knil
                          (list-ref ell0 0)
                          (list-ref ell1 0)
                          (list-ref ell2 0))
                    (list-ref ell0 1)
                    (list-ref ell1 1)
                    (list-ref ell2 1))
              (list-ref ell0 2)
              (list-ref ell1 2)
              (list-ref ell2 2))
        (list-ref ell0 3)
        (list-ref ell1 3)
        (list-ref ell2 3))

while with the “traditional” style: 

(fold kons knil ell0 ell1 ell2) ≡
  (kons (list-ref ell0 3)
        (list-ref ell1 3)
        (list-ref ell2 3)
        (kons (list-ref ell0 2)
              (list-ref ell1 2)
              (list-ref ell2 2)
              (kons (list-ref ell0 1)
                    (list-ref ell1 1)
                    (list-ref ell2 1)
                    (kons (list-ref ell0 0)
                          (list-ref ell1 0)
                          (list-ref ell2 0)
                          knil))))

the return value of a right–folding with both R6RS style and “traditional” style, is computed as with: 

(fold-right kons knil ell0 ell1 ell2) ≡
     (fold* kons knil ell0 ell1 ell2) ≡
  (kons (list-ref ell0 0)
        (list-ref ell1 0)
        (list-ref ell2 0)
        (kons (list-ref ell0 1)
              (list-ref ell1 1)
              (list-ref ell2 1)
              (kons (list-ref ell0 2)
                    (list-ref ell1 2)
                    (list-ref ell2 2)
                    (kons (list-ref ell0 3)
                          (list-ref ell1 3)
                          (list-ref ell2 3)
                          knil))))

Left–folding, usage examples for fold in the single list argument case: 

;; add the elements
(fold + 0 '(1 2 3))             ⇒ 6

;; reverse a list
(fold cons '() '(1 2 3))        ⇒ (3 2 1)

;; append in reverse order
(fold cons '(4 5 6) '(3 2 1))   ⇒ (1 2 3 4 5 6)

;; how many symbols?
(fold (lambda (x count)
        (if (symbol? x)
            (+ count 1)
          count))
      0
      '(a 1 b 2 c 3))           ⇒ 3

Right–folding usage examples for fold* in the single list argument case: 

;; copy the list
(fold* cons '() '(1 2 3))       ⇒ (1 2 3)

;; add elements
(fold* + 0 numbers)             ⇒ 45

;; prepend elements
(fold* cons '(4 5 6) '(1 2 3))  ⇒ (1 2 3 4 5 6)

;; filter the even numbers
(fold* (lambda (x l)
         (if (even? x)
             (cons x l)
           l))
       '()
       '(0 1 2 3 4 5 6 7 8 9))
⇒ (0 2 4 6 8)

Usage examples for fold and fold* in the multiple list argument case: 

(fold (lambda (a b c knil)
        (cons (list a b c) knil))
      '()
      '(1 2 3)
      '(10 20 30)
      '(100 200 300))
⇒ '((3 30 300)
     (2 20 200)
     (1 10 100))

(fold* (lambda (a b c knil)
         (cons (list a b c)
                knil))
       '()
       '(1 2 3)
       '(10 20 30)
       '(100 200 300))
⇒ ((1 10 100)
    (2 20 200)
    (3 30 300))

Next: , Up: lists fold   [Index]