这个函子的特性是否比单子更强大？

Question

这个函子的特性是否比单子更强大？

haskellfunctional-programmingmonadsfunctorcategory-theory

27

在思考如何一般化单子时，我想出了一个关于函子F的以下特性：

inject :: (a -> F b) -> F(a -> b)

-- 应该在a和b中都是自然变换。

在没有更好的名称的情况下，如果存在如上所示的自然变换inject，则称函子F为可绑定的(bindable)。

主要问题是，是否已知此属性并具有名称，并且它与函子的其他众所周知的属性（例如，可应用、单调、指向、遍历等）有何关系。

名称“可绑定”(bindable)的动机来自以下考虑：假设M是一个单子(Monad)，而F是一个“可绑定”的函子。那么就有以下自然态射：

fbind :: M a -> (a -> F(M b)) -> F(M b)

这类似于单子的“绑定(bind)”，

bind :: M a -> (a -> M b) -> M b

除了结果被functor F修饰之外。

fbind的背后思想是，广义单子操作不仅可以产生单个结果M b，还可以产生“functor-ful”F中的多个这样的结果。我想表达的是当单子操作产生多个“计算线程”而不仅仅是一个时的情况；每个“计算线程”再次是一个单子计算。

请注意，每个functor F都有一个态射。

eject :: F(a -> b) -> a -> F b

这是与“inject”相反的概念。但并不是每个函子F都有“inject”。

具有“inject”的函子示例： F t =（t，t，t）或F t = c ->（t，t）其中c是常量类型。函子F t = c（常量函子）或F t =（c，t）不可“绑定”（即没有“inject”）。连续函子F t =（t -> r） -> r似乎也没有inject。

“inject”的存在可以用另一种方式来表达。考虑“reader”函子R t = c -> t其中c是常量类型。（这个函子是适用和单调的，但这不是重点。）然后，“inject”属性意味着R（F t） -> F（R t），换句话说，R与F交换。请注意，这与要求F可遍历的要求不同；对于任何函子F而言，这将始终满足对于R来说，那将是F（R t） -> R（F t）。

到目前为止，我能够证明“inject”对于任何单子M都意味着“fbind”。

此外，我展示了具有“inject”的每个函子F还将具有以下其他属性：

- 它是指向的 - 如果F是“可绑定”的并且适用，则F也是单子 - 如果F和G是“可绑定”的，则对于一对函子F * G（但不是F + G）也是如此。 - 如果F是“可绑定”的并且A是任何profunctor，则（pro）functor G t = A t -> F t是可绑定的。 - 标识函子是可绑定的。

未解决的问题：

- “可绑定”属性是否等同于其他众所周知的属性，或者它是通常不考虑的函子的新属性？ - 从“inject”的存在中是否还遵循函子“F”的任何其他属性？ - 我们需要为“inject”制定任何法则吗？例如，我们可以要求R（F t）在一个或两个方向上与F（R t）同构。

- winitzki

2

附带问题：您是否有一些有用的代码片段可以展示这个工具的实用性？ - BitTickler

3

我认为对于任何函子F，属性 F (a->b) -> a -> F b 都成立，而不仅仅是可遍历的函子。 - winitzki

3

对我来说，这看起来比单子强大得多。从纯实用的角度来看，我们无法构建类似于inject id :: IO (IO a -> a)的东西。那将是非常危险的，实际上为纯代码提供对unsafePerformIO的访问，只要最终从IO中调用它就可以了（因为我们是从“main”开始的）。基本上，我们只需要做main = do upIO <- inject id ; print (pureF upIO 12) ; ...就可以让纯类型的pureF运行副作用。这很可怕。 - chi

3

请注意，我之前问了这个问题：https://dev59.com/GoTba4cB1Zd3GeqP1RlS ，据大家所知，唯一具有此属性的函子是 Identity 和 (->) a。因此，我怀疑这比 Monad 要强得多。 - Jonathan Cast

4

Distributive f可以让你使用distribute :: Functor g => g (f a) -> f (g a)函数，从Haskell类型的角度来看比你的函数更强大。我不知道它是否满足您的范畴论法则。每个“可表示”functor都是分配的，并且文档中指出，反过来也成立数学上。 - dfeuer

