haskell - 以与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 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

然后我们得到适当的绑定(bind)同态:

这样runFree1形成绑定(bind)同态，这是定义属性:

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

看来主要问题在于我们需要确定是否使用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])借用的。而且我在定义“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我们都没有(我发现了一个可能的类型进行类型检查，但是它执行了两次效果，因此不是正确的绑定(bind)同构)

因此，尽管此方法为我们提供了fromFree，但我似乎找不到找到写runFree1的方法，这正是赋予它“免费Bind”功能的原因。

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

具有实际的免费Bind和runFree1，但是与Free不兼容，因为您无法将Free匹配为Free1或纯值。

具有与Free兼容的类型(可能是“非空Free”)，但实际上不是免费的Bind(没有runFree1)，并且破坏了整个目的。

据此，我可以得出以下两个结论之一:

有一些方法可以制作与Free1兼容的免费绑定(bind)Free，但是

我还无法弄清楚

从根本上讲，我们不能提供与Bind兼容的免费Free。这似乎与我的直觉相矛盾(我们总是可以立即确定Free是纯净的还是不纯净的，因此我们也应该能够立即区分出纯净的(零影响)还是Free1)，但是也许我更想不到一个更深层次的原因出来吗？

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

先感谢您!

编辑为了消除我是否正在使用“真正的免费绑定(bind)”的不确定性，我开始查看定义上真正是免费的绑定(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，那么可以说我不能为任何自由绑定(bind)实现编写fromFree，因为所有实现都与此同构。

有没有办法为此写fromFree？还是全部不可能:'((对于Alt/Plus和Apply/Applicative来说，效果都很好。

Answer 1

Free f a是带有“f -nodes”和a -leaves的树的类型，而“free Bind-structure” Free1 f a是此类树的类型，但有一个额外的限制:f -node的子代要么全部是叶子，要么全部f-节点。因此，如果我们考虑二叉树:

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树的深处发生，因此仅使用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