5

我有这个 F 代数（在上一个问题中介绍过），我想在它上面加上一个有效的代数。通过绝望的试验，我设法拼凑出一个有效的一元变态。我想知道它是否可以推广到应用程序，如果不能，为什么。

这就是我定义的方式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并且根据一篇关于 applicative do-notation 的论文，在这种情况下，我们不能对 Applicative 脱糖。似乎没有办法解决这个问题；我们需要一个单子从嵌套的深处浮起来。

这是真的吗？我可以安全地得出结论，只有扁平结构可以折叠，仅具有应用效果吗？

4

1 回答 1

5

我可以安全地得出结论，只有扁平结构可以折叠，仅具有应用效果吗？

你可以再说一遍！毕竟，“扁平化嵌套结构”正是使单子成为单子的原因，而不是Applicative只能组合相邻的结构。比较两个抽象的签名（一个版本）：

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

Monad增加的是将嵌套Applicative的 s扁平化为一个的能力。这就是为什么's是。只让你把迄今为止无关的s粉碎在一起。 mm[]joinconcatApplicativef

free monad 的Free构造函数包含一个f完整的Free fs 并非巧合，而 free applicative 的Ap构造函数只包含一个s 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)一个Traversablefor f。我的第一反应是traverse折叠f包含的子树：

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

该洞现在有一个目标类型m (f a) -> m a。既然有f :: f a -> m a敲门声，让我们尝试在下面m转换包含f的 s：

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

现在我们有一个目标类型m (m a) -> m a，即join。所以你确实需要一个Monad。

于 2018-01-29T01:31:44.977 回答