Пределы выразительности свёрток

Виталий Брагилевский

Аннотация: Свёртки — удобное средство обработки списков и других структур данных. Они позволяют записывать многие функции без явной рекурсии, а также упрощают формальное доказательство их корректности. В настоящей статье рассматривается вопрос о пределах того, что вообще можно записать (вычислить) с помощью свёрток. В частности, показывается, что свёртки могут вести себя как комбинаторы неподвижной точки при моделировании рекурсивных вызовов. С помощью свёрток также реализуется оператор примитивной рекурсии на списках, что позволяет выразить в соответствующих терминах любые примитивно рекурсивные функции.


Folding is a convenient tool for processing lists and other data structures. Folds allow to avoid explicit use of recursion when defining functions and simplify formal correctness proofs. This article discusses the expressive power of folds. It is shown that a fold can be used as a fixed-point combinator to simulate recursion and to express the primitive recursion operator on lists, thus being capable of implementing arbitrary primitive recursive functions.



Обсуждение статьи ведется по адресу
http://community.livejournal.com/fprog/8096.html.

1  Введение

В центре современной информатики (computer science) находится теория алгоритмов, в рамках которой изучаются формальные вычислительные модели. Пожалуй, самыми известными моделями являются машина Тьюринга и λ-исчисление Чёрча. Именно они служат теоретическим основанием для императивного и функционального программирования.

Помимо λ-исчисления и машины Тьюринга в XX веке было сформулировано множество других формализаций понятия алгоритма: машины Поста и Минского, нормальные алгорифмы Маркова, теория рекурсивных функций. Все эти формализации являются эквивалентными в следующем смысле: всё, что можно вычислить в рамках одной формализации, можно вычислить и в другой.

В этой статье демонстрируется связь между таким важным инструментом функционального программирования как свёртки и некоторыми разделами теории алгоритмов. В частности, во втором разделе рассматривается несколько искусственная, но от того не менее интересная задача выражения функции dropWhile из стандартной библиотеки языка Haskell в терминах свёрток. Здесь показаны полезные на практике приёмы передачи контекстной информации в процессе свёртки списка и использования там же функций высшего порядка. Третий раздел посвящён связи между свёртками и комбинаторами неподвижной точки, используемыми в λ-исчислении для реализации рекурсивных вызовов. Там показывается, что свёртку можно использовать вместо таких комбинаторов, моделируя с её помощью рекурсию. Наконец, в четвёртом разделе рассматривается построение достаточно широкого класса примитивно рекурсивных функций, который в свою очередь является подклассом класса частично рекурсивных функций, исчерпывающего все вычислимые функции. Это достигается выражением оператора примитивной рекурсии в терминах свёрток.

Необходимо заметить, что данная статья носит теоретический характер, её полезность для практического программирования невелика. В основе статьи лежат две работы: статьи Берни Поупа [5] и Грэма Хаттона [3].

Для чтения статьи необходимо понимать определение и порядок работы функций foldl и foldr ([9], п. 5.11), а также уметь читать код на языке Haskell, включая определение функций, сопоставление с образцом ([9], п. 5.10), функции высшего порядка ([9], п. 5.3), каррирование ([9], п. 5.5) и бесточечный стиль ([9], п. 5.6). Словом, лучше предварительно прочитать статью Евгения Кирпичёва «Элементы функционального программирования» [9]. Кроме того, мы будем активно использовать различные термины из λ-исчисления, в том числе понятие комбинатора неподвижной точки. Лучший способ познакомиться с ними — прочитать вторую и третью главы курса Джона Харрисона «Введение в функциональное программирование» [8], переведённого на русский язык силами энтузиастов.

2  Неуловимый dropWhile

Функция dropWhile из модуля Prelude стандартной библиотеки языка Haskell предназначена для удаления самого длинного префикса (начальной части) заданного списка, состоящего из элементов, удовлетворяющих некоторому предикату. В качестве аргументов она принимает предикат и исходный список, а возвращает новый список. Приведём её определение и примеры использования:

dropWhile :: (a -> Bool) -> [a] -> [a] dropWhile predicate [] = [] dropWhile predicate list@(x:xs) | predicate x = dropWhile predicate xs | otherwise = list > dropWhile (<5) [1..10] [5,6,7,8,9,10] > dropWhile (>0) [1,2,-3,2,1] [-3,2,1] > dropWhile even [2,4,1,2,3] [1,2,3] > dropWhile (==1) [2,2,1,1] [2,2,1,1] > dropWhile (/=0) [1..5] [] > take 3 (dropWhile (<5) [1..]) [5,6,7]

Из определения видно, что рекурсия завершается при обнаружении первого элемента, не удовлетворяющего предикату, при этом возвращается весь остаток списка. Если ни один из элементов списка не удовлетворяет предикату, то возвращается пустой список. Последний пример демонстрирует ленивость функции dropWhile, благодаря которой её можно применять к бесконечным спискам. Поскольку из всего списка (dropWhile (<5) [1..]) для вывода результата требуются только три первых элемента (take 3), все остальные не вычисляются.

Ричард Бёрд (Richard Bird) в своей классической книге «Introduction to Functional Programming using Haskell» поставил вопрос о том, можно ли реализовать стандартную функцию dropWhile, пользуясь свёртками ([1], с. 126, упр. 4.5.2). Эта задача оказалась неожиданно сложной, причём было получено множество совершенно разных решений с отличающимися свойствами. Демонстрируя некоторые из этих решений, мы будем следовать преимущественно, но не исключительно, работе Берни Поупа [5].

