在编程的上下文中，“余代数”是什么意思？

Question

我在函数式编程和PLT圈子里听过“余代数”这个术语好几次，尤其是当讨论对象、副词、透镜等等的时候。谷歌这个术语给出的页面给出了这些结构的数学描述，这对我来说是很难理解的。谁能解释一下在编程环境中余代数的含义，它们的意义是什么，以及它们与对象和共轭子的关系？

Answer 1

我想从理解代数的概念开始。这只是像群、环、单半体等代数结构的推广。大多数时候，这些东西都是从集合的角度介绍的，但是由于我们是朋友，所以我将讨论Haskell类型。（不过我还是忍不住用一些希腊字母--它们让一切看起来更酷！）

那么，代数就是一个具有某些函数和恒等式的τ类型。这些函数采用不同数量的τ类型的参数，并生成τ:未经修饰的，它们看起来都像(τ,τ,…,τ)→τ。它们还可以具有“身份”--τ元素，它们对某些函数具有特殊的行为。

最简单的例子是么半群。么半群是任意类型τ，其函数mappend±(τ,τ)→τ，恒等式mzero±τ。其他例子包括群（除了有一个额外的invert\τ→τ函数外，它就像单子体）、环、格等等。

所有函数都在τ上操作，但可以有不同的性质。我们可以将它们写成τ→τ，其中τ映射到nτ的元组。这样，可以将标识理解为τy→τ，其中τy只是空元组()。所以我们现在可以简化代数的概念：它只是一种类型，上面有一些函数。

代数只是数学中被“分解”的一个常见模式，就像我们处理代码一样。人们注意到一大堆有趣的东西--前面提到的单元体、群、格等等--都遵循类似的模式，所以他们把它抽象出来。这样做的好处和在编程中一样：它创建了可重用的证明，并使某些类型的推理更加容易。

然而，我们还没有完全完成因式分解。到目前为止，我们有一堆函数τ→τ。我们实际上可以做一个巧妙的把戏，把它们都组合成一个函数。特别是，让我们来看看monoids:我们有mappendü(τ,τ)→τ和memptyü()→τ。我们可以使用一个和类型-或者将这些转换成一个函数。它看起来是这样的：

op ∷ Monoid τ ⇒ Either (τ, τ) () → τ
op (Left (a, b)) = mappend (a, b)
op (Right ())    = mempty

这让我们把代数作为一种类型τ来讨论，它有一个单一的函数，从一些s到一个τ。对于单元体，这种混乱是:要么(τ,τ)()；对于群（有一个额外的τ→τ操作），它是:Obet(τ，τ)τ)()。每种不同的结构都有不同的类型。那么所有这些类型有什么共同点呢？最明显的是，它们都只是乘积的和--代数数据类型。例如，对于monoids，我们可以创建一个适用于任何monoidτ的monoid参数类型：

data MonoidArgument τ = Mappend τ τ -- here τ τ is the same as (τ, τ)
                      | Mempty      -- here we can just leave the () out

对于群、环、格和其他所有可能的结构，我们也可以做同样的事情。

所有这些类型还有什么特别之处？嗯，它们都是函数！例如：

instance Functor MonoidArgument where
  fmap f (Mappend τ τ) = Mappend (f τ) (f τ)
  fmap f Mempty        = Mempty

class Functor f ⇒ Algebra f τ where
  op ∷ f τ → τ

class Functor f ⇒ CoAlgebra f τ where
  coop ∷ τ → f τ

在阅读了一些内容之后，我想我对如何使用余代数来表示类和对象有了一个很好的想法。我们有一个类型C，它包含类中对象的所有可能的内部状态；类本身是C上的余代数，它指定对象的方法和属性。

如代数示例所示，如果对于任何a,b,…，我们有一组函数，比如a→τ和，我们可以使用Alper，将它们组合成一个函数。对偶“概念”将组合一系列τ→a、τ→B等类型的函数。我们可以使用和类型-乘积类型的对偶来实现这一点。因此，给定上面的两个函数（称为f和g)，我们可以创建一个如下所示的函数：

both ∷ τ → (a, b)
both x = (f x, g x)

类型(a,a)以直接的方式是一个函子，因此它肯定符合我们的F-余代数的概念。这个特殊的技巧让我们可以将一堆不同的函数打包成一个τ→fτ类型的函数。

