Допустим, мы хотим добавить список чисел вместе:
1 + 2 + 3 + 4.
Это вполне нормальный способ написания. Но я написал "добавить список чисел вместе", а не "записать числа плюсами между ними". Между тем, как я выразил операцию в прозе, и используемой мною математической записью есть нечто принципиально иное. Мы делаем это, потому что знаем, что это эквивалентная запись для сложения (поскольку она коммутативна), и в наших головах она немедленно сводится к:
3 + 7.
а потом
10.
Так в чем же дело? Проблема в том, что мы не можем понять идею суммирования из этого примера. Что, если бы вместо этого я написал: «Начните с 0, затем берите по одному элементу из списка и добавляйте его к начальному значению в виде текущей суммы»? На самом деле это то, что касается суммирования, а не произвольного решения, какие две вещи добавить первыми, пока уравнение не уменьшится.
sum(List) -> sum(List, 0).
sum([], A) -> A;
sum([H|T], A) -> sum(T, H + A).
Если вы со мной до сих пор, то вы готовы понять фолды.
Возникла проблема с указанной выше функцией; это слишком конкретно. Он объединяет три идеи вместе, не определяя ни одну из них по отдельности:
- итерация
- накопление
- добавление
Легко упустить разницу между итерацией и накоплением, потому что большую часть времени мы никогда не задумываемся об этом. Большинство языков случайно подталкивают нас к тому, чтобы упустить разницу, поскольку одно и то же место хранения меняет свое значение при каждой итерации аналогичной функции.
Легко упустить независимость сложения только из-за того, как оно написано в этом примере, потому что «+» выглядит как «операция», а не как функция.
Что, если бы я сказал: «Начните с 1, затем берите по одному элементу из списка и умножайте его на текущее значение»? Мы по-прежнему будем обрабатывать список точно так же, но с двумя примерами для сравнения становится ясно, что умножение и сложение — единственная разница между ними:
prod(List) -> prod(List, 1).
prod([], A) -> A;
prod([H|T], A) -> prod(T, H * A).
Это точно такой же поток выполнения, но для внутренней операции и начального значения аккумулятора.
Итак, давайте превратим биты сложения и умножения в функции, чтобы мы могли извлечь эту часть шаблона:
add(A, B) -> A + B.
mult(A, B) -> A * B.
Как мы могли бы написать операцию списка самостоятельно? Нам нужно передать функцию — сложение или умножение — и заставить ее работать со значениями. Кроме того, мы должны обращать внимание на идентификацию типа и операции вещей, над которыми мы работаем, иначе мы испортим магию. это агрегация значений. "add(0, X)" всегда возвращает X, поэтому эта идея (0 + Foo) является операцией добавления идентификатора. При умножении тождественная операция заключается в умножении на 1. Поэтому мы должны начинать наш аккумулятор с 0 для сложения и 1 для умножения (и для построения списков, пустой список и т. д.). Таким образом, мы не можем написать функцию со встроенным значением аккумулятора, потому что она будет правильной только для некоторых пар тип+операция.
Таким образом, это означает, что для написания сгиба нам нужен аргумент-список, аргумент-функция для выполнения действий и аргумент-аккумулятор, например:
fold([], _, Accumulator) ->
Accumulator;
fold([H|T], Operation, Accumulator) ->
fold(T, Operation, Operation(H, Accumulator)).
С этим определением теперь мы можем написать sum/1, используя этот более общий шаблон:
fsum(List) -> fold(List, fun add/2, 0).
И prod/1 также:
fprod(List) -> fold(List, fun prod/2, 1).
И функционально они идентичны тому, что мы написали выше, но обозначения более понятны и нам не нужно писать кучу рекурсивных деталей, которые путают идею итерации с идеей накопления с идея некоторой конкретной операции, такой как умножение или сложение.
В случае калькулятора RPN идея операций со сводным списком сочетается с концепцией выборочной отправки (выбор операции для выполнения на основе того, какой символ встречается/сопоставляется). Пример RPN относительно прост и мал (в голове сразу может уместиться весь код, это всего несколько строк), но пока вы не привыкнете к функциональным парадигмам, процесс, который он проявляет, может вызвать у вас головную боль. В функциональном программировании небольшое количество кода может создать сколь угодно сложный процесс с непредсказуемым (или даже развивающимся!) поведением, основанный только на операциях со списками и выборочной диспетчеризации; это очень отличается от методов условной проверки, проверки ввода и процедурной проверки, используемых в других парадигмах, более распространенных сегодня. Анализу такого поведения значительно помогает одиночное присваивание и рекурсивная запись, поскольку каждая итерация представляет собой концептуально независимый отрезок времени, который можно рассматривать отдельно от остальной системы. Я говорю немного раньше основного вопроса, но это основная идея, которую вы, возможно, захотите обдумать, когда будете думать, почему нам нравится использовать такие операции, как свертки и рекурсивные обозначения, вместо процедурных, множественных. петли назначения.
Надеюсь, это больше помогло, чем запутало.
person
zxq9
schedule
10.11.2014
