我有一个 F 代数(在先前的问题中介绍),我想将一个效应代数施加到它上面。通过不懈的尝试,我设法组合出了一个可行的单子范畴。我想知道它是否可以推广为一个应用函子,如果不能,为什么。
这是我如何定义 Traversable:
不幸的是,这里的
这是真的吗?我可以安全地得出结论,只有扁平结构才能仅使用applicative效果进行折叠吗?
这是我如何定义 Traversable:
instance Traversable Expr where
traverse f (Branch xs) = fmap Branch $ traverse f xs
traverse f (Leaf i ) = pure $ Leaf i
这是单子范畴折叠:
type AlgebraM a f b = a b -> f b
cataM :: (Monad f, Traversable a) => AlgebraM a f b -> Fix a -> f b
cataM f x = f =<< (traverse (cataM f) . unFix $ x)
这是它的工作原理:
λ let printAndReturn x = print x >> pure x
λ cataM (printAndReturn . evalSum) $ branch [branch [leaf 1, leaf 2], leaf 3]
1
2
3
3
6
6
我现在的想法是,我可以像这样重写:
cataA :: (Applicative f, Traversable a) => AlgebraM a f b -> Fix a -> f b
cataA f x = do
subtree <- traverse (cataA f) . unFix $ x
value <- f subtree
return value
不幸的是,这里的
value
取决于subtree
,根据一篇关于应用do-notation的论文所述,在这种情况下,我们无法将其展开为Applicative。看起来没有绕过这个问题的方法;我们需要一个单子从嵌套的深处浮现出来。这是真的吗?我可以安全地得出结论,只有扁平结构才能仅使用applicative效果进行折叠吗?
cataA
可以被实现...那么就会出现矛盾”)。 - Benjamin Hodgson