Схема рекурсии от Int -> Int? - PullRequest
Новая
       112

Схема рекурсии от Int -> Int?

0 голосов
/ 06 мая 2019

Идентификатор свёртки равен 

foldr (:) []

В более общем случае, со сгибами вы можете либо разрушить структуру и получить итоговое значение, либо ввести структуру таким образом, что вы получите ту же структуру вывода.

[Int] -> [Int] или [Int] -> Int или [Int] -> ?

Мне интересно, существует ли подобная идентичность с unfoldr / l.

Я знаю, как получить

Int -> [Int]

с раскрытием / аной.

Я ищу какой-то путь от

Int -> Int

со схемой рекурсии.

Ответы [ 2 ]

5 голосов
/ 07 мая 2019

Подводя итог вашему замечанию о факториалах, мы можем отметить, что натуральные числа можно рассматривать как рекурсивную структуру данных: 

data Nat = Zero | Succ Nat

В терминах рекурсивных схем машинного оборудования соответствующий базовый функтор будет: 

data NatF a = ZeroF | SuccF a
    deriving (Functor)

NatF, однако, изоморфен Maybe. Таким образом, рекурсивные схемы удобно делают Maybe базовым функтором типа Natural из base . Например, вот тип ana, специализированный для Natural: 

ana @Natural :: (a -> Maybe a) -> a -> Natural

Мы можем использовать его, чтобы написать раскрывающуюся личность для Natural: 

{-# LANGUAGE LambdaCase #-}

import Numeric.Natural
import Data.Functor.Foldable

idNatAna :: Natural -> Natural
idNatAna = ana $ \case
    0 -> Nothing
    x -> Just (x - 1)

Коалгебра, которую мы только что дали ana, равна project для Natural, project - функция, которая разворачивает один слой рекурсивной структуры. В терминах рекурсивных схем словарь, ana project - это раскрытие идентичности, а cata embed - это складка идентичности. (В частности, project для списков равно uncons из Data.List, за исключением того, что оно кодируется ListF вместо Maybe.)

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

fact :: Natural -> Natural
fact = para $ \case
    Nothing -> 1
    Just (predec, prod) -> prod * (predec + 1)

para делает доступным на каждом рекурсивном шаге оставшуюся часть структуры, которую нужно сложить (если бы мы складывали список, это был бы его хвост). В данном случае я назвал предоставленное значение predec, потому что на n -ом рекурсивном шаге снизу вверх predec равно n - 1.

Обратите внимание, что hylomorphism user11228628 , вероятно, является более эффективной реализацией, если вам случится позаботиться об этом. (Я не тестировал их, хотя.)

3 голосов
/ 06 мая 2019

Схема рекурсии, которая имеет дело с созданием промежуточной структуры и ее разрушением, чтобы структура не появлялась на входе или выходе, представляет собой гиломорфизм, записанный hylo в recursion-schemes.

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

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

Один из способов взглянуть на факториал - это произведение списка чисел с обратным отсчетом от начального n. В этом кадре мы можем думать о продукте как о нашей алгебре, снося список по одному минусу за раз, а обратный отсчет как о нашей коалгебре, составляя список как n, уменьшается.

recursion-schemes дает нам ListF в качестве удобного базового функтора для списков, поэтому мы будем использовать его в качестве типа данных, создаваемых коалгеброй и потребляемых алгеброй. Его конструкторы Nil и Cons, которые, конечно, напоминают конструкторы для полных списков, за исключением того, что ListF, как и любая базовая структура в схеме рекурсии, использует параметр типа в том месте, где списки будут использовать реальную рекурсию (имеется в виду Cons :: a -> b -> ListF a b вместо (:) :: a -> [a] -> [a]).

Так что это определяет наши типы. Теперь определение fact - довольно простое упражнение: 

import Prelude hiding (product)
import Data.Functor.Foldable

product :: ListF Int Int -> Int
product Nil = 1
product (Cons a b) = a * b

countDown :: Int -> ListF Int Int
countDown 0 = Nil
countDown n = Cons n (n - 1)

fact :: Int -> Int
fact = hylo product countDown
...