Гистоморфизмы, зигоморфизмы и футуморфизмы, специализированные для списков

В итоге я понял это. Смотрите видео и слайды выступления, которое я дал:

Оригинальный вопрос:

В моих попытках понять общие схемы рекурсии (т. Fix Использующие Fix) я обнаружил, что полезно писать версии различных схем только для списков. Это значительно упрощает понимание реальных схем (без дополнительных затрат на Fix).

Тем не менее, я еще не понял, как определить список только версии zygo и futu.

Вот мои специальные определения:

cataL :: (a ->        b -> b) -> b -> [a] -> b
cataL f b (a : as) = f a    (cataL f b as)
cataL _ b []       = b

paraL :: (a -> [a] -> b -> b) -> b -> [a] -> b
paraL f b (a : as) = f a as (paraL f b as)
paraL _ b []       = b

-- TODO: histo

-- DONE: zygo (see below)

anaL  :: (b ->       (a, b))               -> b -> [a]
anaL  f b = let (a, b') = f b in a : anaL f b'

anaL' :: (b -> Maybe (a, b))               -> b -> [a]
anaL' f b = case f b of
    Just (a, b') -> a : anaL' f b'
    Nothing      -> []

apoL :: ([b] -> Maybe (a, Either [b] [a])) -> [b] -> [a]
apoL f b = case f b of
    Nothing -> []
    Just (x, Left c)  -> x : apoL f c
    Just (x, Right e) -> x : e

-- DONE: futu (see below)

hyloL  :: (a -> c -> c) -> c -> (b -> Maybe (a, b)) -> b -> c
hyloL f z g = cataL f z . anaL' g

hyloL' :: (a -> c -> c) -> c -> (c -> Maybe (a, c))      -> c
hyloL' f z g = case g z of
    Nothing     -> z
    Just (x,z') -> f x (hyloL' f z' g)

Как вы определяете histo, zygo и futu для списков?

Ответ 1

Зигоморфизм - это матетизированное название с высоким фалутином, которое мы даем складкам, построенным из двух полу-взаимно рекурсивных функций. Я приведу пример.

Представьте себе функцию pm :: [Int] → Int (для плюс-минус), которая перемежает + и - попеременно через список чисел, такой что pm [v,w,x,y,z] = v - (w + (x - (y + z))). Вы можете написать это, используя примитивную рекурсию:

lengthEven :: [a] -> Bool
lengthEven = even . length

pm0 [] = 0
pm0 (x:xs) = if lengthEven xs
             then x - pm0 xs
             else x + pm0 xs

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

paraL :: (a -> [a] -> b -> b) -> b -> [a] -> b
paraL f z [] = z
paraL f z (x:xs) = f x xs (paraL f z xs)

pm1 = paraL (\x xs acc -> if lengthEven xs then x - acc else x + acc) 0

Но это неэффективно. lengthEven обходит весь список на каждой итерации параморфизма, что приводит к алгоритму O (n ²).

Мы можем добиться прогресса, отметив, что и lengthEven и para могут быть выражены как катаморфизм с помощью foldr...

cataL = foldr

lengthEven' = cataL (\_ p -> not p) True
paraL' f z = snd . cataL (\x (xs, acc) -> (x:xs, f x xs acc)) ([], z)

... что говорит о том, что мы можем объединить две операции в один проход по списку.

pm2 = snd . cataL (\x (isEven, total) -> (not isEven, if isEven
                                                      then x - total
                                                      else x + total)) (True, 0)

У нас был фолд, который зависел от результата другого фолда, и мы смогли объединить их в один обход списка. Зигоморфизм захватывает именно этот паттерн.

zygoL :: (a -> b -> b) ->  -- a folding function
         (a -> b -> c -> c) ->  -- a folding function which depends on the result of the other fold
         b -> c ->  -- zeroes for the two folds
         [a] -> c
zygoL f g z e = snd . cataL (\x (p, q) -> (f x p, g x p q)) (z, e)

На каждой итерации сгиба f видит свой ответ из последней итерации как в катаморфизме, но g видит ответы обеих функций. g перепутывает себя с f.

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

pm3 = zygoL (\_ p -> not p) (\x isEven total -> if isEven
                                                then x - total
                                                else x + total) True 0

Это классический стиль функционального программирования. У нас есть функция более высокого порядка, выполняющая тяжелую работу по использованию списка; все, что нам нужно было сделать, это включить логику для агрегирования результатов. Конструкция явно заканчивается (вам нужно только доказать завершение для foldr), и она более эффективна, чем оригинальная рукописная версия для загрузки.

Кроме того, @AlexR указывает в комментариях, что у зигоморфизма есть старшая сестра, называемая мутуморфизмом, который отражает взаимную рекурсию во всей своей красе. mutu обобщает zygo тем, что обеим функциям свертывания разрешается проверять другой результат предыдущей итерации.
mutuL :: (a -> b -> c -> b) ->
         (a -> b -> c -> c) ->
         b -> c ->
         [a] -> c
mutuL f g z e = snd . cataL (\x (p, q) -> (f x p q, g x p q)) (z, e)
Вы восстанавливаете zygo из mutu просто игнорируя дополнительный аргумент. zygoL f = mutuL (\xpq → fxp)

Конечно, все эти шаблоны свертывания обобщаются от списков до фиксированной точки произвольного функтора:

newtype Fix f = Fix { unFix :: f (Fix f) }

cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix

para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a
para f = snd . cata (\x -> (Fix $ fmap fst x, f x))

zygo :: Functor f => (f b -> b) -> (f (b, a) -> a) -> Fix f -> a
zygo f g = snd . cata (\x -> (f $ fmap fst x, g x))

mutu :: Functor f => (f (b, a) -> b) -> (f (b, a) -> a) -> Fix f -> a
mutu f g = snd . cata (\x -> (f x, g x))

Сравните определение zygo с определением zygoL. Также обратите внимание, что zygo Fix = para, и что последние три сгиба могут быть реализованы в терминах cata. В фолдологии все связано со всем остальным.

Вы можете восстановить версию списка из обобщенной версии.

data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)

zygoL' :: (a -> b -> b) -> (a -> b -> c -> c) -> b -> c -> List a -> c
zygoL' f g z e = zygo k l
    where k Nil_ = z
          k (Cons_ x y) = f x y
          l Nil_ = e
          l (Cons_ x (y, z)) = g x y z

pm4 = zygoL' (\_ p -> not p) (\x isEven total -> if isEven
                                                 then x - total
                                                 else x + total) True 0

Ответ 2

Поскольку еще никто не ответил за futu, я постараюсь наткнуться на него. Я собираюсь использовать ListF ab = Base [a] = ConsF ab | NilF ListF ab = Base [a] = ConsF ab | NilF

Взяв тип в recursion-schemes: futu :: Unfoldable t => (a → Base t (Free (Base t) a)) → a → t.

Я собираюсь игнорировать ограничение "Не Unfoldable и заменить [b] на t.

(a -> Base [b] (Free (Base [b]) a)) -> a -> [b]
(a -> ListF b (Free (ListF b) a)) -> a -> [b]

Free (ListF b) a) представляет собой список, возможно, с a -typed отверстием на конце. Это означает, что оно изоморфно ([b], Maybe a). Итак, теперь мы имеем:

