Схемы рекурсии, объясненные с использованием регулярных выражений

Учебник по катаморфизму и параморфизму

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

Точно так же, как использование циклов while и for вместо goto вносит структуру и гармонию в императивный поток управления, использование схем рекурсии вместо рукописной рекурсии вносит аналогичную структуру в рекурсивные вычисления. Это понимание настолько важно, что я повторю его еще раз: схемы рекурсии столь же важны для идиоматического функционального программирования, как for и while — для идиоматического императивного программирования. — Патрик Томпсон

У меня нет такого твердого мнения. Я думаю, что схемы рекурсии умопомрачительно интересны, и меня также смущает связь, которую Патрик Бар установил с Tree Automata, поскольку я проделал довольно много работы с Tree Automata, и наблюдать за тем, как она применяется на практике, гораздо интереснее. мне, чем вам.

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

Существует несколько типов рекурсии, поэтому у нас есть несколько схем, чтобы охватить их все. В этой статье я попытаюсь объяснить две наиболее распространенные схемы рекурсии:

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

Примечание. Эта статья требует понимания Haskell, по крайней мере, вплоть до реализации Functor.

Алгоритм производных регулярных выражений

Объяснение схем рекурсии требует примера. Для этого я выбрал производный алгоритм для регулярных выражений, о котором я рассказывал в предыдущей статье.

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

Функция производной или deriv возвращает регулярное выражение, оставшееся для сопоставления, с заданным символом в качестве входного значения. Мы зацикливаем это на входной строке, используя foldl, чтобы получить регулярное выражение, которое остается для сопоставления после того, как мы использовали всю строку. Затем мы проверяем, соответствует ли результирующее регулярное выражение пустой строке, используя функцию nullable, чтобы узнать, соответствует ли регулярное выражение, которое использовало всю строку, этой строке.

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

Вкус

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

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

что такое FAlgebra
почему появился новый тип под названием RegexF
как функция cata выполняет восходящую рекурсию

Что такое функтор

Наши схемы рекурсии требуют места для хранения промежуточных результатов во время нашей рекурсии. Нам нужен контейнер для этих результатов. Мы знаем, что функтор — отличный контейнер, поэтому мы превратим наш тип данных Regex в функтор, настроив его параметрами. Затем этот параметр может хранить различные промежуточные результаты во время наших рекурсивных алгоритмов.

Начнем с переименования Regex в RegexF, где F означает функтор. Мы параметризуем все рекурсивные Regex поля. Вот код:

Если вы вернетесь и посмотрите на исходное определение Regex, вы увидите, что мы заменили все рекурсивные вхождения Regex на r. Мы назвали параметр r для рекурсии или результата. Этот r будет использоваться для хранения логических результатов, поскольку мы выполняем восходящую рекурсию для нашей функции, допускающей значение NULL, используя катаморфизм, но об этом позже.

Во-первых, у нас есть проблема. Мы должны выбрать, какой параметр установить для r, чтобы вернуть исходное Regex, используя определение RegexF.

Если мы превратим r в Bool, мы сможем создать только очень маленькие выражения, такие как EmptyString, но другие будут иметь еще меньше смысла: Concat True False.
Если мы выберем r равным Regex, мы получим RegexF Regex, что будет работать, но мы потеряем свойство рекурсивного функтора.
Мы можем попытаться выбрать r как RegexF, тогда мы получим RegexF RegexF, это близко, но теперь нам нужно, чтобы еще один RegexF был параметром для второго RegexF, поэтому мы получаем RegexF (RegexF RegexF), но это бесконечная проблема. В какой-то момент мы хотим, чтобы эта рекурсия закончилась.
Мы можем попробовать два уровня RegexF, тогда мы получим RegexF (RegexF (RegexF ())), но тогда мы сможем представлять регулярные выражения только двухуровневой глубины.

Нам нужен функтор, но мы также не хотим ограничиваться максимальной глубиной рекурсии.

Поправляйся, Феликс.

Фиксированная точка — это место, где функция сходится или где вход функции равен выходу. Например: f(x) = x² имеет фиксированную точку 1, так как 1² = 1.

Мы можем воссоздать наш эквивалентный тип данных Regex, используя фиксированную точку:

type Regex = Fix RegexF