显示剩余32条评论

3个回答

6

这里是一种可能的刚性函子呈现方式。出于我即将提到的原因，我稍微修改了你的命名：

flap :: Functor f => f (a -> b) -> a -> f b
flap u a = ($ a) <$> u 

class Functor g => Rigid g where
    fflip :: (a -> g b) -> g (a -> b)
    fflip f = (. f) <$> extractors

    extractors :: g (g a -> a)
    extractors = fflip id

-- "Left inverse"/non-degeneracy law: flap . fflip = id

instance Rigid ((->) r) where
    fflip = flip

一些关于我的措辞的备注：

I have changed the names of inject and eject to fflip and flap, mainly because, to my eyes, flap looks more like injecting, due to things like this:
```
sweep :: Functor f => f a -> b -> f (a, b)
sweep u b = flap ((,) <$> u) b
```
I took the flap name from protolude. It is a play on flip, which is fitting because it is one of two symmetrical ways of generalising it. (We can either pull the function outside of an arbitrary Functor, as in flap, or pull a Rigid functor outside of a function, as in fflip.)

extractors and fflip are interdefinable, making it possible to write, for example, this neat instance for the search/selection monad:

newtype Sel r a = Sel { runSel :: (a -> r) -> a }
    deriving (Functor, Applicative, Monad) via SelectT r Identity

instance Rigid (Sel r) where
    -- Sel r (Sel r a -> a) ~ ((Sel r a -> a) -> r) -> Sel r a -> a
    extractors = Sel $ \k m -> m `runSel` \a -> k (const a)

extractors 的一个重要事实是它引出了以下组合子：

distributeLike :: (Rigid g, Functor f) => f (g a) -> g (f a)
distributeLike m = (<$> m) <$> extractors

distributeLike 是 Distributive 类中 distribute 的更通用版本。相应地，合法的 distribute 必须遵守以下定律，这些定律是 Traversable 定律的对偶：

-- Identity law
fmap runIdentity . distribute = runIdentity

-- Composition law
fmap getCompose . distribute = distribute . fmap distribute . getCompose

-- Naturality law (always holds, by parametricity)
-- For any natural transformation t
fmap t . distribute = distribute . t

由于fflip是使用reader作为另一个functor的distributeLike函数，而flap则是reader的distribute函数，因此flap . fflip = id和fflip . flap = id都是特例...

-- m :: f (g a)
distributeLike (distributeLike m) = m

...通过适当选择f和g，可以满足上述特性。现在，上述属性可以证明等价于以下条件：

对于g的distributeLike遵循分配函子的恒等法则（顺便说一下，这与刚性法则等价）；
对于f的distributeLike也遵循分配函子的恒等法则；
以下任一等价条件成立：

a. f的distributeLike遵循分配函子的组合法则；或

b. 由f的extractors提供的所有f a -> a函数在a中都是自然的。

特别地，由于flap是一个合法的distribute，flap.fflip = id相当于g的恒等律（条件#2），而fflip.flap = id则表明f具有分配性质（条件#1和#3）。

（上述条件可以通过使用extractors分析distributeLike.distributeLike = id来建立，这遵循了我在“每个分配都是可表示的”一文中“路障和绕路”部分中应用于组合法则的类似策略。）

为了举例说明，让我们考虑Sel r的情况。正如您所指出的，它是刚性但不具有分配性质，其distributeLike遵循恒等律但不遵循组合律。因此，fflip.flap = id不成立。

关于在类型类星座中找到适合 Rigid 的位置，我想强调条件 #3b 特别有趣。看起来，鉴于 extractors @f :: forall a. f (f a -> a) 在 a 上是完全多态的，为了提供非自然的 f a -> a 提取器，f 不能严格为正，对应于你的答案中“构造和示例”部分中的第4个构造。缺乏严格的正性使得 extractors 可以包含非自然性（通过用户提供的逆变参数）而不需要在其定义中明确指定。因此，只有不严格为正的函子，例如 Sel r，可能是刚性的而不是分配的。

杂项说明

