Understanding fold and reduce functions in scheme

Question

I have generic question about scheme and lisp. How fold and reduce functions should work?

In guile scheme using (use-modules (srfi srfi-1)) you can use this:

guile> (fold cons '() '(1 2 3 4))
> (4 3 2 1)
guile> (fold cons '(1 2 3 4) '())
> (1 2 3 4)

I'm working on fold function in my lisp in JavaScript, I want to create single function for both reduce and fold (the function will return one of those functions).

But how they should work? In my code I'm checking if first list is not null or if it did not ended but here you pass empty list (first code). Does fold work on second list instead and check if that not ended or on both since reverse also works? How many times fold got executed when called with '() as init value, ones or it process whole first argument?

Here is my reduce function:

function reduce(fn, list, init = nil) {
    if (isEmptyList(list) || isNull(list)) {
        return list;
    }
    let result = init;
    let node = list;
    if (init === null) {
        result = list.car;
        node = list.cdr;
    }
    return (function loop() {
        function next(value) {
            result = value;
            node = node.cdr;
            return loop();
        }
        if (node === nil || !(node instanceof Pair)) {
            if (typeof result === 'number') {
                return LNumber(result);
            }
            return result;
        }
        const item = node.car;
        const value = fn(result, item);
        if (isPromise(value)) {
            return value.then(next);
        } else {
            return next(value);
        }
    })();
}

does below results are correct for reduce?

lips> (reduce cons '(1 2 3 4) nil)
((((nil . 1) . 2) . 3) . 4)
lips> (reduce list '(1 2 3 4) nil)
((((nil 1) 2) 3) 4)
lips>

How should fold function work and look like in JavaScript? What is exact logic for fold and reduce in scheme?

Here is another example for guile:

guile> (fold-right append '(1 2 3 4) '())
(1 2 3 4)
lips> (reduce append '(1 2 3 4) '())
(1 2 3 4)

it works the same in my lisp, does it mean that my reduce is correct? How to test if my function works right?

I have one issue this, in Guile:

guile> (fold-right list '(1 2 3 4) '())
> (1 2 3 4)
guile> (fold list '(1 2 3 4) '())
> (1 2 3 4)

but in my lisp:

lips> (reduce list '(1 2 3 4) '())
((((() 1) 2) 3) 4)

is fold-right in fact reduce? Because this code in guile give the same result in as my reduce:

guile> (list (list (list (list '() 1) 2) 3) 4)
> ((((() 1) 2) 3) 4)

Mulan Mulan · Accepted Answer · 2019-04-21T13:04:15

https://www.gnu.org/software/guile/manual/html_node/SRFI_002d1-Fold-and-Map.html

Scheme Procedure: fold proc init lst1 lst2 …
Scheme Procedure: fold-right proc init lst1 lst2 …

Apply proc to the elements of lst1 lst2 … to build a result, and return that result.

Each proc call is (proc elem1 elem2 … previous), where elem1 is from lst1, elem2 is from lst2, and so on. previous is the return from the previous call to proc, or the given init for the first call. If any list is empty, just init is returned.

fold works through the list elements from first to last. The following shows a list reversal and the calls it makes,

(fold cons '() '(1 2 3))

(cons 1 '())
(cons 2 '(1))
(cons 3 '(2 1)
⇒ (3 2 1)

fold-right works through the list elements from last to first, ie. from the right. So for example the following finds the longest string, and the last among equal longest,

(fold-right (lambda (str prev)
              (if (> (string-length str) (string-length prev))
                  str
                  prev))
            ""
            '("x" "abc" "xyz" "jk"))
⇒ "xyz"

The scheme folds support multiple lists, but I'll show you how to adjust your JavaScript implementation so it works with one list -

function reduce (fn, init, list) {
  if (isNull(list))
    return init
  else
    return reduce(fn, fn(list.car, init), list.cdr)
}

function reduceRight (fn, init, list) {
  if (isNull(list))
    return init
  else
    return fn(list.car, reduceRight(fn, init, list.cdr))
}

Supporting multiple lists is easy enough thanks to JavaScript's support for rest parameters and spread arguments -

function some (fn, list) {
  if (isNull(list))
    return false
  else
    return fn(list.car) || some(fn, list.cdr)
}

function reduce (fn, init, ...lists) {
  if (some(isEmpty, lists))
    return init
  else
    return reduce
             ( fn
             , fn (...lists.map(l => l.car), init)
             , lists.map(l => l.cdr)
             )
}

function reduceRight (fn, init, ...lists) {
  if (some(isEmpty, lists))
    return init
  else
    // exercise left for reader
    // ...
}

Understanding fold and reduce functions in scheme

1 Answers