(a -> ListF b ([b], Maybe a)) -> a -> [b]

Исключая последний ListF, замечая, что ListF ab изоморфен Maybe (a, b):

(a -> Maybe (b, ([b], Maybe a))) -> a -> [b]

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

futuL f x = case f x of
  Nothing -> []
  Just (y, (ys, mz)) -> y : (ys ++ fz)
    where fz = case mz of
      Nothing -> []
      Just z -> futuL f z

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

Сначала я думал, что это было эквивалентно

notFutuL :: (a -> ([b], Maybe a)) -> a -> [b]
notFutuL f x = case f x of
  (ys, mx) -> ys ++ case mx of
    Nothing -> []
    Just x' -> notFutuL f x'

И на практике, возможно, так оно и есть, более или менее, но одно существенное отличие состоит в том, что реальное futu гарантирует производительность (то есть, если f всегда возвращается, вы никогда не будете застревать в ожидании следующего элемента списка).

Ответ 3

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

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

Вот как выглядит история повторения списка (ory):

data History a b = Ancient b | Age a b (History a b)

History - это список пар вещей и результатов, с дополнительным результатом в конце, соответствующим [] -thing. Мы сопоставим каждый слой входного списка с его соответствующим результатом.

cataL = foldr

history :: (a -> History a b -> b) -> b -> [a] -> History a b
history f z = cataL (\x h -> Age x (f x h) h) (Ancient z)

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

headH :: History a b -> b
headH (Ancient x) = x
headH (Age _ x _) = x

histoL :: (a -> History a b -> b) -> b -> [a] -> b
histoL f z = headH . history f z

(Бывает, что History a является comonad, но headH (née extract) - это все, что нам нужно define histoL.)

History помещает каждый слой списка ввода с соответствующим результатом. Коэффициент cofree фиксирует шаблон маркировки каждого слоя произвольной структуры.

data Cofree f a = Cofree { headC :: a, tailC :: f (Cofree f a) }

(я придумал History, подключив ListF к Cofree и упростив.)

Сравните это со свободной монадой,

data Free f a = Free (f (Free f a))
              | Return a

Free - тип копроизведения; Cofree - тип продукта. Free слои вверх по лазаньи f s, со значениями a в нижней части лазаньи. Cofree слои вверх по лазаньне со значениями a на каждом слое. Свободные монады - это обобщенные деревья с внешней меткой; cofree comonads - это обобщенные деревья с внутренней меткой.

С Cofree в руке мы можем обобщить из списков на фиксированную точку произвольного функтора,

newtype Fix f = Fix { unFix :: f (Fix f) }

cata :: Functor f => (f b -> b) -> Fix f -> b
cata f = f . fmap (cata f) . unFix

histo :: Functor f => (f (Cofree f b) -> b) -> Fix f -> b
histo f = headC . cata (\x -> Cofree (f x) x)

и еще раз восстановить версию списка.

data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)
type History' a b = Cofree (ListF a) b

histoL' :: (a -> History' a b -> b) -> b -> List a -> b
histoL' f z = histo g
    where g Nil_ = z
          g (Cons_ x h) = f x h

Помимо: histo является двойственным от futu. Посмотрите на их типы.
histo :: Functor f => (f (Cofree f a) -> a) -> (Fix f -> a)
futu  :: Functor f => (a  ->  f (Free f a)) -> (a -> Fix f)
futu есть histo, когда стрелки перевернуты и с заменой Free на Cofree. Гистоморфизмы видят прошлое; футуморфизмы предсказывают будущее. И очень похоже на cata f . ana g можно слить в гемоморфизм, histo f . futu g можно слить в chronomorphism.

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