Примеры гистоморфизмов в Haskell

Ответ 1

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

data Nat = S Nat | Z

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

Мы можем легко построить новые натуральные числа из целых чисел:

-- Allow us to construct Nats
mkNat :: Integer -> Nat
mkNat n | n < 0 = error "cannot construct negative natural number"
mkNat 0 = Z
mkNat n = S $ mkNat (n-1)

Теперь мы сначала определим катаморфизм для этого типа, потому что гистоморфизм очень похож на него, и катаморфизм легче понять.

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

data NatF a = SF a | ZF -- Aside: this is just Maybe

Теперь мы можем определить тип нашего катаморфизма для Nat:

cata :: (NatF a -> a)
     -> (Nat -> a)

Для функции, которая умеет сворачивать нерекурсивную структуру NatF a в a, cata превращает это в функцию, чтобы сбрасывать целое Nat.

Реализация cata довольно проста: сначала сверните рекурсивный подтерм (если есть) и примените нашу функцию:

cata f Z = f ZF -- No subterm to fold, base case
cata f (S subterm) = f $ SF $ cata f subterm -- Fold subterm first, recursive case

Мы можем использовать этот катаморфизм для преобразования Nat обратно в Integer s, например:

natToInteger :: Nat -> Integer
natToInteger = cata phi where
  -- We only need to provide a function to fold
  -- a non-recursive Nat-like structure
  phi :: NatF Integer -> Integer
  phi ZF = 0
  phi (SF x) = x + 1

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

Гистоморфизм (гисто звучит очень похоже на "историю" ) позволяет нам получить доступ ко всем предыдущим значениям, а не только к последним. Это означает, что теперь мы получаем список значений, а не только один, поэтому тип гистоморфизма:

-- We could use the type NatF (NonEmptyList a) here.
-- But because NatF is Maybe, NatF (NonEmptyList a) is equal to [a].
-- Using just [a] is a lot simpler
histo :: ([a] -> a)
      -> Nat -> a
histo f = head . go where
  -- go :: Nat -> [a]  -- This signature would need ScopedTVs
  go Z = [f []]
  go (S x) = let subvalues = go x in f subvalues : subvalues

Теперь мы можем определить fibN следующим образом:

-- Example: calculate the n-th fibonacci number
fibN :: Nat -> Integer
fibN = histo $ \x -> case x of
 (x:y:_) -> x + y
 _       -> 1

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

То, что я не показал в приведенном выше примере, заключается в том, что cata и histo могут быть реализованы очень широко, если вы определяете свой тип как фиксированную точку функтора. Наш тип Nat - это только фиксированная точка Functor NatF.

Если вы определяете histo общим способом, вам также нужно придумать такой тип, как NonEmptyList в нашем примере, но для любого функтора. Этот тип точно Cofree f, где f - функтор, на который вы взяли фиксированную точку. Вы можете видеть, что это работает для нашего примера: NonEmptyList - это просто Cofree Maybe. Вот как вы попадаете в общий тип histo:

histo :: Functor f 
      => (f (Cofree f a) -> a)
      -> Fix f  -- ^ This is the fixed point of f
      -> a

Вы можете думать о f (Cofree f a) как о стеке, где с каждым "слоем" вы можете видеть менее сложную структуру. В верхней части стека каждый непосредственный подтип складывается. Затем, если вы переходите на один уровень глубже, непосредственный субтерм больше не сворачивается, но суб-подтермы все уже свернуты (или оценены, что может иметь смысл сказать в случае АСТ). Таким образом, вы можете в основном увидеть "последовательность сокращений", которая была применена (= история).

Ответ 2

Мы можем думать о нем как о континууме обобщения от cata до histo до dyna. В терминологии recursion-schemes:

Foldable t => (Base t a -> a)                                  -> (t -> a) -- (1)
Foldable t => (Base t (Cofree (Base t) a) -> a)                -> (t -> a) -- (2)
Functor  f => (f      (Cofree f        a) -> a) ->  (t -> f t) -> (t -> a) -- (3)

