Почему в Racket странным образом определяется foldl?

Question

В Haskell, как и во многих других функциональных языках, функция foldl определена так, что, например, foldl (-) 0 [1,2,3,4] = -10.

Это нормально, потому что foldl (-) 0 [1, 2,3,4] по определению ((((0 - 1) - 2) - 3) - 4).

Но в Racket (foldl - 0 '(1 2 3 4)) равно 2, потому что Racket "разумно" вычисляет так: (4 - (3 - (2 - (1 - 0)))), что в действительности равно 2.

Конечно, если мы определим вспомогательную функцию flip, как это:

(define (flip bin-fn)
  (lambda (x y)
    (bin-fn y x)))

тогда мы можем в Racket добиться того же поведения, что и в Haskell: вместо (foldl - 0 '(1 2 3 4)) мы можем написать: (foldl (flip -) 0 '(1 2 3 4))

Вопрос в том, почему foldl в ракетке определяется таким странным (нестандартным и не интуитивным) способом, отличным от любого другого языка?

Answer 1

• Определение Haskell не однородно . В Racket функции для обоих сгибов имеют один и тот же порядок ввода, и поэтому вы можете просто заменить foldl на foldr и получить тот же результат. Если вы сделаете это с версией на Haskell, вы получите другой результат (обычно) - и вы можете увидеть это в разных типах.

  (На самом деле, я думаю, что для правильного сравнения следует избегать этих игрушечных числовых примеров, где обе переменные типа являются целыми числами.)

• Это хороший побочный продукт, в котором вам предлагается выбрать foldl или foldr в соответствии с их семантическими различиями. Я предполагаю, что с заказом Haskell вы, вероятно, выберете в соответствии с операцией. У вас есть хороший пример для этого: вы использовали foldl, потому что вы хотите вычесть каждое число - и это такой «очевидный» выбор, что легко упустить из виду тот факт, что foldl обычно плохой выбор для ленивых язык.

• Другое отличие состоит в том, что версия на Haskell более ограничена, чем версия Racket обычным способом: она работает только с одним входным списком, тогда как Racket может принимать любое количество списков. Это делает более важным иметь единый порядок аргументов для функции ввода).

• Наконец, неправильно предполагать, что Racket отличается от «многих других функциональных языков», поскольку сворачивание далеко от нового трюка, и у Racket есть корни, которые намного старше, чем Haskell (или эти другие языки). Поэтому вопрос может пойти другим путем : почему foldl Хаскеля определен странным образом? (И нет, (-) не является хорошим оправданием.)

Историческое обновление:

Поскольку это, кажется, беспокоит людей снова и снова, я немного поработал. Это ни в коем случае не является окончательным, просто мое предположение из вторых рук. Не стесняйтесь редактировать это, если вы знаете больше, или даже лучше, напишите соответствующим людям и спросите. В частности, я не знаю даты, когда были приняты эти решения, поэтому следующий список в грубом порядке.

• Сначала был Лисп, и никаких упоминаний о "сворачивании" какого-либо рода. Вместо этого Lisp имеет reduce, который очень неоднороден, особенно если учесть его тип. Например, :from-end - это аргумент ключевого слова, который определяет, является ли это сканирование влево или вправо и он использует различные функции аккумулятора, что означает, что тип аккумулятора зависит от этого ключевого слова. Это в дополнение к другим хаки: обычно первое значение берется из списка (если вы не указали :initial-value). Наконец, если вы не укажете :initial-value, а список будет пуст, он фактически применит функцию к нулевым аргументам, чтобы получить результат.

  Все это означает, что reduce обычно используется для того, что предполагает его название: сокращение списка значений в одно значение, где два типа обычно одинаковы. Вывод здесь заключается в том, что он выполняет своего рода функцию, аналогичную свертыванию, но он не так полезен, как универсальная конструкция итерации списка, которую вы получаете при сворачивании. Я предполагаю, что это означает, что нет никакой сильной связи между reduce и более поздними операциями сгиба.

