理解 bind 在 free monad 中的使用

Question

我正在尝试了解免费 monad 的工作原理。在此期间，我进入了 Free 的 monad 实例，即：

data Free f a = Pure a | Free (f (Free f a))

instance (Functor f) => Monad (Free f) where
  return = Pure
  Pure a >>= k = k a
  Free m >>= k = Free ((>>= k) <$> m)

知道

  -- k :: a -> Free f b
  -- m :: f (Free f a)
  -- fmap :: Functor f => (a -> b) -> f a -> f b
  -- (>>=) :: Free f a -> (a -> Free f b) -> Free f b

我不明白这是怎么回事

Free ((>>= k) <$> m)

首先，>>= k怎么可能呢？ k 是一个函数，而 >>= 的第一个参数不是。就像它绕过第一个参数并将 k 作为第二个参数，留下 Free f a -> Free f b

谁能帮助我更好地理解这一点？谢谢！

Answer 1

我不知道这个 Free 到底是什么，但是我们都知道

(>>= k) <$> m == fmap (>>= k) m

所以如果m == f sth，那么

fmap (>>= k) m == f ((>>= k) sth) == f (sth >>= k)

所以一切似乎都是类型检查。

正如评论中所建议的那样，您可能唯一想念的是 (.op. y) 将 y 作为第二个参数传递给 .op.，这与 (.op.) y 不同它作为第一个参数。

Answer 2

我无法在签名方面为您提供帮助，但如果我在字里行间没看错的话，您想了解这些签名以便了解仿函数的自由 monad 的绑定应该做什么。我可以解释一下，希望这也能帮助您理解您明确询问的签名。

函子 f 的自由单子是树形式的函子，其中值存储在纯 a 叶子中，所有节点的形状都是 f。所有分支的长度相同，由到达 Pure a 之前完成的 Free (f(Free f a)) 的迭代次数决定。例如，对函子 f = (a, a) 和 Free 的十次迭代的自由单子将是一个（完美的）十层二叉树，并且 2^10 = 1024 a:s 存储在 Pure a 叶子中.当 f 将一个类型转换为该类型的一对时，Free (f (Free f a)) 的每次迭代都将一个“具有长度为 n 的分支的对函子的自由单子”-type 转换为两个这样的类型的一对，使其成为“具有长度为 n+1 的分支的对函子的自由单子”类型。

如您所知，bind 接受一个类型为 a 的 monad 和一个函数从 a 到一个类型为 b 的 monad，并产生一个类型为 b 的 monad。自由 monad 的绑定采用 a:s 的树，其中分支的长度为 n 和从 a 到 b 的树的函数，其中分支的长度为 m 并生成 b:s 的树，其中分支具有长度 n+m，只需将函数应用于原始树中每个 Pure a 叶子中的 a 并将其替换为生成的 b 树。当你以前在下降 n 个节点后找到一个 Pure a 时，你会发现另一个 m 级节点导致一堆 b:s。因此新的分支长度为 n + m.

作为旁注，因为您正在尝试理解自由单子：在范畴论和附加词中，自由通常意味着“以所有允许的方式从输入中挤出信息并存储它”。其他 monad 的绑定使用平面图折叠其输出中的信息。例如，列表 monad 的绑定将忘记其函数从输入列表中生成的列表列表的单个长度信息。函子 f 的自由 monad 永远不会折叠任何东西，它们只会增长以完全容纳所有输入它们的东西。 list functor 的 free monad 只是将列表的列表包装在另一层 Free ([(Free [] a)]) 中。这将我们引向另一个与术语“自由”相关的属性：有一种方法可以从仿函数的自由单子到仿函数的任何其他单子。不过，我不完全确定在这种情况下这到底意味着什么......

理解 bind 在 free monad 中的使用

Understanding the use of bind in free monad

syntax

monads

haskell

operators

free-monad