fold и foldBack - две очень полезные функции, которые работают с несколькими структурами данных в F #. Они могут помешать вам писать рекурсивные функции во многих ситуациях. Однако в первый раз их может быть немного сложно понять. В этой статье объясняется, как они работают, и приводится множество примеров того, что они вам помогают. Мы сосредоточимся на списках, но они очень похоже ведут себя с массивами, наборами и другими линейными структурами.

Эта статья предполагает базовые знания F #, включая работу со списками и массивами.

СОДЕРЖАНИЕ

  1. складывать;
  2. foldBack;
  3. fold2 и foldBack2;
  4. 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 # Ханса Ришеля и Майкла Р. Хансена.

Справочник конкурентоспособного программиста, автор - Аннти Лааксонен.