Каковы правила составления f-алгебр в катаморфизме

Question

Вот несколько простых F-алгебр для списков. Они работают с cata функция из библиотеки рекурсивных схем.

import Data.Functor.Foldable

algFilterSmall :: ListF Int [Int] -> [Int]
algFilterSmall Nil = [] 
algFilterSmall (Cons x xs) = if x >= 10 then (x:xs) else xs

algFilterBig :: ListF Int [Int] -> [Int]
algFilterBig Nil = [] 
algFilterBig (Cons x xs) = if x < 100 then (x:xs) else xs

algDouble :: ListF Int [Int] -> [Int]
algDouble Nil = [] 
algDouble (Cons x xs) = 2*x : xs

algTripple :: ListF Int [Int] -> [Int]
algTripple Nil = [] 
algTripple (Cons x xs) = 3*x : xs

Теперь я сочиняю их:

doubleAndTripple :: [Int] -> [Int]
doubleAndTripple = cata $ algTripple . project . algDouble
-- >>> doubleAndTripple [200,300,20,30,2,3]
-- [1200,1800,120,180,12,18]

doubleAndTriple работает как положено. Обе алгебры сохраняют структуру, они не меняют длину списка, поэтому cata может применять обе алгебры к каждому элементу списка.

Следующий - фильтр и двойник:

filterAndDouble :: [Int] -> [Int] 
filterAndDouble = cata $ algDouble . project . algFilterBig
-- >>> filterAndDouble [200,300,20,30,2,3]
-- [160,60,4,6]

Это не работает должным образом. Я предполагаю, что это потому, что algFilterBig не сохраняет структуру.

Теперь последний пример:

filterBoth :: [Int] -> [Int] 
filterBoth = cata $ algFilterSmall . project . algFilterBig 
-- >>> filterBoth [200,300,20,30,2,3]
-- [20,30]

Здесь обе алгебры не сохраняют структуру, но этот пример работает.

Каковы точные правила составления f-алгебр?

Answer 1

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

inList :: ListF a [a] -> [a]
inList Nil = []
inList (Cons a as) = a : as

ntDouble, ntTriple :: forall a. ListF Int a -> ListF Int a
algDouble = inList . ntDouble
algTriple = inList . ntTriple

Тогда для любой алгебры f и естественная трансформация n,

cata (f . inList . n) = cata f . cata n

doubleAndTriple Пример является примером этого для f = algTriple а также n = ntDouble,

Это нелегко обобщить на большие классы алгебр.

Я думаю, что случай фильтра легче увидеть без категорий, как следствие того, что filter является полугрупповым гомоморфизмом: filter p . filter q = filter (liftA2 (&&) p q),

---

Я искал общее, но достаточное условие для "закона распределения" на алгеброобразных алгебрах. Немного сокращать afs = algFilterSmall, afb = algFilterBig, Мы рассуждаем задом наперед, чтобы найти достаточное условие для:

cata (afs . project . afb) = cata afs . cata afb  -- Equation (0)

По определению катаморфизма, z = cata (afs . project . afb) является единственным решением этого уравнения (замаскированная коммутативная диаграмма):

z . inList = afs . project . afb . fmap z

Замена z с RHS предыдущего уравнения:

cata afs . cata afb . inList = afs . project . afb . fmap (cata afs . cata afb)
-- (1), equivalent to (0)

• На LHS мы применяем определение cata как функция Haskell, cata afb = afb . fmap (cata afb) . projectи упростить с project . inList = id;

• на RHS, мы применяем закон функтора fmap (f . g) = fmap f . fmap g,

Это дает:

cata afs . afb . fmap (cata afb) = afs . project . afb . fmap (cata afs) . fmap (cata afb)
-- (2), equivalent to (1)

Мы "упрощаем" последний фактор fmap (cata afb) (помните, что мы рассуждаем задом наперед)

cata afs . afb = afs . project . afb . fmap (cata afs)  -- (3), implies (2)

Это самый простой, который я мог придумать.