以与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形成了monad同态，这是自由monad的定义属性。

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

我们还可以进行类似于（我相信是）Bind半组群自由的构造，半自由群是仅具有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)

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

1. 的Free是纯的，所以不能在被表示Free1。
2. 的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

看来主要问题在于我们需要确定是否使用Done或More构造函数而无需“运行” f。我们需要一个：

f (Free f a) -> Free1 f a

如果您无法“离开”，这听起来似乎对函子很麻烦IO。

因此，这听起来是不可能的，除非我缺少任何东西。

我尝试了另一种编码：

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

这确实使我们能够定义fromFree，并且它是从NonEmpty构造（data NonEmpty a = a :| [a]）借来的。而且我在定义“免费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（我发现了一个可能的类型进行类型检查，但是它执行了两次效果，因此不是正确的绑定同构）

因此，虽然这种方法给了我们fromFree，但我似乎找不到一种写方法runFree1，这正是赋予它“免费Bind”功能的原因。

在这两种方法中，我们要么：

1. 实际Bind拥有runFree1，但与Free不能兼容，因为您不能将“匹配” Free到Free1或纯值中。
2. 具有与兼容的类型Free（可能是“非空Free”），但实际上不是自由的类型Bind（否runFree1），并且破坏了整个目的。

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

1. 有一些方法可以制作Free1与兼容的免费Bind Free，但我还无法弄清楚
2. 从根本上讲，我们不能拥有Bind与兼容的免费软件Free。这似乎与我的直觉相矛盾（我们总是可以立即确定a Free是纯的还是不纯的，因此我们也应该能够立即区分出纯（零影响）还是Free1），但是也许有更深层次的原因使我错过了？

这是哪种情况？如果是＃1，那是方法，如果是＃2，更深层的原因是什么？:)

先感谢您！

---

编辑为了消除我是否在使用“真正的免费绑定”的不确定性，我开始查看定义上真正是免费的绑定：

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

虽然是具有“ -nodes”和-leavesFree f a的树的类型，但“自由绑定结构”是具有附加限制的此类树的类型：-node 的子节点要么是所有叶子，要么是所有-nodes。因此，如果我们考虑二叉树：faFree1 f aff

data Bin x = Bin x x

然后Free Bin a包含以下树形状，但Free1 Bin a不包含：

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

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

请注意，由于 的上述特征Free1，根据 的其他定义实际上Free并不等效：

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