从单子的角度看，我们可以说刚性单子配备了从Kleisli箭头到静态箭头的单射转换。对于分配单子，该转换升级为同构，这是Applicative和Monad在Reader中等价的推广。非分配刚性单子的一个有趣方面是，fflip是单射但不是满射，这意味着静态箭头比Kleisli箭头更多，这是一种相当不寻常的状态。
extractors概括了Distributive的大部分内容。对于任何分配函子g，都存在一个g (g a -> a)值，在其中每个位置都填充了匹配的g a -> a自然提取函数。对于不是分配的刚性函子，这种整洁的对应关系不再成立。例如，对于Sel r，每个a -> r都会产生一个提取器，但通常不是自然的。这最终排除了将distribute/fflip（以及tabulate）作为同构的可能性。实际上，当处理不是严格正面的函子时，一个具有良定义位置的形状的概念本质上会崩溃。
Distributive是Traversable的对偶，两个类之间有几个对应关系（特别是，以读取器函子的同构表示的Distributive的演示，反映了Traversable的形状和内容的表述方式，可以用某些类似于列表的函子的同构表示）。既然如此，人们可能会想知道是否存在类似于Rigid的概念适用于Traversable。我相信它确实存在，尽管这种概念有多么有用还不清楚。"co-rigid"伪遍历的一个例子是，一个数据结构配备了一个遍历，该遍历复制效果，但在重建应用层下的结构时丢弃相应的重复元素，以遵循恒等律，但不遵循组合律。

- duplode

（1）确实如此。撇开实现细节不谈，Traversable同构等价于一个clear函数，它清空可遍历结构并输出其形状和内容列表，以及一个fill函数，它根据形状和内容重新创建结构。fill . clear = id相当于Traversable的恒等律，而添加clear . fill = id相当于添加组合律。虚拟可遍历类仅具有恒等律是可以想象的，但我怀疑它不会被广泛使用——主要问题在于遍历无法干净地组合。 - duplode

（2a）所有分配函子都与某个r的Reader r同构，尽管根据需要，使用非函数形式可能更方便。例如，无限流、固定长度向量以及更一般地具有固定形状的任何数据结构。 - duplode

一个遍历对象如果拥有clear . fill = id而没有fill . clear = id，那会有用吗？ - winitzki

@winitzki 重新审视这个问题，我注意到我的推理有一个缺陷：对于具有适当高阶类型((forall x. Sel r x -> x) -> a) -> Sel r a的Sel r，没有合理的revert。我们编写的extractors和fflip是从具有类型((Sel r a -> a) -> a) -> Sel r a的revert的模仿中产生的。鉴于这种不太多态化的类型和Sel r a不是严格正的，我们可以欺骗并使用单态化的k :: a -> r函数来提取结果。这意味着我关于revert/evert的大部分考虑都不适用于Sel r。我会研究一种修复此答案的方法... - duplode

@winitzki 我已经重写了答案，删除了有关 revert/evert 的各种离题讨论，并专注于一些看起来不错的积极结果：似乎只有那些不严格正（即您的构造#4）的函数子可以是刚性的而不是分配的。顺便说一句，考虑到Sel的反例对于使我理解 Distributive更加清晰非常重要；感谢您让我考虑它！ - duplode

显示剩余5条评论

1

我们都熟悉 Traversable 类型类，它可以归纳为以下内容：

class Functor t => Traversable t
  where
  sequenceA :: Applicative f => t (f a) -> f (t a)

这里使用了“Applicative”函子的概念。对于支撑“Applicative”的范畴概念，有一种仅涉及规律的加强版，具体如下：

-- Laxities of a lax monoidal endofunctor on Hask under (,)
zip :: Applicative f => (f a, f b) -> f (a, b)
zip = uncurry $ liftA2 (,)

husk :: Applicative f => () -> f ()
husk = pure

-- Oplaxities of an oplax monoidal endofunctor on ... (this is trivial for all endofunctors on Hask)
unzip :: Functor f => f (a, b) -> (f a, f b)
unzip fab = (fst <$> fab, snd <$> fab)

unhusk :: f () -> ()
unhusk = const ()

-- The class
class Applicative f => StrongApplicative f

-- The laws
-- zip . unzip = id
-- unzip . zip = id
-- husk . unhusk = id
-- unhusk . husk = id -- this one is trivial