2.1  Готовим сцену

Напомним, что различают правую и левую свёртки. Левая свёртка определяется следующим образом:

foldl :: (a -> b -> a) -> a -> [b] -> a foldl combine base [] = base foldl combine base (x:xs) = foldl combine (combine base x) xs

При обработке списка [x1,x2,...,xn] левая свёртка трансформируется в последовательность вызовов:

combine (...(combine (combine base x1) x2)...) xn

Правая свёртка определяется так:

foldr :: (a -> b -> b) -> b -> [a] -> b foldr combine base [] = base foldr combine base (x:xs) = combine x (foldr combine base xs)

Соответственно, правая свёртка списка [x1,x2,...,xn] преобразуется в вызовы:

combine x1 (combine x2 (...(combine xn base)...))

Использование свёрток предполагает единую схему реализуемой функции, которой мы будем всюду придерживаться. Например, для правой свёртки эта схема выглядит так:

dwImpl :: (a -> Bool) -> [a] -> [a] dwImpl predicate list = foldr combine base list where base = ... combine x xs = ...

Для удобства тестирования различных реализаций функции dropWhile подготовим две вспомогательные функции. Функция evalDW вычисляет результаты тестируемой реализации на каждом задании из списка tasks, а функция testDW сравнивает результаты, полученные тестируемой реализацией, с результатами dropWhile. Список tasks состоит из пар (предикат, исходный список).

evalDW dwImpl = let tasks = [((<5), [1..10]), ((>0), [1,2,-3,2,1]), (even, [2,4,1,2,3]), ((==1), [2,2,1,1]), ((/=0), [1..5])] in map (uncurry dwImpl) tasks testDW dwImpl = evalDW dwImpl == evalDW dropWhile > evalDW dropWhile [[5,6,7,8,9,10],[-3,2,1],[1,2,3],[2,2,1,1],[]] > testDW dropWhile True

Таким образом, если testDW dwImpl == True, то на указанных примерах функция dwImpl ведёт себя так же, как dropWhile, а значение False будет сигнализировать об ошибке. Использованная в функции evalDW стандартная функция uncurry позволяет вызвать функцию dwImpl с двумя аргументами, передав ей только один — пару (предикат, список).

Чтобы понять, в чём состоит основная сложность поставленной задачи, попробуем привести неправильное, хотя и очень близкое к правильному, решение:

dropWhileWrong predicate list = foldr combine base list where base = [] combine x xs | predicate x = xs | otherwise = x:xs > testDW dropWhileWrong False > evalDW dropWhileWrong [[5,6,7,8,9,10],[-3],[1,3],[2,2],[]]

Из примеров видно, что эта реализация удаляет не только начальные элементы списка, удовлетворяющие предикату, но и все остальные, реализуя тем самым стандартную функцию filter. Действительно, свёртка проходит по всему списку, а у нас нет способа остановить её в нужном месте. Проблема здесь в нехватке контекстной информации: удалять нужно не просто элементы, удовлетворяющие предикату, а элементы, удовлетворяющие предикату и стоящие в начале списка. Как раз вторая часть этого условия в нашей неправильной реализации не учитывается, а извлечь её из аргументов функции combine невозможно.

2.2  Добавляем контекст

Итак, первоочередная задача — добавление контекста. Это можно сделать, например, так: результатом свёртки становится пара (сформированный список, контекстная информация). Самый простой вариант достаточной контекстной информации — признак начала списка (логическое значение). Тогда при свёртке списка слева направо (с использованием левой свёртки foldl) этот флаг учитывается, и удаление элемента происходит, только если он имеет истинное значение. Значение флага меняется на False при обнаружении первого элемента, не удовлетворяющего предикату, после чего все оставшиеся элементы переносятся в новый список без изменения. В самом конце из пары выделяется первый элемент — список, который и является результатом:

dropWhileWithContext predicate list = fst (foldl combine base list) where base = ([], True) combine res@(xs, lead) x | lead && predicate x = res | otherwise = (xs++[x], False) > testDW dropWhileWithContext True

Рассмотрим работу функции на конкретном примере, предположив, что выполняется следующий вызов:

> dropWhileWithContext (<3) [1,2,3,4,1,5]

Согласно определению левой свёртки, этот вызов трансформируется в последовательность вызовов combine:

combine (combine (combine (combine (combine (combine ([], True) 1) 2) 3) 4) 1) 5

Соберём в таблицу аргументы и результаты всех вызовов функции combine, начиная с самого внутреннего (звёздочкой помечены результаты, полученные по ветви otherwise):

 Аргументы 
Шаг res@(xslead) xРезультат
1([], True)1([], True)
2([], True)2([], True)
3([], True)3([3], False)*
4([3], False)4([3,4], False)*
5([3,4], False)1([3,4,1], False)*
6([3,4,1], False)5([3,4,1,5], False)*

Окончательно, получаем:

> dropWhileWithContext (<3) [1,2,3,4,1,5] [3,4,1,5]

Фактически, обработка элементов списка при левой свёртке ведётся от начала к концу, поэтому каждый следующий элемент должен добавляться к концу формируемого списка с помощью относительно неэффективной операции конкатенации (++). Если бы элементы списка обрабатывались в обратном порядке, то очередной элемент можно было бы добавлять в начало формируемого списка с помощью эффективного конструктора списка (:). Для достижения соответствующего результата придётся прибегнуть к правой свёртке. К сожалению, в этом случае контекстная информация в виде признака начала списка перестаёт работать: определить, в какой момент «начинается» начальная часть списка при движении с конца невозможно. К счастью, можно придумать другой контекст (предложенный Грэмом Хаттоном в статье [3]) — будем формировать пару, состоящую из двух списков:

  1. Все просмотренные к настоящему моменту элементы.
  2. Все просмотренные к настоящему моменту элементы, за исключением начальных, удовлетворяющих предикату.

