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

В 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 (xy) (bin-fn yx))) 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

foldl и foldl ракетка (а также fold и foldl SRFI-1 ) обладают тем свойством, что

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

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

Из документации Racket описание 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 , что документация для foldl не делает никаких предположений относительно порядка оценки аргументов для proc , но только для того, чтобы гарантировать, что используется постоянное пространство, и что элементы в списке оцениваются слева направо.

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

 (- 0 1 2 3 4) > -10 
  • В чем разница между цитатой и списком?
  • Сгладить список, используя только формы в «The Little Schemer»
  • Как создать весь DDL схемы Oracle (сценарий)?
  • Почему именно это зло?
  • Как отменить конкретную миграцию?
  • В чем разница между eq ?, eqv ?, equal ?, и = в схеме?
  • Какой пакет lang подходит для SICP в Dr.Racket?
  • Spring v3 нет объявления для элемента 'mvc: resources'
  • где можно найти xsd.exe в visual studio 2013 на windowsх 8
  • Как хранить массивы в MySQL?
  • Как показать схему таблицы в базе данных MySQL?
  • Давайте будем гением компьютера.