Profunctors 的自由单子模拟

Question

我们可以定义 data Free f a = Pure a | Free (f (Free f a)) 等 Functor f => Monad (Free f).

如果我们定义 data T f a b = R a | S b | T (f a (T f a b)) 我们有一些类似的 M 所以 Profunctor f => M (T f a)，其中 class Profunctor f where dimap :: (a -> b) -> (c -> d) -> f b c -> f a d?

自从我注意到 Data.Comp.Term.Context and Free are isomorphic about a potential analog for Data.Comp.Param.Term.Context.

以来，我一直在想

Answer 1

所以我想我明白了：M ~ Monad ☺

instance Profunctor f => Functor (T f a) where
    fmap f (In m) = In (dimap id (fmap f) m)
    fmap f (Hole x) = Hole (f x)
    fmap f (Var v) = Var v

instance Profunctor f => Applicative (T f a) where
    pure = Hole
    (<*>) = ap

instance Profunctor f => Monad (T f a) where
    In m >>= f = In ((>>= f) <$> m)
    Hole x >>= f = f x
    Var v >>= _ = Var v

事后看来很明显。

Answer 2

有一个更合适的概念，即从发音者那里获得免费的东西。那我们就可以举一反三了。

由集合 X 生成的自由幺半群 Y 可以被认为是方程 "Y=1+XY" 的解。在 Haskell 表示法中是

data List a = Nil | Cons a (List a)

由函子 F 生成的自由单子 M 可以被认为是方程 "M=1+FM" 的解，其中乘积“FM”是函子的组合。1 只是恒等函子。在 Haskell 表示法中是

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

从profunctor P 中解脱出来的东西应该看起来像"A=1+PA" 的解决方案A。产品 "PA" 是标准 composition of profunctors。 1 是 "identity" profunctor，(->)。所以我们得到

data Free p a b = Pure (a -> b) | forall x.Free (p a x) (Free p x b)

这也是一个profunctor:

instance Profunctor b => Profunctor (Free b) where
    lmap f (Pure g) = Pure (g . f)
    lmap f (Free g h) = Free (lmap f g) h
    rmap f (Pure g) = Pure (f . g)
    rmap f (Free g h) = Free g (rmap f h)

如果 profunctor 很强大，那么免费版也很强大：

instance Strong p => Strong (Free p) where
    first' (Pure f) = Pure (first' f)
    first' (Free f g) = Free (first' f) (first' g)

但 Free p 究竟是什么？它实际上是一个叫做 pre-arrow 的东西。限制，自由强profunctors是箭头：

instance Profunctor p => Category (Free p) where
    id = Pure id
    Pure f . Pure g = Pure (f . g)
    Free g h . Pure f = Free (lmap f g) h
    Pure f . Free g h = Free g (Pure f . h)
    f . Free g h = Free g (f . h)

instance (Profunctor p, Strong p) => Arrow (Free p) where
    arr = Pure
    first = first'

凭直觉，你可以把一个profunctor P a b的元素想象成把一个a-ish的东西变成一个b-ish的东西，[=给出了典型的例子16=]。 Free P 是这些具有兼容（但不可观察）中间类型的元素的未计算链。

Profunctors 的自由单子模拟

Analog of free monads for Profunctors

haskell

free-monad

profunctor