Как это Fix RegexF эквивалентно нашему исходному Regex?
Чтобы понять это, нам нужно поближе взглянуть на Fix. Fix — это тип данных с фиксированной точкой:

newtype Fix f = Fix (f (Fix f))

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

Но если вы спокойно посмотрите на каждую часть, это может иметь смысл:

newtype Fix f = Fix (f (Fix f))

Первый Fix — это имя типа.
Второй Fix — это имя конструктора типа.
Третий Fix — это используемый тип.

Тип Fix принимает один параметр типа с именем f. f — это функтор, что означает, что он также принимает параметр типа. В этом случае параметр типа будет последним Fix f.

Если мы выберем RegexF в качестве нашего f, наш параметр типа r будет Fix RegexF, но мы знаем, что Fix RegexF на самом деле Fix (RegexF (Fix RegexF)), а мы знаем, что на самом деле Fix (RegexF (Fix (RegexF (Fix RegexF)))) и т. д. Это именно то, что мы хотели. Теперь мы можем представлять регулярные выражения любой глубины. Феликс исправил!

WreckIt Ralph также может расфиксировать наш тип данных Fix, что будет полезно при реализации функции катаморфизма.

wreckit сопоставляется шаблону с Fix и возвращает значение внутри:

wreckit :: Fix f -> f (Fix f)
wreckit (Fix x) = x

Что такое F-алгебра

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

Алгебра состоит из следующего:

Способность формировать выражения. Например, конструкторы Regex и
Возможность вычислять эти выражения, например nullable :: Regex -> Bool

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

type Algebra e r = e -> r

Это означает, что функция nullable фактически является функцией NullableAlgebra.

type NullableAlgebra = Algebra Regex Bool
nullable :: NullableAlgebra

F-алгебра в теории категорий состоит из следующего:

Возможность формировать выражения, являющиеся функторами, например RegexF r и
Возможность вычислять эти выражения, например: nullable :: RegexF Bool -> Bool.

Это означает, что тип F-алгебры:

type FAlgebra f r = f r -> r

Функция nullableAlg — это NullableAlgebra:

type NullableFAlgebra = FAlgebra RegexF Bool
nullableAlg :: NullableFAlgebra

Катаморфизм: рекурсия снизу вверх

Как функция cata абстрагируется от восходящей рекурсии? Вот вся функция:

cata :: Functor f => FAlgebra f r -> Fix f -> r
cata alg = alg . fmap (cata alg) . wreckit

Это очень абстрактно. Давайте сделаем это более конкретным. Для удобства чтения давайте сначала добавим в Haskell оператор канала Elm, который эквивалентен оператору & в Haskell, но больше похож на канал Unix и указывает направление. Извините, мне легче читать.

infixl 0 |>
(|>) :: a -> (a -> b) -> b
x |> f = f x

Теперь давайте сделаем реализацию функции cata более конкретной для применения функции nullableAlg:

cata :: NullableFAlgebra -> Regex -> Bool
cata nullableAlg regex = 
  wreckit regex
  |> fmap (cata nullableAlg)
  |> nullableAlg

В качестве первого шага wreckit возьмет наш Regex и удалит внешний Fix:

wreckit :: Regex -> RegexF Regex

Теперь у нас есть функтор, а это значит, что мы можем fmap выполнить RegexF. fmap рекурсирует на один уровень вниз. Функция, с которой мы хотим выполнить рекурсию, — это функция nullable, эквивалентная cata nullableAlg.

nullable :: Regex -> Bool
nullable = cata nullableAlg

На каждом уровне рекурсии мы хотим вызывать нашу функцию nullable. Таким образом, каждый раз, когда мы fmap спускаемся на уровень, мы передаем вниз cata nullableAlg для вызова на более низком уровне.

fmap (cata nullableAlg) :: RegexF Regex -> RegexF Bool

Когда мы рекурсивно возвращаемся назад, мы возвращаем RegexF Bool, в котором хранятся промежуточные результаты вычислений nullable на нижних уровнях. Затем мы должны пройти через финальный nullableAlg, чтобы получить окончательный результат Bool.

nullableAlg :: RegexF Bool -> Bool

Это означает, что теперь мы можем определить функцию nullableAlg без какой-либо рекурсии, поскольку функция cata выполнит всю восходящую рекурсию для нашей функции nullable:

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

Умные конструкторы

