scala - "coalgebra"在编程上下文中是什么意思？

Question

我在函数式编程和 PLT 圈子中多次听说过“coalgebras”这个词，尤其是当讨论是关于对象、共子、透镜等的时候。谷歌搜索这个术语给出了对这些结构进行数学描述的页面，这对我来说几乎是不可理解的。任何人都可以解释代数在编程上下文中的含义，它们的意义是什么，以及它们与对象和共子的关系吗？

Answer 1

代数

我认为首先要了解 的想法。代数 .这只是对群、环、幺半群等代数结构的概括。大多数时候，这些东西都是以集合的形式介绍的，但由于我们是 friend ，所以我将改为讨论 Haskell 类型。 (虽然我无法抗拒使用一些希腊字母 - 它们让一切看起来更酷!)

那么，代数只是一个类型 τ具有一定的功能和身份。这些函数采用不同数量的 τ 类型的参数并产生一个 τ : uncurrying, 它们看起来都像 (τ, τ,…, τ) → τ .它们也可以有“身份”——τ 的元素具有某些功能的特殊行为。

最简单的例子是幺半群。幺半群是任何类型 τ带功能 mappend ∷ (τ, τ) → τ和一个身份 mzero ∷ τ .其他例子包括群(就像幺半群一样，除了有一个额外的 invert ∷ τ → τ 函数)、环、格等等。

所有功能都在τ上运行但可以有不同的参数。我们可以将这些写成 τⁿ → τ ，其中 τⁿ映射到 n 的元组τ .这样，将身份视为 τ⁰ → τ 是有意义的。哪里τ⁰只是空元组 () .所以我们现在实际上可以简化代数的概念:它只是某种类型，上面有一些函数。

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

F-代数

但是，我们还没有完成因式分解。到目前为止，我们有一堆函数 τⁿ → τ .我们实际上可以做一个巧妙的技巧将它们全部组合成一个函数。特别是，让我们看看幺半群:我们有 mappend ∷ (τ, τ) → τ和 mempty ∷ () → τ .我们可以使用 sum 类型将这些转换为单个函数— Either .它看起来像这样:

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

我们实际上可以反复使用这个变换来组合所有 τⁿ → τ对于任何代数，函数都可以归为一个函数。 (实际上，我们可以对任意数量的函数 a → τ 、 b → τ 等进行此操作，对任何 a, b,… 也可以这样做。)

这让我们把代数作为一种类型来讨论 τ具有来自 Either 的一些困惑的单个功能s 到单个 τ .对于幺半群，这个困惑是:Either (τ, τ) () ;对于组(有一个额外的 τ → τ 操作)，它是:Either (Either (τ, τ) τ) () .对于每种不同的结构，它都是不同的类型。那么所有这些类型有什么共同点呢？最明显的是，它们都只是乘积的总和——代数数据类型。例如，对于幺半群，我们可以创建一个适用于任何幺半群 τ 的幺半群参数类型:

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

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

所有这些类型还有什么特别之处？嗯，他们都是Functors !例如。:

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

所以我们可以更加概括我们的代数概念。这只是某种类型 τ带功能 f τ → τ对于一些仿函数 f .事实上，我们可以把它写成一个类型类:

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

这通常被称为“F 代数”，因为它由仿函数 F 决定。 .如果我们可以部分应用类型类，我们可以定义类似 class Monoid = Algebra MonoidArgument 的内容。 .

代数

现在，希望您已经很好地掌握了代数是什么以及它如何只是正常代数结构的概括。那么什么是 F 代数呢？好吧，co 暗示它是代数的“对偶”——也就是说，我们取一个代数并翻转一些箭头。我在上面的定义中只看到一个箭头，所以我将翻转它:

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

仅此而已!现在，这个结论似乎有点轻率(呵呵)。它告诉你什么是余代数，但并没有真正提供关于它如何有用或我们为什么关心的任何见解。一旦我找到或想出一个或两个很好的例子，我会很快解决这个问题:P。

类和对象

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

如代数示例所示，如果我们有一堆函数，如 a → τ和 b → τ对于任何 a, b,… ，我们可以使用 Either 将它们全部组合成一个函数，求和类型。双重“概念”将组合一组 τ → a 类型的函数。 , τ → b等等。我们可以使用 sum 类型的对偶(乘积类型)来做到这一点。因此，鉴于上面的两个函数(称为 f 和 g )，我们可以像这样创建一个:

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

型号(a, a)是一个简单的仿函数，所以它肯定符合我们的 F 代数概念。这个特殊的技巧让我们将一堆不同的函数——或者，对于 OOP，方法——打包成一个类型为 τ → f τ 的函数。 .

我们类型的元素 C表示对象的内部状态。如果对象具有一些可读属性，则它们必须能够依赖于状态。最明显的方法是让它们成为 C 的函数。 .所以如果我们想要一个长度属性(例如 object.length )，我们会有一个函数 C → Int .

