Блог

У меня общий вопрос о scheme и lisp. Как fold и reduce функции должны работать?

При использовании схемы guile (use-modules (srfi srfi-1)) вы можете использовать это:

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

Я работаю над функцией fold в моем lisp на JavaScript, я хочу создать единую функцию как для reduce, так и для fold (функция вернет одну из этих функций).

Но как они должны работать? В моем коде я проверяю, не равен ли первый список нулю или он не закончился, но здесь вы передаете пустой список (первый код). Работает ли fold вместо этого во втором списке и проверяет, не закончилось ли это, или на обоих, поскольку reverse также работает? Сколько раз fold выполнялся при вызове с ‘() в качестве значения инициализации, единицы или он обрабатывает весь первый аргумент?

Вот моя функция уменьшения:

 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 resu<
        }
        const item = node.car;
        const value = fn(result, item);
        if (isPromise(value)) {
            return value.then(next);
        } else {
            return next(value);
        }
    })();
}
  

верны ли приведенные ниже результаты для 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>
  

Как функция fold должна работать и выглядеть в JavaScript? Какова точная логика для fold и reduce в схеме?

Вот еще один пример для хитрости:

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

это работает так же в моем lisp, означает ли это, что мое сокращение правильное? Как проверить, правильно ли работает моя функция?

У меня есть одна проблема, связанная с лукавством:

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

но в моем lisp:

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

является ли fold-right на самом деле reduce? Потому что этот код в guile дает тот же результат, что и мой reduce:

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

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

процедура свертки процесса инициализации lst1 lst2 Scheme: …
процедура схемы lst1 lst2 с откидной правой обработкой: …

Примените proc к элементам lst1 lst2, чтобы создать результат, и верните этот результат.

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

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

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

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

 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
    // ...
}