Если в какой-то момент в ходе работы оказывается, что встречен элемент, не удовлетворяющий предикату, второй список отбрасывается, а его место занимает первый. Результатом является второй список, причём первый список — копия исходного.

dropWhileWithContext2 predicate list = snd (foldr combine base list) where base = ([], []) combine x (xs, ys) | predicate x = (x:xs, ys) | otherwise = (x:xs, x:xs) > testDW dropWhileWithContext2 True

Теперь попробуем выполнить вызов:

> dropWhileWithContext2 (<3) [1,2,3,4,1,5]

Правая свёртка преобразуется в последовательность вызовов:

combine 1 (combine 2 (combine 3 (combine 4 (combine 1 (combine 5 base)))))

Видно, что при правой свёртке самому внутреннему вызову функции combine передаётся последний элемент списка. Посмотрим на аргументы и результаты всех вызовов функции combine (звёздочка снова обозначает результат, полученный по ветви otherwise):

 Аргументы 
Шаг x (xsys)Результат
15([],[])([5],[5])*
21([5],[5])([1,5],[5])
34([1,5],[5])([4,1,5],[4,1,5])*
43([4,1,5],[4,1,5])([3,4,1,5],[3,4,1,5])*
52([3,4,1,5],[3,4,1,5])([2,3,4,1,5],[3,4,1,5])
61([2,3,4,1,5],[3,4,1,5])([1,2,3,4,1,5],[3,4,1,5])

Итак, в результате получаем:

> dropWhileWithContext2 (<3) [1,2,3,4,1,5] [3,4,1,5]

К сожалению, обе разработанные функции имеют слишком строгое ограничение — они не работают с бесконечными списками. Например:

> take 3 (dropWhileWithContext2 (<5) [1..]) ERROR - ...

В следующих реализациях мы попытаемся обойти это ограничение.

2.3  Пишем функцию, возвращающую функцию

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

Эта идея исходит из того, что функция dropWhile фактически эквивалентна композиции нескольких функций tail (напомним, что функция tail возвращает хвост списка, т. е. весь список без первого элемента):

> dropWhile (<5) [1..10] [5,6,7,8,9,10] > tail (tail (tail (tail [1..10]))) [5,6,7,8,9,10]

Ту же композицию можно записать явно, пользуясь операцией (.):

> (tail.tail.tail.tail) [1..10] [5,6,7,8,9,10]

Теперь при свёртке исходного списка можно строить композицию нужного количества функций tail, а затем применять её снова к исходному списку:

dropWhileHigherOrder predicate list = (foldr combine base list) list where base = id combine x f | predicate x = f.tail | otherwise = id > testDW dropWhileHigherOrder True

Функция id — это тождественное отображение, играющее роль нейтрального элемента при композиции функций. Чтобы понять, как работает функция dropWhileHigherOrder, нужно аккуратно проследить, что является результатом свёртки. Для этого напишем вспомогательную функцию, которая вместо композиции строит список строк — названий соответствующих функций:

dropWhileHigherOrderStrings predicate list = foldr combine base list where base = ["id"] combine x f | predicate x = f++["tail"] | otherwise = ["id"] > dropWhileHigherOrderStrings (<5) [1..10] ["id","tail","tail","tail","tail"]

Заметим, что если первый элемент исходного списка не удовлетворяет предикату, то вся композиция исчерпывается одной единственной функцией id:

> dropWhileHigherOrder (<5) [5..10] [5,6,7,8,9,10] > dropWhileHigherOrderStrings (<5) [5..10] ["id"]

Рассмотрим работу свёртки на уже знакомом примере:

> dropWhileHigherOrder (<3) [1,2,3,4,1,5] [3,4,1,5]
 Аргументы 
Шаг x fРезультат
15idid*
21idid.tail
34id.tailid*
43idid*
52idid.tail
61id.tailid.tail.tail

Теперь нужно убедиться, что полученные функции работают с бесконечными списками. Действительно:

> take 3 (dropWhileHigherOrder (<5) [1..]) [5,6,7] > dropWhileHigherOrderStrings (<5) [1..] ["id","tail","tail","tail","tail"]

Запишем начальную часть последовательности вызовов функции combine, в которую преобразуется вызов dropWhileHigherOrder в этом примере:

combine 1 (combine 2 (combine 3 (combine 4 (combine 5 (combine ...)))))

Заметим, что при обработке элементов списка, не удовлетворяющих предикату, результат функции combine не зависит от значения свёртки оставшейся части списка. Действительно, выбор нужного варианта её определения осуществляется без использования второго аргумента f (результат свёртки оставшейся части списка), а как только выбранным оказывается второй вариант (otherwise = id; очередной элемент не удовлетворяет предикату), он не нужен и для вычисления результата. В нашем примере первый элемент, не удовлетворяющий предикату — это число 5, и второй аргумент соответствующего вызова функции combine вычисляться не будет. Здесь проявляется свойство ленивости вычислений в языке Haskell.


Рис. 1: Дерево вызовов, формируемое foldr