我们想要可以接受参数并修改状态的方法。为此，我们需要获取所有参数并生成一个新的 C .让我们想象一个 setPosition方法采用 x和一个 y坐标:object.setPosition(1, 2) .它看起来像这样:C → ((Int, Int) → C) .

这里的重要模式是对象的“方法”和“属性”将对象本身作为它们的第一个参数。这就像self Python 中的参数和隐式 this许多其他语言。代数本质上只是封装了取 self 的行为。参数:这就是第一个 C在 C → F C是。

所以让我们把它们放在一起。让我们想象一个带有 position 的类属性(property)，name属性(property)和setPosition功能:

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

我们需要两部分来表示这个类。首先，我们需要表示对象的内部状态；在这种情况下，它只包含两个 Int s 和 String . (这是我们的类型 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 }

这就像一个带有显式 self 的 Python 类。变量。现在我们有一堆 self →函数，我们需要将它们组合成一个用于余代数的函数。我们可以用一个简单的元组来做到这一点:

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

型号((Int, Int), String, (Int, Int) → c) —对于任何 c — 是仿函数，所以 coop确实有我们想要的形式:Functor f ⇒ C → f C .

鉴于此，C连同 coop形成一个余代数，它指定了我上面给出的类。您可以看到我们如何使用相同的技术为我们的对象指定任意数量的方法和属性。

这让我们可以使用代数推理来处理类。例如，我们可以引入“F-coalgebra 同态”的概念来表示类之间的转换。这是一个听起来很可怕的术语，仅表示保留结构的余代数之间的转换。这使得考虑将类映射到其他类变得更加容易。

简而言之，F-coalgebra 通过拥有一堆依赖于 self 的属性和方法来表示一个类。包含每个对象内部状态的参数。

其他类别

到目前为止，我们已经将代数和余代数作为 Haskell 类型进行了讨论。代数只是一种类型 τ带功能 f τ → τ而余代数只是一个类型 τ带功能 τ → f τ .

然而，没有什么能真正将这些想法与 Haskell 本身联系起来。事实上，它们通常是根据集合和数学函数而不是类型和 Haskell 函数来介绍的。事实上，我们可以将这些概念推广到任何类别!

我们可以为某个类别定义 F 代数 C .首先，我们需要一个仿函数 F : C → C ——也就是说，一个内仿函数。 (所有 Haskell Functor 实际上都是来自 Hask → Hask 的内仿函数。)那么，代数只是一个对象 A来自 C带态射 F A → A .余代数是相同的，除了 A → F A .

考虑其他类别我们会得到什么？好吧，我们可以在不同的上下文中使用相同的想法。就像单子(monad)一样。在 Haskell 中，monad 是某种类型 M ∷ ★ → ★三个操作:

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

map函数只是事实的证明 M是 Functor .所以我们可以说一个 monad 只是一个有两个操作的仿函数:return和 join .

仿函数本身形成一个范畴，它们之间的态射是所谓的“自然变换”。自然变换只是一种将一个仿函数变换为另一个同时保留其结构的方法。 Here's一篇很好的文章，有助于解释这个想法。谈concat ，这只是 join对于列表。

使用 Haskell 仿函数，两个仿函数的组合就是一个仿函数本身。在伪代码中，我们可以这样写:

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

这有助于我们思考 join作为来自 f ∘ f → f 的映射. join的类型是 ∀α. f (f α) → f α .直观地，我们可以看到一个函数如何对所有类型有效 α可以认为是对f的改造.
return是类似的变换。它的类型是 ∀α. α → f α .这看起来不一样——第一个 α不是“在”一个仿函数!令人高兴的是，我们可以通过在那里添加一个恒等仿函数来解决这个问题:∀α. Identity α → f α .所以return是一个转换 Identity → f .

现在我们可以将 monad 视为基于某个仿函数 f 的代数。与操作 f ∘ f → f和 Identity → f .这看起来是不是很熟悉？它非常类似于幺半群，它只是某种类型 τ与操作 τ × τ → τ和 () → τ .

所以一个 monad 就像一个幺半群，除了我们有一个仿函数而不是一个类型。这是同一种代数，只是属于不同的类别。 (据我所知，这就是短语“单子(monad)只是内仿函数范畴中的幺半群”的来源。)

现在，我们有这两个操作: f ∘ f → f和 Identity → f .为了得到相应的余代数，我们只需翻转箭头即可。这给了我们两个新的操作:f → f ∘ f和 f → Identity .我们可以通过添加类型变量将它们转换为 Haskell 类型，如上，给我们 ∀α. f α → f (f α)和 ∀α. f α → α .这看起来就像一个 comonad 的定义:

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

因此，共谐子是一类内仿函数中的余代数。