链接的问题及其答案有更多细节，但要点是StrongApplicative模型化了一些关于函子“固定大小”的概念。这个类型类与Representable函子有一个有趣的联系。为参考，Representable是：

class Functor f => Representable x f | f -> x
  where
  rep :: f a -> (x -> a)
  unrep :: (x -> a) -> f a

instance Representable a ((->) a)
  where
  rep = id
  unrep = id

一个由@Daniel Wagner提出的论点表明StrongApplicative是Representable的一般化，因为每个Representable都是StrongApplicative。目前还不清楚是否存在任何不是Representable的StrongApplicative。

现在，我们知道Traversable是以Applicative为基础并向一个方向运行的。由于StrongApplicative将Applicative的松弛程度提升到同构，也许我们想要使用这个额外的设备来反转Traversable提供的分配法则：

class Functor f => Something f
  where
  unsequence :: StrongApplicative f => f (t a) -> t (f a)

恰好，(->) a是一个StrongApplicative，实际上是Representable StrongApplicative函子的代表样本（如果您允许我开个玩笑的话）。因此，我们可以将您的inject/promote操作写为：

promote :: Something f => (a -> f b) -> f (a -> b)
promote = unsequence

我们之前提到过，StrongApplicative 是 Representative 函子家族的一个超类。从检查 unsequence 的类型中可以看出，我们在多态应用上放置的限制越强，实现 unsequence 就会变得更容易（因此结果类的实例也会更多）。

因此，在某种意义上，存在一种“可反向遍历”函子的层次结构，其流动方向与您可能希望对其进行反遍历的适用效果的层次结构相反。 “内部”函子的层次结构如下：

Functor f => Applicative f => StrongApplicative f => Representable x f

相应的可遍历/分配函子的层次结构可能如下所示：

Distributive t <= ADistributive t <= SADistributive t <= RDistributive t

带有定义：

class RDistributive t
  where
  rdistribute :: Representable x f => f (t a) -> t (f a)

  default rdistribute :: (SADistributive t, StrongApplicative f) => f (t a) -> t (f a)
  rdistribute = sadistribute

class RDistributive t => SADistributive t
  where
  sadistribute :: StrongApplicative f => f (t a) -> t (f a)

  default sadistribute :: (ADistributive t, Applicative f) => f (t a) -> t (f a)
  sadistribute = adistribute

class SADistributive t => ADistributive t
  where
  adistribute :: Applicative f => f (t a) -> t (f a)

  default adistribute :: (Distributive t, Functor f) => f (t a) -> t (f a)
  adistribute = distribute

class ADistributive t => Distributive t
  where
  distribute :: Functor f => f (t a) -> t (f a)

我们对于 promote 的定义可以概括为依赖于 RDistributive（因为 (->) a 本身确实是一个可表示函子）：

promote :: RDistributive f => (a -> f b) -> f (a -> b)
promote = rdistribute

在一个奇怪的转折中，一旦你到达这个层次结构的底部（即到达），相对于你的需求，你的detraversability承诺变得非常强大，以至于你只能为实现它的函子提供乐趣。这样一个可分配、可表示（因此刚性）的函子的例子是一对：

data Pair a = Pair { pfst :: a, psnd :: a }
  deriving Functor

instance RDistributive Pair
instance SADistributive Pair
instance ADistributive Pair
instance Distributive Pair
  where
  distribute x = Pair (pfst <$> x) (psnd <$> x)

当然，如果您对多态的“内部函数”提出了强烈的要求，例如在RDistributive中的Representable x f，则可以实现此类实例：

newtype Weird r a = Weird { runWeird :: (a -> r) -> a }
  deriving Functor

instance RDistributive (Weird r)
  where
  rdistribute = fmap unrep . promoteWeird . rep
    where
    promoteWeird :: (x -> Weird r a) -> Weird r (x -> a)
    promoteWeird f = fmap (. f) $ Weird $ \k m -> m `runWeird` \a -> k (const a)

待完成：检查在层次结构中是否有其他刚性函子的示例。

就像我说的，我没有非常仔细地考虑过，因此可能这里的人们已经对刚性函子概念进行了一些思考，并立即在其中挑出了漏洞。或者，也许它可以使我尚未看到的事情恰好落到位。

