Какой формальный термин для «складываемой» функции? - PullRequest
Новая
       26

Какой формальный термин для «складываемой» функции?

4 голосов
/ 11 ноября 2011

Я использую оператор LINQ Aggregate довольно часто. По сути, он позволяет «накапливать» функцию над последовательностью, многократно применяя функцию к последнему вычисленному значению функции и следующему элементу последовательности.

Например: 

int[] numbers = ...
int result = numbers.Aggregate(0, (result, next) => result + next * next);

вычислит сумму квадратов элементов массива.

После некоторого поиска в Google я обнаружил, что общий термин для этого в функциональном программировании: "fold" .

Теперь я думаю, что функция, которую можно вычислить с помощью этого оператора, должна только удовлетворять (пожалуйста, исправьте меня, если я ошибаюсь): 

f(x1, x2, ..., xn) = f(f(x1, x2, ..., xn-1), xn)

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

Ответы [ 3 ]

3 голосов
/ 12 ноября 2011

В функциональном программировании fold используется для агрегирования результатов по наборам, таким как список, массив, последовательность ... Ваша формулировка fold неверна, что приводит к путанице.Правильная формулировка может быть: 

fold f e [x1, x2, x3,..., xn] = f((...f(f(f(e, x1),x2),x3)...), xn)

Требование для f на самом деле очень слабое.Допустим, тип элементов - T, а тип e - U.Таким образом, функция f действительно принимает два аргумента: первый тип U, а второй тип T и возвращает значение типа U (поскольку это значение будет предоставлено в качестве первого аргумента функцииf снова).Короче говоря, у нас есть функция «накапливать» с подписью f: U * T -> U. По этой причине я не думаю, что существует формальный термин для такого рода функций.

В вашем примере e = 0, T = int, U = int и вашЛямбда-функция (result, next) => result + next * next имеет сигнатуру f: int * int -> int, которая удовлетворяет условию «складных» функций.

Если вы хотите знать, другой вариант fold - это foldBack, который накапливает результаты собратный порядок от xn до x1: 

   foldBack f [x1, x2,..., xn] e = f(x1,f(x2,...,f(n,e)...))

Существуют интересные случаи с коммутативными функциями, которые удовлетворяют f (x, y) = f (x, y), когда fold иfoldBack вернуть тот же результат.О самом fold, это конкретный случай катаморфизма в теории категорий.Вы можете прочитать больше о катаморфизме здесь .

3 голосов
/ 11 ноября 2011

Итеративная двоичная операция может быть тем, что вы ищете.

Вам также необходимо добавить некоторые условия остановки, такие как 

f(x) = something
f(x1,x2) = something2

Они определяют двоичный файлоперация f и другая функция F в предоставленной мною ссылке для обработки того, что происходит, когда вы переходите на f(x1,x2).

2 голосов
/ 12 ноября 2011

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

sumSq = fold ((result, next) => result + next * next) 0

Какие функции f имеют это свойство, где dom f = { A tuples }, ran f :: B?

Очевидно, что из-за механики сгиба утверждение о том, что f складывается, является утверждением, что существует h :: A * B -> B такое, что для любого n> 0, x1, ..., xn в A, f ((x1,...xn)) = h (xn, f ((x1,...,xn-1))).

Утверждение, что h существует, говорит почти то же самое, что и ваше состояние, что 

f((x1, x2, ..., xn)) = f((f((x1, x2, ..., xn-1)), xn))     (*)

так что вы были почти правы; разница в том, что вам требуется A=B, что немного более ограничительно, чем обычная функция, выражаемая сгибом. Что еще более проблематично, сгиб обычно также принимает начальное значение a, которое установлено на a = f nil. Основная причина, по которой ваша формулировка (*) неверна, состоит в том, что она предполагает, что h - это то, что f делает в списках пар, но это верно только тогда, когда h(x, a) = a. То есть в вашем примере суммы квадратов начальное значение, которое вы задали для Accumulate, было 0, что при добавлении ничего не дает, но есть функции с выражением в виде сгиба, где начальное значение что-то делает, и в этом случае мы иметь выражаемую в сгибе функцию, которая не удовлетворяет (*).

Например, возьмите эту выражаемую фолдом функцию lengthPlusOne: 

lengthPlusOne = fold  ((result, next) => result + 1) 1

f (1) = 2, но f(f(), 1) = f(1, 1) = 3.

Наконец, давайте приведем пример функций в списках, не выражаемых в терминах свертывания. Предположим, у нас была функция черного ящика и мы проверили ее на следующих входах: 

f (1) = 1
f (1, 1) = 1    (1)
f (2, 1) = 1
f (1, 2, 1) = 2 (2)

Такая функция для кортежей (= конечных списков), очевидно, существует (мы можем просто определить ее так, чтобы эти выходы были выше и были равны нулю в любых других списках). Тем не менее, это не складывается, потому что (1) подразумевает h(1,1)=1, в то время как (2) подразумевает h(1,1)=2.

Я не знаю, есть ли другая терминология, кроме просто сказать «функция, выражаемая как складка». Возможно, (слева / справа) функция списка без контекста будет хорошим способом ее описания?

...