如何将免费monad转换为仿函数？

Question

该免费结构上Haskell的wiki页面定义一个函数以一个仿函数实例转换成一个自由单子:

inj :: Functor f => f a -> Free f a
inj fa = Roll $ fmap Return fa

然后,说inj [1,2,3],有类型(Num t) => Free [] t.如何定义一个函数返回像inj [1,2,3]回[1,2,3]？

Answer 1

要注意的第一件事是inj将品牌Free变成几乎是单变换器的东西.

我将使用Control.Monad.Free,从我的hackage 免费软件包中,避免重复此处的所有内容.这意味着相对于wiki上的版本,Roll变为Free并在下面的代码中Return命名Pure.

import Control.Monad
import Control.Monad.Free -- from 'free'

instance MonadTrans Free where
    lift = Free . liftM Pure

然而,你无法向任意方向走向另一个方向Functor.但是,如果你有一个Monadon 实例m,你可以通过展平Free m到底层monad的单层来撤消提升m!

retract :: Monad f => Free f a -> f a  
retract (Pure a) = return a
retract (Free as) = as >>= retract

选择这个名字,因为这是一个退缩的lift.所谓的因为

retract . lift = id 

如图所示

retract (lift as) =                        -- by definition of lift
retract (Free (liftM Pure as)) =           -- by definition of retract
liftM Pure as >>= retract =                -- by definition of liftM
as >>= \a -> return (Pure a) >>= retract = -- first monad law
as >>= \a -> retract (Pure a)              -- by definition of retract
as >>= \a -> return a =                    -- eta reduction
as >>= return                              -- second monad law
as

所以功能retract撤消了工作lift.

从fmap=开始liftM,这也适用inj.

请注意,lift . retract是不是 id.目前根本没有足够的空间把一切都在干预的类型-使用单子都摔破平-但lift . retract . lift . retract = lift . retract成立是因为lift . retract . lift . retract = lift . id . retract = lift . retract,这样lift . retract是幂等.

这个'提升'的问题在于'提升'不是单子同态,而是仅仅是单子同态"向上缩回",因此这推动了对提升计算的用户保留单子变换器定律的负担,因此将inj作为单独的函数名称保留是有意义的.

我现在实际上要加入retract免费套餐.我最近需要它来写一篇我正在写的文章.

Answer 2

正如@sclv所说,在一般情况下,没有办法直接将仿函数的免费monad转换回仿函数.为什么不？

如果你回想起你所链接的"自由结构"页面,它首先讨论免费幺半群,然后再扩展相同的概念来讨论monad.一个类型的自由幺半群是一个列表; 在这种情况下,等效的"转换回"函数将使用类型[a]将具有类型的自由monoid 转换为单个元素a.这显然不可行于两种方式:如果列表为空,则不能返回任何内容; 如果列表有多个元素,则必须丢弃除一个之外的所有元素.

免费monad的构造是类似的,并提出了类似的问题.一个免费的monad由functor组合定义,除了类型构造函数之外,它就像常规函数组合一样.我们不能直接在Haskell中编写函子组合,但就像f . g手段一样\x -> f (g x),我们可以嵌套类型构造函数的应用程序.例如,Maybe与自身合成给出类似的类型Maybe (Maybe a).

换句话说,在普通仿函数描述某种参数化结构的情况下,该仿函数的自由monad描述了嵌套在任意深度内的结构.

因此,如果我们看一下Free [] Int,它可以是单个Int,Ints列表,列表Ints等等.

因此,就像我们只能将一个免费的monoid(列表)直接转换为单个项目(如果列表只有一个项目长),如果嵌套只是一层深度,我们只能将一个免费的monad直接转换为底层的functor .

如果你对从一个免费monad中取出东西的一般方法感兴趣,你需要更进一步 - 某种类似递归折叠的操作来折叠结构.

在列表的自由monad的特定情况下,有一个明显的方法 - 通过剥离Roll和Return构造函数以及连接列表来递归地展平结构.这也可能是启发思考,为什么这种方法能在这种情况下,它如何与清单的结构.