值得思考这些不可遍历类型类的某些定律。一个明显的建议是，在函子支持Traversable和Untraverse的情况下，sequence.unsequence = id和unsequence.sequence = id。

值得一提的是，函子的“分配定律”与单子和余单子的相互作用已经被广泛研究，因此这可能与您帖子中与单子相关的讨论有关。

- Asad Saeeduddin

目前还不清楚是否存在任何StrongApplicative不是Representable。 StrongApplicative确实意味着Representable。 husk.unhusk = id表示对于任何u，() <$ u = husk()。因此，husk()的形状是StrongApplicative唯一可能的形状，并且具有单一形状相当于是Representable/Distributive。 - duplode

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- winitzki · Accepted Answer

为了更好地表达术语，我建议将这些函数子称为“刚性”而不是“可绑定”的。下面将解释称之为“刚性”的动机。

定义

如果一个函子f具有所示的inject方法，则称其为刚性。请注意，每个函子都有eject方法。

class (Functor f) => Rigid f where
  inject :: (a -> f b) -> f(a -> b)

  eject :: f(a -> b) -> a -> f b
  eject fab x = fmap (\ab -> ab x) fab

"非退化性"定律必须得到遵守：

eject . inject = id

属性

刚性函子始终是指向的：

instance (Rigid f) => Pointed f where
  point :: t -> f t
  point x = fmap (const x) (inject id)

如果一个刚性函子是应用函子，则它自动成为单子函子：

instance (Rigid f, Applicative f) => Monad f where
  bind :: f a -> (a -> f b) -> f b
  bind fa afb = (inject afb) <*> fa

具有刚性特性的函子与具有单子特性的函子无法比较（既不强于也不弱于）：如果一个函子具有刚性特性，则似乎不能自动推出它是单子特性（尽管我不知道此情况的具体反例）。如果一个函子具有单子特性，则不能推出它具有刚性特性（存在反例）。

不具有刚性特性的单子函子的基本反例是Maybe和List。这些是具有多个构造函数的函子：这样的函子不能是刚性的。

实现Maybe的inject函数的问题在于，inject必须将类型为a->Maybe b的函数转换为Maybe(a -> b) ，而Maybe有两个构造函数。类型为a->Maybe b的函数可以针对a的不同值返回不同的构造函数。然而，我们应该构造一个类型为Maybe(a -> b)的值。如果对于某些a，给定的函数产生Nothing，则我们没有b，因此无法产生完全函数a->b 。因此，我们不能返回Just(a->b)；只要给定的函数对于任何一个a的值产生Nothing，我们就被迫返回Nothing。但是，我们无法检查类型为a->Maybe b的给定函数是否对所有a的值产生Just(...)。因此，在所有情况下，我们都被迫返回Nothing。这将不符合非退化性法则。

因此，我们只有在f t是具有“固定形状”的容器（仅具有一个构造函数）时才能实现inject。因此称为“刚性”。

另一个解释为什么刚性比单子更严格的方法是考虑自然定义的表达式。

(inject id) :: f(f a -> a)

id :: f a -> f a表示我们可以对任何类型a进行f-代数f a -> a，只要它被包含在f中。并不是所有的monad都有代数；例如，各种“future”monad以及IO monad描述了类型为f a的计算，这些计算不允许我们提取类型为a的值——即使它们被包装在f-容器中，我们也不应该能够拥有类型为f a -> a的方法。这表明“future”monads和IO monad不是刚性的。

比刚性更严格的一个特性是来自E. Kmett的软件包之一的distributivity。如果我们可以交换任何functor p的顺序，就像p (f t) -> f (p t)一样，则functor f是分配的。刚性与仅与“reader” functor r t = a -> t相关的顺序互换相同。因此，所有分配的functors都是刚性的。

所有分配的functors必须是可表示的，这意味着它们等价于具有某个固定类型c的“reader” functor c -> t。然而，并非所有刚性的functors都是可表示的。一个例子是由下列定义的functor g：

type g t = (t -> r) -> t

函子g与固定类型c的c -> t不等价。

构造和示例