我们想要的方法，可以采取一个参数和修改状态。为此，我们需要接受所有参数并生成一个新的C。让我们设想一个setposition方法，它接受x和y坐标:object.setposition(1,2)。它将如下所示:C→((Int,Int)→C)。

这里的重要模式是，对象的“方法”和“属性”以对象本身作为它们的第一个参数。这就像Python中的self参数一样，也像许多其他语言中隐式的This一样。余代数本质上只是封装了接受self参数的行为：这就是C→F C中的第一个C。

所以让我们把一切都放在一起。假设一个类具有position属性、name属性和setposition函数：

class C
  private
    x, y  : Int
    _name : String
  public
    name        : String
    position    : (Int, Int)
    setPosition : (Int, Int) → C

data C = Obj { x, y  ∷ Int
             , _name ∷ String }

我们有两个属性要写。它们很微不足道：

position ∷ C → (Int, Int)
position self = (x self, y self)

name ∷ C → String
name self = _name self

现在我们只需要能够更新位置：

setPosition ∷ C → (Int, Int) → C
setPosition self (newX, newY) = self { x = newX, y = newY }

这就像一个Python类，它有显式的self变量。现在我们有了一系列self→函数，我们需要将它们组合成一个用于余代数的函数。我们可以用一个简单的元组来完成：

coop ∷ C → ((Int, Int), String, (Int, Int) → C)
coop self = (position self, name self, setPosition self)

简而言之，F余代数通过一系列属性和方法来表示一个类，这些属性和方法都依赖于包含每个对象内部状态的self参数。

到目前为止，我们已经讨论了作为Haskell类型的代数和余代数。代数是一个具有函数fτ→τ的类型τ，而余代数是一个具有函数τ→fτ的类型τ。

然而，没有什么真正将这些想法与Haskell本身联系起来。事实上，它们通常是以集合和数学函数的形式介绍的，而不是以类型和Haskell函数的形式介绍的。的确，我们可以将这些概念概括为任何范畴！

我们可以为某个范畴C定义一个F-代数。首先，我们需要一个函子F:C→C-即内函子。（所有Haskellfunctor实际上都是来自hask→hask的内函数。）然后，代数只是C中的一个对象a，其形态为F a→a。除A→FA外，余代数是相同的。

我们通过考虑其他类别得到了什么？嗯，我们可以在不同的上下文中使用相同的想法。就像单子。在Haskell中，单子是具有三个操作的mut★→类型：

map      ∷ (α → β) → (M α → M β)
return   ∷ α → M α
join     ∷ M (M α) → M α

对于Haskell函子，两个函子的合成就是一个函子本身。在伪代码中，我们可以这样写：

instance (Functor f, Functor g) ⇒ Functor (f ∘ g) where
  fmap fun x = fmap (fmap fun) x

这有助于我们将join看作是从ftpf→f的映射。join的类型是Theα。f(fα)→fα。直观地，我们可以看到一个对所有类型α都有效的函数是如何被认为是F的转换。

return是类似的转换。它的类型是theα。α→fα。这看起来不同--第一个α不是“在”一个函数中！令人高兴的是，我们可以通过在这里添加一个标识函子来解决这个问题:theα。恒等式α→fα。所以return是一个转换标识→F。

现在，我们可以把一个单子看作是一个代数，它是基于某个函子f，它的操作F_2O_F→f和Identity→f。这看起来不眼熟吗？它非常类似于一个半群，它只是某种类型τ，其操作τ×τ→τ和()→τ。

所以一个单子就像一个半群，除了有一个函子，而不是一个类型。这是同一种代数，只是在不同的类别里。（据我所知，这就是“一个单子只是内功能子范畴中的一个单子”这句话的由来。）

现在，我们有了这两个操作:ftpf→f和identity→f。为了得到相应的余代数，我们只需翻转箭头。这为我们提供了两个新的操作:f→fservf和f→identity。我们可以通过像上面这样添加类型变量将它们转换为Haskell类型，给我们α。fα→f(fα)和±α。fα→α。这看起来就像Comonad的定义：

class Functor f ⇒ Comonad f where
  coreturn ∷ f α → α
  cojoin   ∷ f α → f (f α)