На рис. 1 показано дерево вызовов, формируемое foldr в этом примере. Штриховой рамкой отмечена свёртка хвоста, вычисление которой не потребуется, а курсивом написаны результаты соответствующих вызовов combine. Результатом вызова функции foldr является композиция id.tail.tail.tail.tail, которая затем применяется к исходному списку.

Интересно, что эффект ленивости можно испортить, добавив заведомо истинное условие для выбора варианта определения функции (примитивная операция seq f True принудительно вычислит f, а затем, отбросив результат вычисления, вернёт True):

dropWhileHigherOrderSpoiled predicate list = (foldr combine base list) list where base = id combine x f | seq f True && predicate x = f.tail | otherwise = id > testDW dropWhileHigherOrderSpoiled True > dropWhileHigherOrderSpoiled (<3) [1..] ERROR - ...

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

К сожалению, у функции dropWhileHigherOrder есть другой недостаток: результатом свёртки может оказаться функция, состоящая из композиции огромного числа функций tail (их количество зависит от длины начальной части списка, подлежащей удалению), и памяти для хранения этой композиции может оказаться недостаточно. Из следующего примера видно, что dropWhileHigherOrder не справляется с большим, хоть и конечным, объёмом данных, хотя у dropWhile никаких проблем с этим нет (разумеется, вычисления продолжаются довольно долго):

> dropWhile (<1000000) [1..1000001] [1000000,1000001] > dropWhileHigherOrder (<1000000) [1..1000001] ERROR - ...

2.4  Совмещаем композицию и применение

Новая идея — совместить построение композиции функций tail с одновременным применением их к списку. Вспомним, что результатом свёртки в целом, а значит и функции combine в частности, является функция, которая затем применяется к списку. Это означает, что функцию combine:

combine :: a -> ([a]->[a]) -> ([a]->[a]) combine x f | predicate x = f.tail | otherwise = id

можно переписать, явно указав, что она возвращает функцию над списками:

combine x f = \list -> (if predicate x then f.tail else id) list

или, что то же самое:

combine x f = \list -> if predicate x then (f.tail) list else id list

От использования безымянной λ-функции можно отказаться, перенеся её аргумент list непосредственно в аргументы combine:

combine :: a -> ([a]->[a]) -> [a] -> [a] combine x f list | predicate x = (f.tail) list | otherwise = id list

Очевидно, теперь можно избавиться от явной композиции и функции id:

combine x f list | predicate x = f (tail list) | otherwise = list

Заметим, что если эту версию трёхаргументной функции combine вызывать с двумя аргументами (как это фактически происходит при свёртке), то результатом будет функция над списками, т. е. именно то, что требуется.

Проведённые до сих пор изменения пока не привели к ожидаемому эффекту, так как вследствие свойства ленивости вызов tail будет задерживаться до тех пор, пока его результат не понадобится. Т. е. вместо явной композиции в нашей функции мы получаем неявную в трансляторе Haskell. Сделаем ещё один шаг — потребуем вычислить хвост списка, воспользовавшись сопоставлением с образцом:

combine x f list@(_:xs) | predicate x = f xs | otherwise = list

Заметим, что список list здесь гарантированно не пустой, так как максимальное количество вызовов combine равно количеству элементов в списке (все эти вызовы потребуются только в том случае, если все элементы списка удовлетворяют предикату, т. е. их все требуется удалить).

Теперь всё должно работать как следует. Приведём полученную функцию полностью:

dropWhileHigherOrder2 predicate list = (foldr combine base list) list where base = id combine x f list@(_:xs) | predicate x = f xs | otherwise = list > testDW dropWhileHigherOrder2 True > take 3 (dropWhileHigherOrder2 (<5) [1..]) [5,6,7] > dropWhileHigherOrder2 (<1000000) [1..1000001] [1000000,1000001]

Посмотрим, что происходит при выполнении следующего вызова:

> dropWhileHigherOrder2 (<3) [1..5]

Сначала выполняется первый шаг свёртки:

dropWhileHigherOrder2 (<3) [1..5] => (foldr combine id [1..5]) [1..5] => (combine 1 (foldr combine id [2..5])) [1..5]

Так как combine теперь трёхаргументная, она сразу применяется к списку:

combine 1 (foldr combine id [2..5]) [1..5]

Число 1 удовлетворяет предикату, поэтому выбирается первый вариант определения combine (f xs):

(foldr combine id [2..5]) [2..5]

Ещё два шага свёртки и два перехода от двухаргументной combine к трёхаргументной:

(combine 2 (foldr combine id [3..5])) [2..5] => combine 2 (foldr combine id [3..5])) [2..5] => (combine 3 (foldr combine id [4..5])) [3..5] => combine 3 (foldr combine id [4..5])) [3..5]

Как и прежде, свёртка строится до первого элемента, не удовлетворяющего предикату (<3 в нашем примере), поэтому второй аргумент последнего вызова combine не вычисляется, а результатом оказывается третий:

Получаемая последовательность вызовов показана на рис. 2.


Рис. 2: Последовательность вызовов combine

Однако наш путь на этом не заканчивается. Изучая код функции dropWhileHigherOrder2, можно заметить, что здесь используются две копии списка — по одной из них идёт свёртка, а ко второй применяется её результат. Понятно, что очередной сворачиваемый элемент можно брать из любого из этих списков. Например, в следующем варианте он берётся из второй копии:

dropWhileHigherOrder2' predicate list = (foldr combine base list) list where base = id combine _ f list@(x:xs) | predicate x = f xs | otherwise = list > testDW dropWhileHigherOrder2' True

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

