Понимание сложения и уменьшения функций в схеме - PullRequest
Новая
       55

Понимание сложения и уменьшения функций в схеме

0 голосов
/ 21 апреля 2019

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

В схеме с использованием (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)

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

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

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

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

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

Как должна работать функция сгиба и выглядеть в 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: 

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

но в моем лиспе: 

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

действительно ли уменьшить в разы? Потому что этот код в guile дает тот же результат, что и мой Reduce: 

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

1 Ответ

2 голосов
/ 21 апреля 2019

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

Процедура схемы: fold proc init lst1 lst2 …
Процедура схемы: fold-right proc init lst1 lst2 …

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

Каждый proc вызов (proc elem1 elem2 … previous) ,где elem1 от lst1 , elem2 от lst2 и так далее.previous - это возврат предыдущего вызова к proc или заданный init для первого вызова. Если какой-либо список пуст, возвращается только init .

fold обрабатывает элементы списка от первого до последнего.Далее показано обращение списка и выполняемые им вызовы: 

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

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

fold-right работает через элементы списка от последнего к первому, т.е.справаТак, например, следующий код находит самую длинную строку и последнюю среди равных самых длинных, 

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

Схемы свертывания поддерживают несколько списков, но я покажу вам, как настроить реализацию JavaScript так, чтобы онаработает с одним списком - 

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

Поддержка нескольких списков достаточно проста благодаря поддержке JavaScript для параметров отдыха и аргументов распространения - 

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