• Первый соответствующий язык, который следует за Лиспом и имеет правильную складку, - это ML. Выбор, который был сделан там, как отмечено в ответе newacct ниже, состоял в том, чтобы выбрать версию с унифицированными типами (то есть то, что использует Racket).

• Следующей ссылкой является ItFP Bird & Wadler (1988), в котором используются различные типы (как в Haskell). Однако они отмечают в приложении , что Миранда имеет тот же тип (что и в Ракетке).

• Миранда позже изменила порядок аргументов (то есть переместилась из ордена Ракетки в Хаскелл). В частности, этот текст гласит:

  ПРЕДУПРЕЖДЕНИЕ - это определение foldl отличается от определения в более старых версиях Miranda. Та, что здесь, такая же, как в Bird and Wadler (1988). В старом определении два аргумента `op 'поменялись местами.

• Хаскелл взял много вещей у Миранды, включая разные типы. (Но, конечно, я не знаю дат, поэтому, возможно, изменение в Миранде произошло из-за Хаскелла.) В любом случае, на данный момент ясно, что консенсуса не было, поэтому обратный вопрос, приведенный выше, остается в силе.

• OCaml пошел в направлении Haskell и использует различных типов

• Я предполагаю, что "Как разрабатывать программы" (он же HtDP) был написан примерно в тот же период, и они выбрали того же типа . Однако нет мотивации или объяснения - и на самом деле после этого упражнения он просто упоминается как одна из встроенных функций .

  Реализация операций складывания в Racket - это, конечно, «встроенные модули», которые здесь упоминаются.

• Затем пришло SRFI-1 , и выбор был в том, чтобы использовать версию того же типа (как Racket). Это решение было вопросом Джона Дэвида Стоуна, который указывает на комментарий в SRFI, в котором говорится

  Примечание: Схема MIT и Haskell переворачивают порядок аргументов F для их функций reduce и fold.

  Олин позже обратился к этому : все, что он сказал, было:

  Хороший вопрос, но я хочу согласованности между двумя функциями. сначала значение состояния: srfi-1, SML последнее значение состояния: Haskell

  Обратите внимание, в частности, на его использование значение-состояния , которое предлагает представление, в котором согласованные типы являются, возможно, более важной точкой, чем порядок операторов.

Answer 2

«иначе, чем на любом другом языке»

В качестве контрпримера, стандартный ML (ML - очень старый и влиятельный функциональный язык) foldl также работает следующим образом: http://www.standardml.org/Basis/list.html#SIG:LIST.foldl:VAL

Answer 3

Ракетки foldl и foldr (а также SRFI-1 fold и fold-right) имеют свойство, которое

(foldr cons null lst) = lst
(foldl cons null lst) = (reverse lst)

Я предполагаю, что порядок аргументов былвыбран по этой причине.

Answer 4

Из Ракетки Документация , описание foldl:

(foldl proc init lst ...+) → any/c

Упомянуты два вопроса на ваш вопрос:

входные значения пройдены слева направо

И

сложить обрабатывает последние в постоянном пространстве

Я собираюсь поразмышлять над тем, как может выглядеть реализация для этого, с одним списком для простоты:

(define (my-foldl proc init lst)
  (define (iter lst acc)
    (if (null? lst)
        acc
        (iter (cdr lst) (proc (car lst) acc))))
  (iter lst init))

Как видите, требования обхода и константы слева направо выполнены (обратите внимание на хвостовую рекурсию в iter), но порядок аргументов для proc был никогда не указывается в описании. Следовательно, результатом вызова вышеуказанного кода будет:

(my-foldl - 0 '(1 2 3 4))
> 2

Если бы мы указали порядок аргументов для proc следующим образом:

(proc acc (car lst))

Тогда результат будет:

(my-foldl - 0 '(1 2 3 4))
> -10

Моя точка зрения такова, что документация для foldl не делает никаких предположений относительно порядка вычисления аргументов для proc, она должна только гарантировать, что используется постоянное пространство и что элементы в списке оцениваются слева направо.

В качестве примечания вы можете получить желаемый порядок оценки для вашего выражения, просто написав это:

(- 0 1 2 3 4)
> -10