dropWhileHigherOrder2'' predicate list = (foldr combine base [1..length list]) list where base = id combine _ f list@(x:xs) | predicate x = f xs | otherwise = list > testDW dropWhileHigherOrder2'' True

Длина списка, передаваемого свёртке, обеспечивает выполнение нужного количества операций. В принципе, эту задачу тоже можно поручить второй копии списка: для этого нужно обязать функцию combine проверять её пустоту. Заметим, что при этом исчезнет необходимость в присваивании аргументу base тождественного преобразования, так как до его использования свёртка доходить не будет, останавливаясь на последнем вызове combine. Окончательная версия выглядит следующим образом:

dropWhileHigherOrder3 predicate list = (foldr combine base [1..]) list where base = undefined combine _ _ [] = [] combine _ f list@(x:xs) | predicate x = f xs | otherwise = list > testDW dropWhileHigherOrder3 True

Здесь использование бесконечного списка [1..] обеспечивает выполнение того количества операций, которое необходимо в каждом конкретном случае.

3  Свёртка как комбинатор неподвижной точки

3.1  Некоторые сведения из λ-исчисления

Одной из важнейших характеристик функционального программирования является использование функций как значений первого класса (first class values). Это означает, что функции наряду с данными других типов — числами, логическими значениями, списками — могут быть аргументами или возвращаемыми значениями других функций, а следовательно, с ними можно выполнять различные операции, например, композицию. Такое широкое применение функций требует введения удобного их представления (нотации).

Соответствующее представление была изобретено в 30-е годы Алонзо Чёрчем. В нём в качестве вспомогательного символа используется греческая буква λ (с примерами её использования в языке Haskell мы уже встречались). λ-нотация важна не сама по себе, а как инструмент построения формальной системы λ-исчисления, которое является теоретической основой функционального программирования. В рамках этого исчисления строится понятие λ-термов и определяются способы их преобразования (редукции). На базе λ-термов можно вводить целые числа и арифметические операции, логические значения и операции над ними (в т. ч. условную операцию), а также типы данных, строя таким образом полноценный язык программирования. Многие функциональные языки программирования можно считать расширениями λ-исчисления, а при их трансляции иногда происходит возврат в λ-исчисление. Более подробно процесс построения языка программирования на базе λ-исчисления изложен в курсе лекций [8].

Серьёзной проблемой при этом оказывается тот факт, что функции в λ-исчислении являются безымянными. Дело в том, что для реализации рекурсии необходимо в теле функции использовать её имя — но что же делать, если имени нет? Оказывается, эта проблема решается благодаря существованию так называемых комбинаторов неподвижной точки (они ещё называются Y-комбинаторами). Это λ-термы специального вида, предназначенные для отыскания неподвижной точки отображения.

Напомним, что точка x называется неподвижной точкой отображения f, если x = f(x). Если отображение работает на множестве функций, то и неподвижная точка тоже является функцией. Именно такие неподвижные точки ищут комбинаторы неподвижной точки. В λ-исчислении комбинаторы неподвижной точки используются для моделирования рекурсивных вызовов. В следующем пункте будет продемонстрировано их применение для реализации функции вычисления факториала.

3.2  Вычисление факториала

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

fact n | n > 0 = n * fact (n-1) | otherwise = 1

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

factNonRec f n | n > 0 = n * f (n-1) | otherwise = 1

Возьмём какой-нибудь комбинатор неподвижной точки:

fix f = f (fix f)

Необходимо заметить, что комбинатор такого вида не является комбинатором неподвижной точки в терминах λ-исчисления, так как в его определении явно присутствует рекурсия. Можно привести примеры более корректных в этом смысле комбинаторов, которые одновременно являются более сложными. Однако для наших целей достаточно этого упрощённого комбинатора, за подробностями о «настоящих» Y-комбинаторах можно обратиться к пособию [8].

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

fact' = fix factNonRec

Протестируем полученную функцию, сравнив ее результаты с факториалами, вычисленными самым прямолинейным способом2:

testFact factImpl = let test_values=[5,15,27,42] fact n = product [1..n] in map factImpl test_values == map fact test_values > testFact fact' True

Вызов полученной функции fact' приводит к многократному вызову функции factNonRec, причём этот процесс останавливается при выполнении ветви otherwise = 1. Попытаемся посмотреть, что происходит при вызове fact' 3:

fact' 3 => (fix factNonRec) 3 => factNonRec (fix factNonRec) 3 => 3 * ((fix factNonRec) 2) => 3 * (factNonRec (fix factNonRec) 2) => 3 * 2 * ((fix factNonRec) 1) => 3 * 2 * (factNonRec (fix factNonRec) 1) => 3 * 2 * 1 => 6

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

3.3  Использование свёртки как комбинатора неподвижной точки

Мы уже знаем, что комбинаторы неподвижной точки позволяют строить рекурсивные функции. Попробуем сделать то же самое с функцией dropWhile. Вспомним ещё раз её рекурсивную реализацию:

dropWhile predicate [] = [] dropWhile predicate list@(x:xs) | predicate x = dropWhile predicate xs | otherwise = list

Проделаем с ней ту же операцию, которой подверглась функция fact:

dropWhileNonRec f predicate [] = [] dropWhileNonRec f predicate list@(x:xs) | predicate x = f predicate xs | otherwise = list

Теперь оказывается, что эта функция очень похожа на combine в её последнем воплощении (в функции dropWhileHigherOrder3):

