haskell - 授予可遍历的F代数，是否有可能在适用代数上具有同构关系？

我有这个F代数(introduced in a previous question)，并且我想在其上投一个有效的代数。通过绝望的尝试，我设法将一元论的同构作用组合在一起。我想知道它是否可以推广到一个应用程序，如果不能推广，为什么呢。

这就是我定义Traversable的方式:

instance Traversable Expr where
    traverse f (Branch xs) = fmap Branch $ traverse f xs
    traverse f (Leaf   i ) = pure $ Leaf i

这是单子(monad)变态:

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和according to a paper on applicative do-notation，在这种情况下，我们无法将Sugar分解为Applicative。似乎没有办法解决这个问题。我们需要一个monad从嵌套深处浮起。

是真的吗我是否可以安全地得出结论，只有扁平结构可以单独折叠才能产生效果？

最佳答案

你可以再说一遍!毕竟，“扁平化嵌套结构”正是使monad成为monad的原因，而不是Applicative只能组合相邻结构的Monad。比较两个抽象的签名(的一个版本):

class Functor f => Applicative f where
    pure :: a -> f a
    (<.>) :: f a -> f b -> f (a, b)

class Applicative m => Monad m where
    join :: m (m a) -> m a

Applicative添加到m的功能是能够将嵌套的m展平为一个[]。这就是join的concat是Applicative的原因。 f仅允许您将迄今为止不相关的Free粉碎在一起。

免费的monad的f构造函数包含一个完整的Free f，而不是偶然的巧合，而免费的应用程序的Ap构造函数仅包含一个Ap f并非偶然。

data Free f a = Return a | Free (f (Free f a))
data Ap f a where
    Pure :: a -> Ap f a
    Cons :: f a -> Ap f b -> Ap f (a, b)

希望这使您对为什么不应该使用Applicative折叠树感到直觉。

让我们打一点网球，看看它如何震动。我们要写

cataA :: (Traversable f, Applicative m) => (f a -> m a) -> Fix f -> m a
cataA f (Fix xs) = _

我们有xs :: f (Fix f)和Traversable的f。我的第一个本能是traverse f折叠包含的子树:

cataA f (Fix xs) = _ $ traverse (cataA f) xs

现在该洞的目标类型为m (f a) -> m a。由于存在一个f :: f a -> m a，让我们尝试进入m下以转换所包含的f:

cataA f (Fix xs) = _ $ fmap f $ traverse (cataA f) xs

现在，我们有一个目标类型m (m a) -> m a，即join。因此，您毕竟需要Monad。

关于haskell - 授予可遍历的F代数，是否有可能在适用代数上具有同构关系？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48489398/