где (1) cata, (2) - histo, а (3) - dyna. Обзор этого обобщения на высоком уровне состоит в том, что histo улучшает cata, поддерживая историю всех частичных "правильных складок", а dyna улучшает histo, позволяя работать с любым типом t, пока мы можем сделайте для нее f -коалгебру, а не только те Foldable (имеющие универсальные Base t -коалгебры как Foldable, свидетельствующие о том, что типы данных являются окончательными коалгебрами).

Мы можем почти прочитать их свойства, просто посмотрев, что нужно, чтобы выполнить их типы.

Например, классическое использование cata заключается в определении foldr

data instance Prim [a] x = Nil | Cons a x
type instance Base [a] = Prim [a]

instance Foldable [a] where
  project []     = Nil
  project (a:as) = Cons a as

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr cons nil = cata $ \case
  Nil      -> nil
  Cons a b -> cons a b

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

Как histo обобщает cata, мы должны быть в состоянии сделать то же самое с ним. Здесь a histo -based foldr

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr cons nil = histo $ \case
  Nil             -> nil
  Cons a (b :< _) -> cons a b

мы видим, что у нас уже нет немедленного результата предыдущей складки, но вместо этого нужно найти в первом слое Cofree, чтобы найти его. Но Cofree - это поток и содержит потенциально бесконечно много "предыдущих значений свертывания", и мы можем так глубоко погрузиться в него, как нам нравится. Это то, что дает histo его "историческую" власть. Например, мы можем написать довольно прямой tail с помощью histo, который сложнее сделать только с cata:

tail :: [a] -> Maybe [a]
tail = histo $ \case
  Nil             -> Nothing -- empty list
  Cons _ (b :< x) -> case x of
    Nil       -> Just [] -- length 1 list
    Cons a _ -> fmap (a:) b

Стиль немного косвенный, но по существу, потому что мы можем оглянуться назад на два последних шага, мы можем реагировать на списки длины-1 по-разному, чем списки длин-0 или длины - n.

Чтобы сделать последний шаг для обобщения histo на dyna, мы просто заменим естественную проекцию любой коалгеброй. Таким образом, мы могли бы легко реализовать histo в терминах dyna

histo phi = dyna phi project -- project is from the Foldable class

Итак, теперь мы можем применять складки histo к любому типу, который можно даже частично рассматривать как список (ну, пока мы держимся с примером выполнения и используем Prim [a] как Functor, f).

(Теоретически существует ограничение, что эта коалгебра в конечном итоге останавливается, например, мы не можем рассматривать бесконечные потоки, но это больше связано с теорией и оптимизацией, чем с использованием. При использовании такая вещь просто должна быть ленивой и маленькой достаточно для завершения.)

(Это отражает идею представления исходных алгебр по их способности project :: t -> Base t t. Если бы это был действительно полный индуктивный тип, вы могли бы проектировать столько раз, прежде чем достигнуть конца.)

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

data NEL  a   = Some  a | More  a (NEL a)
data NELf a x = Somef a | Moref a x deriving Functor

и создайте коалгебру на натуральных числах, называемых natural, которые соответствующим образом развернуты, обратный отсчет NEL

natural :: Int -> NELf Int Int
natural 0 = Somef 0
natural n = Moref n (n-1)

то мы применяем histo -стильный склад к NELf -view натурального числа для создания n -того каталонского номера.

-- here a quick implementation of `dyna` using `recursion-schemes`

zcata
  :: (Comonad w, Functor f) =>
     (a -> f a) -> (f (w (w c)) -> w b) -> (b -> c) -> a -> c
zcata z k g = g . extract . c where
  c = k . fmap (duplicate . fmap g . c) . z

dyna :: Functor f => (f (Cofree f c) -> c) -> (a -> f a) -> a -> c
dyna phi z = zcata z distHisto phi

takeC :: Int -> Cofree (NELf a) a -> [a]
takeC 0 _                 = []
takeC n (a :< Somef v)    = [a]
takeC n (a :< Moref v as) = a : takeC (n-1) as

catalan :: Int -> Int
catalan = dyna phi natural where
  phi :: NELf Int (Cofree (NELf Int) Int) -> Int
  phi (Somef 0) = 1
  phi (Moref n table) = sum (zipWith (*) xs (reverse xs))
    where xs = takeC n table