更多非可表示（即非“分配”的）刚性函子的示例包括形如a t -> f t的函子，其中a是任意反变函子，f是刚性函子。此外，笛卡尔积和两个刚性函子的组合仍然是刚性的。通过这种方式，我们可以在指数-多项式类别中产生许多刚性函子的示例。

我的回答What is the general case of QuickCheck's promote function?也列出了刚性函子的构造：

f = Identity
如果f和g都是刚性的，则函子乘积h t = (f t, g t)也是刚性的
如果f和g都是刚性的，则组合h t = f (g t)也是刚性的
如果f是刚性的且g是任何反变函子，则函子h t = g t -> f t是刚性的

刚性函子的另一个特性是类型r()等价于()，即类型r()只有一个不同的值。这个值是point()，其中point对于任何刚性函子r都被定义在上面。这表明刚性函子必须只有一个构造函数。这立即表明Maybe、Either、List等不能是刚性的。

与单子的联系

如果f是具有“外部组合”型单子转换器t m a = f (m a)的单子，则f是刚性函子。

“刚性单子”可能是刚性函子的一个子集，因为构造4仅在f也是刚性单子而不是任意刚性函子时才产生刚性单子（但反变函子g仍然可以是任意的）。但是，我没有任何刚性函子的例子，它不是单子。

最简单的刚性单子例子是type r a = (a -> p) -> a，也称为“搜索单子”。（这里的p是一个固定类型。）

为了证明具有“外部组合”变换器t m a = f(m a)的单子f也具有inject方法，我们考虑将外部单子m选择为读取器单子，m a = r -> a。然后，正确类型签名的函数inject定义如下：

 inject = join @t . return @r . (fmap @m (fmap @f return @m))

通过适当选择类型参数，可以实现非退化规律。

非退化规律源于t的自然性：将单子态态射m→Identity（将类型r的值替换为读取器中的值）提升为单子态态射t m a→t Id a。此证明的详细信息略去。

使用案例

最后，我找到了两个刚性函子的使用案例。

第一个用例是考虑刚性函子的原始动机：我们希望一次返回多个单子结果。如果 m 是单子态，且我们想要像问题中所示的那样拥有 fbind，则需要 f 是刚性的。然后，我们可以实现以下的 fbind

fbind :: m a -> (a -> f (m b)) -> f (m b)
fbind ma afmb = fmap (bind ma) (inject afmb)

我们可以使用fbind来进行单子操作，返回多个单子结果（或者更普遍地说，是一个刚性函子的单子结果集合），对于任何单子m。

第二种用例源于以下考虑。假设我们有一个程序p :: a，它在内部使用函数f :: b -> c。现在，我们注意到函数f非常慢，我们想通过将f替换为单子“future”或“task”，或者通常情况下替换为某个单子m c的Kleisli箭头f' :: b -> m c来重构程序。当然，我们期望程序p也变成单子形式：p' :: m a。我们的任务是将p重构为p'。

重构分为两步：首先，我们重构程序p，使函数f明确成为p的参数。假设已经完成了这一步，因此现在我们有p = q f，其中

q :: (b -> c) -> a

第二步，我们将f替换为f'。现在假设已知q和f'。我们希望构建新的程序q'，其类型为：

q' :: (b -> m c) -> m a

所以，p' = q' f'。问题是我们是否可以定义一个通用的组合器，将q重构为q'，

refactor :: ((b -> c) -> a) -> (b -> m c) -> m a

原来只有在m是刚性函子的情况下才能构造refactor。在试图实现refactor时，我们发现与我们尝试为Maybe实现inject时基本相同的问题：我们得到一个函数f' :: b -> m c，它可以为不同的b返回不同的单调效果m c，但我们需要构造m a，它必须代表所有b的相同单调效果。如果m是具有多个构造函数的单子，则无法工作。

如果m是刚性的（我们不需要要求m是单子），我们可以实现refactor：

refactor bca bmc = fmap bca (inject bmc)

如果m不是刚性的，我们就无法重构任意程序。到目前为止，我们已经知道延续单子是刚性的，但“类似于未来”的单子和IO单子不是刚性的。这再次表明，刚性在某种程度上是比单子性更强的属性。