gpt4 book ai didi

haskell - 授予可遍历的 F 代数,是否可能对应用代数进行变形?

转载 作者:行者123 更新时间:2023-12-04 18:57:37 29 4
gpt4 key购买 nike

我有这个 F-代数 (introduced in a previous question),我想在它上面施放一个有效的代数。通过绝望的试验,我设法组合了一个有效的 monadic catamorphism。我想知道它是否可以推广到应用程序,如果不能,为什么。

这就是我定义的方式 Traversable :

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

这是 monadic catamorphism:
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 ,在这种情况下,我们不能对 Applicative 进行脱糖。似乎没有办法解决这个问题;我们需要一个 monad 从嵌套的深处浮出水面。

这是真的吗?我可以安全地得出结论,只有平面结构可以单独使用应用效果折叠吗?

最佳答案

Can I safely conclude that only flat structures can be folded with applicative effects alone?



你可以再说一遍!毕竟,“扁平化嵌套结构”正是使 monad 成为 monad 的原因,而不是 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是能够展平嵌套 m s 合一 m .这就是为什么 []joinconcat . Applicative只让你粉碎至今无关 f s。

免费 monad 的 Free 绝非巧合构造函数包含一个整体 fFree f s,而免费应用程序的 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)和一个 Traversablef .我在这里的第一直觉是 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毕竟。

关于haskell - 授予可遍历的 F 代数,是否可能对应用代数进行变形?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48489398/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com