Прежде чем мы проверим нашу следующую схему рекурсии, вы можете быть обеспокоены тем, как будет выглядеть API. Как вы объясните пользователям, что такое фиксированная точка для пользователей вашей библиотеки? Идея состоит в том, что мы ограничим эти детали реализации внутренними компонентами библиотеки. Наш API не будет раскрывать ни одну из фиксированных точек. Пользователям этой библиотеки не будет доступна функция nullableAlg, только функция nullable. То же самое касается конструкторов типов данных. Мы не хотим выставлять Fix за пределы нашей библиотеки, поэтому мы создаем более умные конструкторы, которые создают фиксированные точки для пользователя, которые мы можем выставить:

Это также будет сделано для нашего внутреннего удобства при реализации функции deriv с использованием параморфизма в следующем разделе.

Параморфизм

Если вы не понимаете циклы for, это просто параморфизм натуральных чисел — Джозеф Свеннингссон

Давайте снова посмотрим на исходную функцию deriv:

Функция deriv не является простой восходящей рекурсией, так как Concat шаг требует проверки, допускает ли первое выражение r значение NULL. Это информация, которая доступна только в стеке. Параморфизм не только сохраняет прерывистый результат в параметре функтора, но также сохраняет копию исходного выражения, чтобы мы могли проверить, допускает ли оно значение NULL. Для этого требуется новая алгебра под названием RAlgebra:

type RAlgebra f r = f (Fix f, r) -> r

Функтор теперь содержит кортеж, где первый параметр — копия исходного выражения, а второй — промежуточный результат. Наш DeriveRAlgebra будет выглядеть немного запутанно, так как наш промежуточный результат имеет тот же тип, что и копия оригинала:

type DeriveRAlgebra = RAlgebra RegexF Regex :: RegexF (Regex, Regex) -> Regex

Этот RAlgebra будет оцениваться функцией para:

para :: (Functor f) => RAlgebra f r -> Fix f -> r
para alg f =
  wreckit f
  |> fmap (\x -> (x, para alg x))
  |> alg

Мы можем сделать это более конкретным для функции derivAlg:

para :: DeriveRAlgebra -> Regex -> Regex
para derivAlg regex = 
  wreckit regex
  |> fmap (\x -> (x, para derivAlg x))
  |> derivAlg

Единственным отличием от функции cata является сохранение в кортеже копии исходных Regex, x, а не только промежуточного результата para derivAlg x.

Мы удаляем внешний слой Fix с помощью wreckit :: Regex -> RegexF Regex.
Мы рекурсивно спускаемся на один уровень функтора, используя fmap.
Функция, которую мы применяем на нижних уровнях, принимает Regex и возвращает исходный Regex, а также производный Regex: Regex -> (Regex, Regex).
Результатом является функтор RegexF (Regex, Regex), который мы можем затем оценить, используя: derivAlg c :: RegexF (Regex, Regex) -> Regex, чтобы получить наше окончательное производное Regex.

Это означает, что теперь мы можем определить функцию derivAlg без какой-либо рекурсии, так как функция para выполнит всю рекурсивную работу для нашей функции deriv:

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

Полный алгоритм

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

Полную демо можно найти на GitHub.

Заключение

Мы рассмотрели только две схемы рекурсии, но есть много других:

Помимо para и cata, есть еще одна складка под названием histo. Гистоморфизмы сохраняют историю всех рекурсивных вычислений, что полезно для алгоритмов, требующих запоминания для повышения эффективности, таких как Фибоначчи.
Разворачивается, включает ana, apo и futu. Анаморфизм — это Теория Категорий, Двойственная катаморфизму. По-гречески cata означает разрушение, а ana — созидание. Анаморфизм может рекурсивно построить выражение, например, построить список нулей заданной длины.
Кроме того, есть перескладки: hylo, который представляет собой cata после ana, и chrono, который представляет собой histo и futu.

Я связал некоторые ресурсы в разделе «Ссылки», если вам интересно узнать больше о схемах рекурсии, чтобы вы могли продолжить свои собственные эпические приключения с морфингом:

Спасибо

Andor Pénzes за корректуру и объяснение всех остальных схем рекурсии, тем более, что я до сих пор понимаю лишь некоторые из них.
Max Heiber за обнаружение ошибки и предложение лучшего объяснения восходящей рекурсии.