Почему foldl определенно задан в Racket?

Question

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

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

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

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

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

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

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

Answer 1

С Ракетка documentation, описание foldl:

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

Две точки, представляющие интерес для вашего вопроса упоминаются:

входные lsts перемещаются слева направо

И

foldl обрабатывает lsts в постоянном пространстве

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

(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, это только h чтобы гарантировать, что используется постоянное пространство, и что элементы в списке оцениваются слева направо.

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

(- 0 1 2 3 4) 
> -10 

Answer 2

Ракетка-х foldl и foldr (а также SRFI-1'sfold и fold-right) обладают свойством

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

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

Answer 3

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

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

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

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

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

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

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

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

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

• Первый соответствующий язык, который следует за Lisp и имеет правильную складку, является ML. Выбор, который был сделан там, как отмечено в ответе newacct ниже, состоял в том, чтобы пойти с uniform types version (то есть, что использует Racket).

• Следующая ссылка: Bird & Wadler's ItFP (1988), которая использует different types (как в Haskell). Тем не менее, они note in the appendix, что Миранда имеет тот же тип (как в Racket).

• Миранда позже на switched the argument order (т. Е. Перемещен из ордера Racket на Haskell). В частности, этот текст гласит:

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

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

• OCaml пошел с направлением Haskell и использует different types

• Я предполагаю, что «Как создать программы» (он же HTDP) была написана примерно в тот же период, и они выбрали same type. Однако нет мотивации или объяснения - и фактически после этого упражнения он просто упоминается как one of the built-in functions.

  Реализация игры fold operations была, конечно же, «встроенными», упомянутыми здесь.

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

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

  Олин позже addressed this: все, что он сказал, было:

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

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

Answer 4

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

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