下面是一些简单的列表 F 代数。他们与 cata
合作功能从
recursion-schemes图书馆。
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 可以将这两个代数应用于列表的每个项目。
下一个是 filter 和 double:
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 代数的确切规则是什么?
最佳答案
“结构保持代数”可以形式化为自然变换(可以在不同的仿函数之间)。
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)
根据 catamorphism 的定义,
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)
cata
的定义作为 Haskell 函数,cata afb = afb . fmap (cata afb) . project
,并用 project . inList = id
简化; 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)
这是我能想到的最简单的一个。
关于haskell - 在 catamorphism 中组合 f-代数的规则是什么,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48843987/