combine _ _ [] = [] combine _ f list@(x:xs) | predicate x = f xs | otherwise = list

Разница лишь в том, что dropWhileNonRec содержит predicate в качестве аргумента и явно передаёт его функции f — заменителю рекурсивного вызова. В combine это не требуется только потому, что аргумент predicate и так доступен из объемлющей функции. Кроме того, в combine имеется фиктивный первый аргумент.

Таким образом, функция свёртки в последней реализации dropWhile играет роль комбинатора неподвижной точки. Именно поэтому свёртке не нужен список с исходными данными, ей нужен просто большой список, чтобы гарантировать достаточное для отыскания неподвижной точки количество рекурсивных вызовов.

Нам остаётся, во-первых, убедиться в том, что полученная из dropWhileNonRec функция делает то, что требуется:

dropWhile' = fix dropWhileNonRec > testDW dropWhile' True > take 3 (dropWhile' (<5) [1..]) [5,6,7]

А во-вторых, что foldr с тем же успехом можно применить для вычисления неподвижной точки функции factNonRec. Для этого достаточно добавить функции factNonRec фиктивный первый аргумент и передать её функции foldr вместо combine:

factNonRec f n | n > 0 = n * f (n-1) | otherwise = 1 fact'' = foldr (\_ -> factNonRec) undefined [1..] > fact'' 5 120 > testFact fact'' True

Оформим такое использование свёртки в виде комбинатора неподвижной точки:

fix' f = foldr (\_ -> f) undefined [1..] > testDW (fix' dropWhileNonRec) True > testFact (fix' factNonRec) True

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

4  Свёртка как оператор примитивной рекурсии

4.1  Некоторые сведения из теории рекурсивных функций

Теория рекурсивных функций наряду с машинами Тьюринга и λ-исчислением является одним из подходов к формализации понятия вычислительного алгоритма. Основной принцип построения рекурсивных функций — рекурсивные определения, при которых значения функции для данных аргументов определяются через значения функции для «более простых» аргументов. При этом понятие «более простой» также нуждается в формализации.

Примитивно рекурсивные функции — это очень широкий и интересный класс всюду определённых функций, который можно получить с помощью рекурсивных определений. Основной задачей этого пункта будет построение класса примитивно рекурсивных функций произвольного числа переменных на множестве натуральных чисел (включая 0). В следующем пункте будет показано, как можно сформулировать понятие примитивно рекурсивной функции над списками.

Во-первых, введём набор простейших функций, из которых можно будет получить все остальные. К ним относятся:

  1. Функция следования: S(x)=x+1.
  2. Нуль-функция: 0(x)=0.
  3. Функции-проекторы: Imn(x1,…,xn)=xm.

Функции-проекторы позволяют получить из набора аргументов аргумент с заданным номером. В дальнейшем наборы аргументов для краткости будем обозначать так:

(x1,…,xn)=x.

Частным случаем функций-проекторов является тождественная функция: её можно записать так:

f(x)=x=I11(x).

Во-вторых, необходимы операторы, позволяющие получать из одних функций другие. Первым из таких операторов является оператор композиции. С его помощью можно получить из функции f и набора функций gi новую функцию ϕ, определяемую правилом:

ϕ(x)=f(g1(x),…,gk(x)).

Заметим, что оператор композиции позволяет выразить любые числовые константы (константные функции), для этого достаточно несколько раз применить функцию следования к нуль-функции, например:

5 = S(S(S(S(S(0(x))))))=((((0+1)+1)+1)+1)+1. 

Здесь оператор композиции применён пять раз: первый раз он применяется к функциям S и 0, а все остальные — к функции S и результату предыдущего применения.

Второй оператор называется оператором примитивной рекурсии. Он позволяет по заданным функциям g и h построить новую функцию ψ, определяемую следующими двумя правилами (схема рекурсии):

ψ(x,0)=g(x),
ψ(x,y+1)=h(x,y,ψ(x,y)).  

Важно, что рекурсия определяется только по одной переменной. Функция g задаёт базу рекурсии, а h — шаг рекурсии.

Теперь можно определить класс примитивно рекурсивных функций — это наименьшее множество, содержащее:

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

x+0=x,
x + (y+1)=(x+y) + 1.

Эти правила можно записать в ином виде:

+(x,0)=I11(x),
+(x,y+1)=S(+(x,y)).

Теперь видно, что функцию сложения можно представить как результат применения оператора примитивной рекурсии к функциям I11 и S.

Похожим образом можно получить умножение, для этого достаточно заметить, что

x × 0=0=0(x),
x × (y+1)=(x× y) + x=+(x,x × y).

Таким образом, функцию умножения можно представить как результат применения оператора примитивной рекурсии к функции 0 и сложению.

Функция вычисления факториала также является примитивно рекурсивной, её можно получить так:

0!=1,
(n+1)!=(n+1) × n!

Примитивно рекурсивные функции не исчерпывают всё множество вычислимых функций. Классическим примером вычислимой функции, не являющейся примитивно рекурсивной, является функция Аккермана. Для расширения множества примитивно рекурсивных функций в рамках теории рекурсивных функций вводится третий оператор минимизации. Он позволяет построить по двум заданным функциям f1 и f2 новую функцию ω, определяемую правилом:

ω(x) = min 

 y |  f1(x,y)=f2(x, y)

C его помощью строится множество частично рекурсивных функций, а после этого доказывается, что вычислительная способность этого множества полностью эквивалентна машине Тьюринга (и, соответственно, всем остальным полным вычислительным моделям). Частично рекурсивные функции могут не быть всюду определёнными, что соответствует зацикливанию машины Тьюринга на некоторых исходных данных (или отсутствию нормальной формы у некоторых λ-термов). Важно помнить, что слово «частично» в названии этих функций относится не к рекурсивности, а к их области определения. Всюду определённые частично рекурсивные функции называются общерекурсивными, они образуют строгое подмножество множества частично рекурсивных функций и надмножество примитивно рекурсивных. Более подробно с теорией рекурсивных функций можно познакомиться по книге В. И. Игошина [7], или в любой другой книге по математической логике и теории алгоритмов.

4.2  Примитивная рекурсия на списках

Теперь нас будут интересовать примитивно рекурсивные функции на списках. Место функции следования здесь занимает конструктор списка (операция присоединения элемента к списку):

S(xxs) = x:xs,

а нуль-функция заменяется на пустой список:

0(xs) = [ ].

Роль функций-проекторов будет играть сопоставление с образцом, а вместо наборов аргументов будем использовать кортежи, обозначая их, как и прежде, x. Оператор композиции — это стандартный механизм композиции функций, особого определения требует только оператор примитивной рекурсии:

ψ(x,[ ])=g(x),
ψ(x,y:ys)=h(x,y,ys,ψ(x,ys)).  

Следует обратить внимание на то, что в функции h добавился ещё один аргумент: вместо y, как у функций над множеством натуральных чисел, теперь используются y и ys (голова списка и его хвост). Такое изменение связано с тем, что в предыдущем случае получить при необходимости y+1 из y можно легко, а вот извлечь из хвоста списка его голову несколько труднее. Заметим также, что ψ вызывается рекурсивно для хвоста списка.

Таким образом, оператор примитивной рекурсии позволяет из двух функций g и h указанного вида получить новую функцию над списками. Любая примитивно рекурсивная функция над списками как обычно строится из простейших с использованием конечного числа применений операторов композиции и примитивной рекурсии.

Дальнейшей целью этого пункта будет выражение оператора примитивной рекурсии через правую свёртку. В следующем пункте мы укажем соответствующие функции g и h для нескольких стандартных функций обработки списков, которые, как выяснится в результате, окажутся примитивно рекурсивными.

Итак, оператор примитивной рекурсии должен работать с тремя типами:

  1. par — тип первого аргумента получаемой функции.
  2. val — тип элемента списка (соответственно, тип самого списка — [val]).
  3. res — тип результата обработки списка.

Он должен принимать в качестве аргументов две функции g и h следующих типов:

g :: par -> res h :: par -> val -> [val] -> res -> res

Наконец, возвращать он будет функцию ψ типа par -> [val] -> res.

Соберём все вместе и получим тип функции, реализующей оператор примитивной рекурсии:

primRec :: (par->res) -> (par -> val -> [val] -> res -> res) -> (par -> [val] -> res)

Заметим, что тип результата, вообще говоря, можно в скобки не заключать, так как результат функции зависит от того, как эту функцию вызывать: если передать ей вместо двух аргументов (функций) три (две функции и ещё один аргумент типа par), то получится функция, преобразующая список в результат его обработки ([val] -> res). А если зафиксировать ещё и список, то получится константа — результат обработки типа res.

Идея реализации оператора примитивной рекурсии заключается в хранении на каждом шаге свёртки полной контекстной информации — результата последнего шага свёртки и обработанной к настоящему моменту части списка:

primRec g h x ys = fst (foldr combine base ys) where base = (g x, []) combine y (z, ys) = (h x y ys z, y:ys)

Мы не будем приводить доказательство корректности соответствующей функции: подробности можно уточнить в работе Хаттона [3]. Впрочем, корректность имеет место только до определённого предела: с бесконечными списками функции, определённые с помощью такого оператора примитивной рекурсии, работать не будут.

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

primRec' g h = fix funcNonRec where funcNonRec f x [] = g x funcNonRec f x (y:ys) = h x y ys (f x ys)

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

4.3  Примеры реализации стандартных функций

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

Для задания функций g и h, используемых в схеме рекурсии, мы будем использовать либо константные функции (const v — функция, возвращающая значение v при любом значении аргумента), либо безымянные λ-функции. Для обозначения фиктивного аргумента (там, где он не требуется) будем использовать пустой тип () (тип с единственным значением, также обозначаемым как ()).

Первым делом определим функцию, вычисляющую длину списка:

length([ ])=0,
length(y:ys)=1+length(ys).  

Здесь мы пытались написать правила для схемы рекурсии, но совершенно случайно почти дословно повторили обычное рекурсивное определение функции length. Теперь понятно, каковы должны быть функции g и h: первая из них есть константа 0, а вторая должна увеличивать значение своего последнего аргумента (результата рекурсивного вызова) на единицу, игнорируя все остальные. Дополнительный аргумент функции length не требуется, поэтому его можно заменить на ().

Окончательно получаем:

length' = primRec (const 0) (\ _ _ _ z -> 1+z) ()

При желании можно ещё проверить тип этой функции и вызвать её для какого-нибудь списка:

> :type length' length' :: [a] -> Integer > length' [1..100] 100

Совершенно аналогично пишутся функции, вычисляющие сумму и произведение элементов списка:

sum' = primRec (const 0) (\ _ y _ z -> y+z) () product' = primRec (const 1) (\ _ y _ z -> y*z) ()

Впрочем, эти функции довольно просты, попробуем реализовать что-нибудь более серьёзное, например, map и filter:

map' = primRec (const []) (\ f y _ z -> f y : z) filter' = primRec (const []) (\ predicate y _ z -> if predicate y then z else y:z)

Здесь всё ещё проще: это функции с двумя аргументами, поэтому потребность в фиктивном аргументе () отпадает. Первые аргументы этих функций напрямую передаются функции h, используемой в схеме рекурсии, и уже в ней вызываются как функции.

Чуть больше сложностей возникает с функцией minimum. Во-первых, она не использует начальное значение, а во-вторых, должна сравнивать элементы списка между собой, поэтому механизму вывода типов требуется небольшая подсказка:

minimum' :: (Ord a) => [a] -> a minimum' = primRec (const undefined) (\ _ y ys z -> if null ys then y else min y z) ()

Нежно любимая нами функция dropWhile также является примитивно рекурсивной, поэтому и для неё есть соответствующее определение:

dropWhile'' = primRec (const []) (\ predicate y ys z -> if predicate y then z else y:ys) > testDW dropWhile'' True

Теперь можно сравнить функцию dropWhile и её первую неправильную реализацию, оказавшуюся реализацией filter, в их исконном, теретико-алгоритмическом (рекурсивно-функциональном), виде:

dropWhile'' = primRec (const []) (\ predicate y ys z -> if predicate y then z else y:ys) filter' = primRec (const []) (\ predicate y _ z -> if predicate y then z else y:z)

Наконец, ничто не мешает определить саму функцию foldr:

foldr' = curry ( primRec (\ (_, base) -> base) (\ (op, _) y _ z -> op y z))

Функция foldr принимает три аргумента вместо двух допустимых, поэтому первые два пришлось объединить в кортеж. Чтобы пользователь ничего не заметил, функцию, полученную в результате действия оператора примитивной рекурсии, необходимо каррировать, т. е. преобразовать из функции, принимающей пару, в функцию двух аргументов. Эту задачу выполняет стандартная функция curry.

Пользуясь выведенной свёрткой, можно попробовать снова реализовать dropWhile, взяв за основу, к примеру, реализацию с контекстом из двух списков:

dropWhile''' predicate list = snd (foldr' combine base list) where base = ([], []) combine x (xs, ys) | predicate x = (x:xs, ys) | otherwise = (x:xs, x:xs) > testDW dropWhile''' True

Итак, свёртка реализует оператор примитивной рекурсии, что позволяет выразить с её помощью большое количество примитивно рекурсивных функций, в том числе практически все стандартные функции обработки списков.

5  Заключение

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

Следует заметить, что само использование свёртки в качестве комбинатора неподвижной точки берёт начало из теоретико-категорной работы Питера Фрейда [2], в которой он замечает, что такой комбинатор может быть выражен в виде композиции анаморфизма и катаморфизма. В работе Мейера и Хаттона [4] результаты Фрейда переводятся на язык функционального программирования и формулируются для произвольных алгебраических типов данных.

В случае списков катаморфизм оказывается свёрткой, а анаморфизм — функцией List.unfoldr. Ясно, что из неё легко получить бесконечный список, который мы использовали при реализации комбинатора неподвижной точки:

> unfoldr (\x -> Just (x, x+1)) 1 [1,2,3,4,...

Впрочем, необходимо иметь в виду, что на практике выражение всех рекурсивных функций в терминах свёрток вряд ли полезно: ясно, что замена рекурсии на свёртку может привести к сильному усложнению кода.

Список литературы

[1]
Richard S. Bird. Introduction to Functional Programming Using Haskell (second edition). Prentice-Hall, 1998.
[2]
Peter Freyd. Algebraically complete categories. Proceedings of the 1990 Como Category Theory Conference, volume 1488 of Lecture Notes In Math, pages 95–104. Springer-Verlag, 1990.
[3]
Graham Hutton. A Tutorial on the Universality and Expressiveness of Fold. Journal of Functional Programming, volume 9, number 4, pages 355–372, http://www.cs.nott.ac.uk/~gmh/fold.pdf. Cambridge University Press, 1999.
[4]
Erik Meijer and Graham Hutton. Bananas in space: Extending fold and unfold to exponential types. Proceedings of the 7th SIGPLAN-SIGARCH-WG2.8 International Conference on Functional Programming and Computer Architecture, pages 324–333, http://www.cs.nott.ac.uk/~gmh/bananas.pdf. ACM Press, 1995.
[5]
Bernie Pope. Getting a fix from the right fold. The Monad Reader, Issue 6, http://www.haskell.org/sitewiki/images/1/14/TMR-Issue6.pdf, 2007.
[6]
Fritz Ruehr. The Evolution of a Haskell Programmer. http://www.willamette.edu/~fruehr/haskell/evolution.html.
[7]
В. И. Игошин. Математическая логика и теория алгоритмов. М.: Академия, 2008.
[8]
Джон Харрисон. Введение в функциональное программирование. Конспект лекций, русский перевод доступен по адресу http://code.google.com/p/funprog-ru/.
[9]
Евгений Кирпичёв. Элементы функциональных языков. Практика функционального программирования, №3, декабрь 2009.

1
Автор представляет себе студенческую молодость примерно так: изучение программирования в любом вузе начинается с λ-исчисления, и на втором или, самое позднее, на третьем занятии студенты изучают комбинаторы неподвижной точки и реализуют с их помощью факториал.
2
Ещё несколько более или менее традиционных способов вычисления факториала приведены в [6].

Этот документ был получен из LATEX при помощи HEVEA