以与 Free Monad 兼容的方式定义 Free Bind

Question

所以我们有了免费的 monad：（编码可能不同，但它们都是一样的）

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

instance Functor f => Monad (Free f) where
    pure = Pure
    Pure   x >>= f = f x
    Impure x >>= f = Impure ((>>= f) <$> x)

liftFree :: Functor f => f a -> Free f a
liftFree x = Impure (Pure <$> x)

runFree :: Monad g => (forall x. f x -> g x) -> Free f a -> g a
runFree _ (Pure   x) = pure x
runFree f (Impure x) = join (runFree f <$> f x)

使得runFree形成一个单子同态，这是自由单子的定义属性。

runFree f (pure x) = pure x
runFree f (liftFree x >>= liftFree . g) = f x >>= (f . g)
-- + some other associativity requirements

我们也可以做一个类似于（我认为是）free Bind from semigroupoids 的构造，它是一个只有 bind >>-:

的函子

data Free1 f a = Done (f a)
               | More (f (Free1 f a))

instance Functor f => Bind (Free f) where
    Done x >>- f = More (f <$> x)
    More x >>- f = More ((>>- f) <$> x)

liftFree1 :: f a -> Free1 f a
liftFree1 = Done

runFree1 :: Bind g => (forall x. f x -> g x) -> Free1 f a -> g a
runFree1 f (Done x) = f x
runFree1 f (More x) = f x >>- runFree1 f

我们得到了合适的绑定同态：

使得runFree1形成绑定同态，即定义属性:

runFree1 f (liftFree1 x >>- liftFree1 . g) = f x >>- (f . g)
-- + some associativity laws

现在，这两种类型都很棒。我们可以将Free1转换为Free，这是有道理的：

toFree :: Free1 f a -> Free f a
toFree (Done x) = Impure (Pure   <$> x)
toFree (More x) = Impure (toFree <$> x)

但向后转换比较棘手。要从 Free 变为 Free1，我们必须处理两种情况：

Free是纯的，所以不能用Free1表示。
Free是不纯的，所以可以用Free1表示。

这两种情况可以静态处理是有道理的，因为我们可以只匹配 Pure 或 Impure.

所以合理的类型签名可能是：

fromFree :: Functor f => Free f a -> Either a (Free1 f a)

但是我在写这篇文章时遇到了问题。

fromFree :: Free f a -> Either a (Free1 f a)
fromFree (Pure   x) = Left x   -- easy
fromFree (Impure x) = Right ?? -- a bit harder

看起来主要的问题是我们需要决定是否在没有 "running" f 的情况下使用 Done 或 More 构造函数。我们需要一个：

f (Free f a) -> Free1 f a

如果你不能 "get out"，这听起来对仿函数来说可能很麻烦，比如 IO。

所以，这听起来不可能，除非我遗漏了什么。

我试过另一种编码：

data Free1 f a = Free1 (f (Free f a))

这个做让我们定义 fromFree，它借鉴了 NonEmpty 结构 (data NonEmpty a = a :| [a])。在定义 "free Apply" 时，我能够使用这种方法，这很好。这确实让我们可以编写 toFree、fromFree、liftFree1 和一个 Bind 实例。但是，我似乎不能写 runFree1:

runFree1 :: Bind g => (forall x. f x -> g x) -> f (Free f a) -> g a

只要我做任何事情，我似乎都需要 return :: a -> g a，但我们没有为所有 Bind g（我找到了一个可能的类型检查版本，但它执行效果twice and so 不是正确的绑定同态)

因此，虽然此方法为我们提供了 fromFree，但我似乎无法找到编写 runFree1 的方法，这正是赋予它 "free Bind" 功能的方法。

在这两种方法中，我们：

有一个真正的免费 Bind 和 runFree1，但它与 Free 不兼容，因为你不能 "match" 一个 Free一个Free1，或者一个纯值。
有一个与 Free 兼容的类型（可能是 "nonempty Free"），但实际上不是免费的 Bind（不是 runFree1），并且打败了整个目的。

由此我可以得出以下两个结论之一：

有一些方法可以制作与 Free 兼容的免费绑定 Free1，但我还没有弄明白
从根本上说，我们无法获得与 Free 兼容的免费 Bind。这似乎与我的直觉相矛盾（我们总是可以立即确定 Free 是纯的还是不纯的，因此我们也应该能够立即区分纯的（零效应）或 Free1），但也许有是我错过的更深层原因吗？

以下哪种情况？如果#1，方法是什么，如果#2，更深层次的原因是什么？ :)

提前致谢！

编辑为了打消我是否在使用 "true Free Bind" 的不确定性，我开始寻找一个真正的自由绑定的定义：

newtype Free1 f a = Free1 { runFree1 :: forall g. Bind g => (forall x. f x -> g x) -> g a }

而且我似乎也无法为此写 fromFree。最后我好像需要一个g (Either a (Free1 a)) -> g a.

如果我不能为此写fromFree，那么按理说我不能为自由绑定的任何实现写fromFree，因为所有实现都与此同构一.

有没有办法为这个写 fromFree，甚至？还是这一切都不可能:'( Alt/Plus 和 Apply/Applicative.

一切都很好

Answer 1

虽然 Free f a 是具有“f-节点”和 a-叶子的树的类型，但 "free Bind-structure" Free1 f a 是这样的树有一个额外的限制：f-node 的子节点要么都是叶子，要么都是 f-nodes。因此，如果我们考虑二叉树：

data Bin x = Bin x x

则Free Bin a包含以下树形，但Free1 Bin a不包含：

Impure (Bin
  (Pure a)
  (Impure (Bin (Pure a) (Pure a))))

因为根节点有一个叶节点和一个 Bin 节点作为子节点，而 Free1 Bin a 应该有两个叶节点或两个 Bin 节点。这样的模式可能发生在 Free 树的深处，因此即使只有 Functor f 约束也无法进行部分转换 Free f a -> Maybe (Free1 f a)。 Traversable f 假设遍历是有限的约束使得这种转换成为可能，但当然对于大树来说仍然不实用，因为在产生任何输出之前必须完全遍历它们。

请注意，由于 Free1 的上述特征，Free 的另一个定义实际上并不等价：

data Free1 f a = Free1 (f (Free f a))  -- Not a free Bind

以与 Free Monad 兼容的方式定义 Free Bind

Defining Free Bind in a way that is compatible with the Free Monad

haskell

category-theory

free-monad