fold
и foldBack
- две очень полезные функции, которые работают с несколькими структурами данных в F #. Они могут помешать вам писать рекурсивные функции во многих ситуациях. Однако в первый раз их может быть немного сложно понять. В этой статье объясняется, как они работают, и приводится множество примеров того, что они вам помогают. Мы сосредоточимся на списках, но они очень похоже ведут себя с массивами, наборами и другими линейными структурами.
Эта статья предполагает базовые знания F #, включая работу со списками и массивами.
СОДЕРЖАНИЕ
- складывать;
- foldBack;
- fold2 и foldBack2;
- mapFold, mapFoldBack и приложение для ранжирования запросов.
сложить
List.fold
имеет подпись (’a -> 'b -> 'a) -> 'a -> 'b list -> 'a
. Он принимает функцию acc: 'a -> 'b -> 'c
, которую мы вызываем функцией накопителя, начальное значение типа 'a
и список с элементами типа 'b
. Вот непрограммное индуктивное определение fold
:
В пустом списке: fold f initialValue [] = initialValue
.
В непустом списке: fold f initialValue x::xs = fold f (f initialValue x) xs
.
Это определение на первый взгляд может показаться немного устрашающим, поэтому теперь мы рассмотрим особый случай для списка длиной 3. Я рекомендую вам пройти индуктивное определение, чтобы найти выражение для fold f init [1; 2; 3]
.
Вот что у вас должно получиться:
fold f init [1; 2; 3] = (f (f (f init 1) 2) 3)
.
Убедитесь, что вы понимаете сигнатуру функции и почему каждый параметр должен иметь данный тип.
Мы могли бы реализовать List.fold
следующим образом:
Давайте теперь посмотрим на несколько примеров, чтобы получить некоторое представление о том, что делает эта функция.
Самый простой - это реализация функции sum
, которая принимает список целых чисел и возвращает сумму всех его элементов. Если мы передадим (+)
в качестве функции аккумулятора и 0 в качестве начального значения, мы получим:
fold (+) 0 [1; 2; 3] = ((+) ((+) ((+) 0 1) 2) 3)
.
Вставляем (+) 0 1 = 0 + 1 = 1
, получаем ((+) ((+) (1) 2) 3)
.
Вставляя (+) (1) 2 = 3
, получаем ((+) (3) 3)
, что равно 6.
Еще одна полезная функция, которую мы можем реализовать с помощью fold
, - это rev
, которая принимает список [x1; ...; xn]
и переворачивает его, возвращая [xn; ...; x1]
. Я позволю вам попробовать реализовать это самостоятельно, прежде чем вы продолжите читать.
Мы возьмем пустой список []
в качестве начального значения, функцию аккумулятора f xs x = x::xs
и передадим список, который мы хотим перевернуть (который мы называем li
). Убедитесь, что вы понимаете, почему эти параметры соответствуют сигнатуре List.fold
. Затем fold
вызовет f [] li.Head
, что приведет к [li.Head]
; затем f [li.Head] li.[1]
, что приводит к [li.[1]; li.Head]
, и так далее, пока не будет пройден весь список, добавляя каждый элемент, от первого до последнего, к результату.
Последний полезный пример - функция join
, которая отображает список строк и разделитель на строку. Например, мы хотим иметь join " " ["To"; "be"; "or"; "not"; "to"; "be"] = "To be or not to be"
.
Еще раз рекомендую вам попробовать написать эту функцию самостоятельно, прежде чем читать дальше.
Вот предлагаемое решение:
Ниже приведены шаги, выполняемые вызовом свертки в функции выше.
свернуть назад
foldBack
похож на fold
, но с немного другой подписью: foldBack: (‘a -> ‘b -> ‘b) -> ‘a list -> ‘b -> ‘b
. Вот возможная реализация:
Это не самая эффективная реализация, и реализация из стандартной библиотеки, конечно, намного быстрее. Я дал это, потому что это более естественно и ближе к математическому определению. Мы все еще можем отметить, что и fold
, и foldBack
имеют линейную сложность.
Если мы рассмотрим список из трех элементов, у нас будет List.foldBack f [1; 2; 3] init = f 1 (f 2 (f 3 init))
.
Обратите внимание, что если 'a = 'b
и f
коммутативны (то есть f a b = f b a
для любого a, b
), то fold
и foldBack
выполняют одну и ту же операцию. Ниже приведен пример со списком длиной 3, но это действительно без потери общности.
List.foldBack
можно рассматривать как перевернутую складку. Если мы сделаем что-то подобное тому, что мы сделали с fold
для реализации функции rev
, то есть,
тогда мы получаем копию [1 .. 10]
, не влияя на порядок. Эта идея позволяет нам реализовать несколько функций, работающих со списками.
Мы можем использовать тот же принцип, что и функция copy, описанная выше, чтобы создать функцию, которая принимает список и значение и возвращает список после удаления всех вхождений значения. Для этого мы используем ту же функцию накопителя, что и раньше, за исключением того, что мы добавляем x
только в том случае, если оно отличается от значения, которое мы хотим удалить. Вот как мы можем это реализовать:
Функция deleteAll
является частным случаем функции, которая принимает предикат p
и удаляет все значения x
из списка, так что p(x)
истинно.
Теперь рассмотрим функцию List.unzip
. Требуется список пар, [(x1, y1); …; (xn, yn)] и возвращает пару списков, ([x1;…; xn], [y1;…; yn]).
Мы хотим передать список пар (тип 'c * 'd
) и получить пару списков типа ('c * 'd) list
. Следовательно, если мы сохраним те же обозначения, что и раньше, у нас будут типы 'a = 'c * 'd
и 'b = 'c list * 'd list
. Наша функция аккумулятора должна добавлять оба элемента новой пары к каждому списку результата. Это дает реализацию ниже.
Другой пример функции из List
, которая может быть реализована с помощью foldBack
, - это map
. map
принимает функцию f и список [x1; …; xn] и возвращает [f x1; …; f xn]. Если f имеет тип 'c -> 'd
, тогда у нас есть 'a =’c
и 'b = 'd list
. Имея это в виду, мы можем реализовать map
следующим образом:
fold2 и foldBack2
List.fold2
и list.foldBack2
выполняют те же операции, что и fold
и foldBack
, за исключением того, что они работают с двумя списками.
Подпись List.fold2
- ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a
. Обратите внимание, что два списка не обязательно должны иметь один и тот же тип.
Простым примером применения fold2
является расширение того, что мы видели ранее: сумма двух списков.
Если вы попробуете эту функцию с неассоциативной операцией, она будет выполняться для каждой пары элементов, имеющих одинаковый индекс.
Давайте перейдем к более сложному примеру. Предположим, у вас есть список строк, представляющих имена, и список целых чисел, представляющих возраст. Вы хотите создать единый список, содержащий элементы типа Person
, который представляет собой запись, определенную следующим образом:
Это можно сделать следующим образом:
Обратите внимание, что порядок не сохраняется: первый элемент возвращенного списка - это Джон с возрастом 547 лет, второй - с Мэри с 5 годами, а последний - с Петром с возрастом -12.
Решением этой проблемы является именно foldBack2
. Его подпись ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c
. Подобно тому, что мы сделали с одним списком, мы можем использовать foldBack2
для решения проблемы, которая требует сохранения порядка, в котором элементы появляются в исходных списках. Например, мы могли бы создать список, который отображает два списка [a1; …; an] и [b1; …; bn] в список [c1; …; cn] с ck = min (ak, bk) для всех индексов k:
mapFold и mapFoldBack
Последние функции, которые мы упомянем, вероятно, самые трудные для понимания: mapFold
и mapFoldBack
. mapFold
имеет подпись ('a -> 'b -> 'c * 'a) -> 'a list -> 'b -> 'c list * 'a
. Он применяет функцию накопителя к каждому элементу списка (как это делает map
) и накапливает их так же, как и fold
.
Аккумулятор принимает два параметра: a и b. b принимает в точности значения элементов списка. Первое значение, принимаемое a, является начальным значением, а (i +1) -ое значение, которое оно принимает, является вторым значением, возвращаемым i -й вызов аккумулятора. Первое значение, возвращаемое каждым вызовом аккумулятора, добавляется к окончательному списку L. mapFold
затем возвращает пару (L, o), где o - второй результат последнего вызова аккумулятора.
Парбле!
Давайте взглянем на простую программу, которая не дает ничего действительно интересного, но, надеюсь, поможет лучше понять, что делает mapFold
:
Вот что произошло:
Столбцы o1 и o2 - это первое и второе значения, возвращаемые аккумулятором при каждом его вызове. Выходные данные функции состоят из списка всех значений в столбце o1 и последнего элемента в столбце o2.
Имея это в виду, мы можем предложить следующую наивную реализацию. Цель здесь не в том, чтобы подробно останавливаться на том, как написать эффективную версию, а в том, чтобы понять, как это действительно работает. Если вам интересно, вы можете найти там официальную реализацию: https://github.com/dotnet/fsharp//tree/master/src/fsharp/FSharp.Core/list.fs#L84-84
List.mapFoldBack
работает точно так же. Его подпись ('a -> 'b -> 'c * 'b) -> 'a list -> 'b -> 'c list * 'b
.
Попробуйте угадать, каков будет результат следующего фрагмента кода.
Готовый?
В следующей таблице показано изменение аргументов и возвращаемого значения функции аккумулятора:
Окончательный результат ([-1; 6; 2; 9, 5], 3)
. Общая структура такая же, как и в mapFold
, за исключением двух основных отличий. Список оценивается в обратном порядке, то есть первое значение первого параметра функции аккумулятора является последним значением списка; и каждый раз, когда вызывается функция аккумулятора, первое значение ее вывода добавляется к окончательному списку, а не добавляется. Это позволяет выполнить простую повторную реализацию функции map
. Это делается простым игнорированием второго параметра функции аккумулятора:
Разница в том, что, в отличие от функции map
, значения нового списка теперь могут зависеть от других элементов списка. Полезное приложение - это функция, которая вычисляет сумму элемента списка и всех предшествующих элементов, а также сумму списка. На этот раз мы будем использовать массивы вместо списков (почему я объясню позже):
Например, partialSums [|1 .. 5|]
это ([|1; 3; 6; 10; 15|], 15)
. Это известно как массив сумм префиксов. Та же функция, реализованная с mapFoldBack
вместо mapFold
, даст массив суффикс-суммы [|1 .. 5|]
, а именно ([|15; 14; 12; 9; 5|], 15)
.
Приложения для ранжирования запросов
Это может быть полезно для выполнения запросов диапазона, то есть выполнения некоторой операции с подмножеством исходного ввода. Это включает в себя нахождение общей суммы подмассива.
Реализованная выше функция partialSum
требует линейного времени по отношению к длине списка li
. Конечно, вычисление суммы подмассивов было бы не менее эффективным, но если бы мы повторили операцию несколько раз, то использование массива префикс-сумма сделало бы вещи намного быстрее. Учитывая массив частичных сумм, мы можем вычислить любую сумму между двумя индексами за постоянное время:
Результатом приведенного выше кода является [15; 11; 5]
.
Это выполняется за линейное время в зависимости от количества запросов и количества элементов в списке (вычисление частичных сумм и оценка q запросов имеют сложность Θ (n + q), где n - длина списка). Это время работы может быть достигнуто, потому что мы сохранили суммы префиксов в массиве, который имеет постоянную индексацию.
Точно так же мы можем использовать Array.mapFold
для построения разностного массива массива [x1; …; xn], который представляет собой массив [d1; …; dn] так, что d1 = x1 и dk = xk - x {k -1} для всех индексов k ≥ 2 (при условии индексирования на основе 1). Это помогает добавить некоторую константу ко всем значениям в пределах диапазона за постоянное время и получить доступ к значению по индексу i в Θ (i) времени.
Массив разностей может быть вычислен за линейное время с использованием mapFold
следующим образом:
Теперь мы можем добавить n ко всем значениям между индексами i и j включительно, применив следующую функцию:
Затем мы можем получить значение по индексу i в исходном массиве, суммируя все значения до индекса i в массиве разностей.
Вывод
Теперь вы должны хорошо понимать функции семейства fold. Я рекомендую запомнить их подпись, так как это помогает запомнить роль каждого параметра и их эволюцию.
Поддержите меня!
Спасибо за чтение! Если вы нашли эту статью полезной, подумайте о том, чтобы подписаться на меня, чтобы помочь мне достичь порога в 100 подписчиков, необходимого для участия в программе Medium Partner Program. Это бесплатно и действительно помогает.
Вы также можете использовать мою реферальную ссылку для подписки на Medium: Стать участником. Вы получите доступ ко всем статьям на Medium, предназначенным только для участников, и ваш членский взнос будет напрямую поддерживать меня.
🐉
использованная литература
Документация F #: https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections-listmodule.html#fold2.
Функциональное программирование с использованием F # Ханса Ришеля и Майкла Р. Хансена.
Справочник конкурентоспособного программиста, автор - Аннти Лааксонен.