“代数"是什么意思在编程的上下文中是什么意思? [英] What does "coalgebra" mean in the context of programming?

问题描述

我在函数式编程和 PLT 圈子中多次听说过代数"这个词，尤其是在讨论对象、共子、透镜等时.谷歌搜索这个术语给出了对这些结构进行数学描述的页面，这对我来说几乎是不可理解的.谁能解释一下余代数在编程上下文中的含义，它们的意义是什么，以及它们与对象和共子的关系?

I have heard the term "coalgebras" several times in functional programming and PLT circles, especially when the discussion is about objects, comonads, lenses, and such. Googling this term gives pages that give mathematical description of these structures which is pretty much incomprehensible to me. Can anyone please explain what coalgebras mean in the context of programming, what is their significance, and how they relate to objects and comonads?

推荐答案

代数

我认为首先要了解代数的概念.这只是对群、环、幺半群等代数结构的概括.大多数时候，这些东西都是以集合的形式介绍的，但由于我们是朋友，所以我将改为讨论 Haskell 类型.(不过我还是忍不住用了一些希腊字母——它们让一切看起来更酷！)

Algebras

I think the place to start would be to understand the idea of an algebra. This is just a generalization of algebraic structures like groups, rings, monoids and so on. Most of the time, these things are introduced in terms of sets, but since we're among friends, I'll talk about Haskell types instead. (I can't resist using some Greek letters though—they make everything look cooler!)

因此，代数只是具有一些函数和恒等式的类型τ.这些函数采用不同数量的 τ 类型的参数并产生一个 τ:非柯里化的，它们看起来都像 (τ, τ,…, τ) → τ.它们也可以有身份"——τ 的元素，这些元素对某些函数具有特殊的行为.

An algebra, then, is just a type τ with some functions and identities. These functions take differing numbers of arguments of type τ and produce a τ: uncurried, they all look like (τ, τ,…, τ) → τ. They can also have "identities"—elements of τ that have special behavior with some of the functions.

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

The simplest example of this is the monoid. A monoid is any type τ with a function mappend ∷ (τ, τ) → τ and an identity mzero ∷ τ. Other examples include things like groups (which are just like monoids except with an extra invert ∷ τ → τ function), rings, lattices and so on.

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

All the functions operate on τ but can have different arities. We can write these out as τⁿ → τ, where τⁿ maps to a tuple of n τ. This way, it makes sense to think of identities as τ⁰ → τ where τ⁰ is just the empty tuple (). So we can actually simplify the idea of an algebra now: it's just some type with some number of functions on it.

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

An algebra is just a common pattern in mathematics that's been "factored out", just like we do with code. People noticed that a whole bunch of interesting things—the aforementioned monoids, groups, lattices and so on—all follow a similar pattern, so they abstracted it out. The advantage of doing this is the same as in programming: it creates reusable proofs and makes certain kinds of reasoning easier.

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

However, we're not quite done with factoring. So far, we have a bunch of functions τⁿ → τ. We can actually do a neat trick to combine them all into one function. In particular, let's look at monoids: we have mappend ∷ (τ, τ) → τ and mempty ∷ () → τ. We can turn these into a single function using a sum type—Either. It would look like this:

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

我们实际上可以重复使用这种转换来将所有τⁿ → τ函数组合成一个函数，用于任何代数.(事实上​​，我们可以对任意数量的函数a → τ、b → τ 等，对于any a, b,....)

We can actually use this transformation repeatedly to combine all the τⁿ → τ functions into a single one, for any algebra. (In fact, we can do this for any number of functions a → τ, b → τ and so on for any a, b,….)

这让我们可以将代数作为一种类型τ 与single 函数从一些Either 到单个τ.对于幺半群，这个混乱是:Either (τ, τ) ();对于组(具有额外的 τ → τ 操作)，它是:Either (Either (τ, τ) τ) ().对于每种不同的结构，它都是不同的类型.那么所有这些类型有什么共同点呢?最明显的是，它们都只是乘积的总和——代数数据类型.例如，对于幺半群，我们可以创建一个适用于 any monoid τ:

This lets us talk about algebras as a type τ with a single function from some mess of Eithers to a single τ. For monoids, this mess is: Either (τ, τ) (); for groups (which have an extra τ → τ operation), it's: Either (Either (τ, τ) τ) (). It's a different type for every different structure. So what do all these types have in common? The most obvious thing is that they are all just sums of products—algebraic data types. For example, for monoids, we could create a monoid argument type that works for any monoid τ:

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

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

We can do the same thing for groups and rings and lattices and all the other possible structures.

所有这些类型还有什么特别之处?好吧，他们都是Functors！例如:

What else is special about all these types? Well, they're all Functors! E.g.:

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

所以我们可以进一步推广我们的代数概念.它只是某种类型的 τ 和一个函数 f τ → τ 用于某些函子 f.事实上，我们可以把它写成一个类型类:

So we can generalize our idea of an algebra even more. It's just some type τ with a function f τ → τ for some functor f. In fact, we could write this out as a typeclass:

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

这通常被称为F-代数"，因为它由函子 F 决定.如果我们可以部分应用类型类，我们可以定义类似 class Monoid = Algebra MonoidArgument 的东西.

This is often called an "F-algebra" because it's determined by the functor F. If we could partially apply typeclasses, we could define something like class Monoid = Algebra MonoidArgument.

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

Now, hopefully you have a good grasp of what an algebra is and how it's just a generalization of normal algebraic structures. So what is an F-coalgebra? Well, the co implies that it's the "dual" of an algebra—that is, we take an algebra and flip some arrows. I only see one arrow in the above definition, so I'll just flip that:

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

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

And that's all it is! Now, this conclusion may seem a little flippant (heh). It tells you what a coalgebra is, but does not really give any insight on how it's useful or why we care. I'll get to that in a bit, once I find or come up with a good example or two :P.

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

After reading around a bit, I think I have a good idea of how to use coalgebras to represent classes and objects. We have a type C that contains all the possible internal states of objects in the class; the class itself is a coalgebra over C which specifies the methods and properties of the objects.

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

As shown in the algebra example, if we have a bunch of functions like a → τ and b → τ for any a, b,…, we can combine them all into a single function using Either, a sum type. The dual "notion" would be combining a bunch of functions of type τ → a, τ → b and so on. We can do this using the dual of a sum type—a product type. So given the two functions above (called f and g), we can create a single one like so:

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

类型 (a, a) 是一个简单的函子，所以它当然符合我们的 F-coalgebra 概念.这个特殊的技巧让我们可以将一堆不同的函数——或者，对于 OOP，方法——打包成一个 τ → f τ 类型的函数.

The type (a, a) is a functor in the straightforward way, so it certainly fits with our notion of an F-coalgebra. This particular trick lets us package up a bunch of different functions—or, for OOP, methods—into a single function of type τ → f τ.

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

The elements of our type C represent the internal state of the object. If the object has some readable properties, they have to be able to depend on the state. The most obvious way to do this is to make them a function of C. So if we want a length property (e.g. object.length), we would have a function C → Int.

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

We want methods that can take an argument and modify state. To do this, we need to take all the arguments and produce a new C. Let's imagine a setPosition method which takes an x and a y coordinate: object.setPosition(1, 2). It would look like this: C → ((Int, Int) → C).

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

The important pattern here is that the "methods" and "properties" of the object take the object itself as their first argument. This is just like the self parameter in Python and like the implicit this of many other languages. A coalgebra essentially just encapsulates the behavior of taking a self parameter: that's what the first C in C → F C is.

所以让我们把它们放在一起.让我们想象一个具有 position 属性、name 属性和 setPosition 函数的类:

So let's put it all together. Let's imagine a class with a position property, a name property and setPosition function:

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

我们需要两部分来表示这个类.首先，我们需要表示对象的内部状态；在这种情况下，它只包含两个 Int 和一个 String.(这是我们的类型C.)然后我们需要想出代表类的余代数.

We need two parts to represent this class. First, we need to represent the internal state of the object; in this case it just holds two Ints and a String. (This is our type C.) Then we need to come up with the coalgebra representing the class.

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

我们有两个属性要写.它们非常简单:

We have two properties to write. They're pretty trivial:

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

name ∷ C → String
name self = _name self

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

Now we just need to be able to update the position:

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

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

This is just like a Python class with its explicit self variables. Now that we have a bunch of self → functions, we need to combine them into a single function for the coalgebra. We can do this with a simple tuple:

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

类型 ((Int, Int), String, (Int, Int) → c)——对于 any c——是一个函子，所以 coop 确实有我们想要的形式:Functor f ⇒ C → f C.

The type ((Int, Int), String, (Int, Int) → c)—for any c—is a functor, so coop does have the form we want: Functor f ⇒ C → f C.

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

Given this, C along with coop form a coalgebra which specifies the class I gave above. You can see how we can use this same technique to specify any number of methods and properties for our objects to have.

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

This lets us use coalgebraic reasoning to deal with classes. For example, we can bring in the notion of an "F-coalgebra homomorphism" to represent transformations between classes. This is a scary sounding term that just means a transformation between coalgebras that preserves structure. This makes it much easier to think about mapping classes onto other classes.

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

In short, an F-coalgebra represents a class by having a bunch of properties and methods that all depend on a self parameter containing each object's internal state.

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

So far, we've talked about algebras and coalgebras as Haskell types. An algebra is just a type τ with a function f τ → τ and a coalgebra is just a type τ with a function τ → f τ.

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

However, nothing really ties these ideas to Haskell per se. In fact, they're usually introduced in terms of sets and mathematical functions rather than types and Haskell functions. Indeed,we can generalize these concepts to any categories!

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

We can define an F-algebra for some category C. First, we need a functor F : C → C—that is, an endofunctor. (All Haskell Functors are actually endofunctors from Hask → Hask.) Then, an algebra is just an object A from C with a morphism F A → A. A coalgebra is the same except with A → F A.

考虑其他类别我们能获得什么?好吧，我们可以在不同的上下文中使用相同的想法.就像单子一样.在 Haskell 中，monad 是具有三个操作的 M ∷ ★ → ★ 类型:

What do we gain by considering other categories? Well, we can use the same ideas in different contexts. Like monads. In Haskell, a monad is some type M ∷ ★ → ★ with three operations:

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

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

The map function is just a proof of the fact that M is a Functor. So we can say that a monad is just a functor with two operations: return and join.

函子自己形成一个范畴，它们之间的态射是所谓的自然变换".自然变换只是将一个函子变换为另一个同时保留其结构的一种方式.这是一篇很好的文章，有助于解释这个想法.它讨论了 concat，它只是列表的 join.

Functors form a category themselves, with morphisms between them being so-called "natural transformations". A natural transformation is just a way to transform one functor into another while preserving its structure. Here's a nice article helping explain the idea. It talks about concat, which is just join for lists.

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

With Haskell functors, the composition of two functors is a functor itself. In pseudocode, we could write this:

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的转换.

This helps us think about join as a mapping from f ∘ f → f. The type of join is ∀α. f (f α) → f α. Intuitively, we can see how a function valid for all types α can be thought of as a transformation of f.

return 是一个类似的转换.它的类型是∀α.α → f α.这看起来不一样——第一个 α 不在函子中！令人高兴的是，我们可以通过在那里添加一个恒等函子来解决这个问题:∀α.恒等式α → f α.所以return是一个转换Identity → f.

return is a similar transformation. Its type is ∀α. α → f α. This looks different—the first α is not "in" a functor! Happily, we can fix this by adding an identity functor there: ∀α. Identity α → f α. So return is a transformation Identity → f.

现在我们可以将 monad 看作只是基于一些函子 f 的代数，带有操作 f ∘ f → f 和 Identity → f>.这看起来是不是很熟悉?它非常类似于幺半群，它只是某种类型的 τ，带有操作 τ × τ → τ 和 () → τ.

Now we can think about a monad as just an algebra based around some functor f with operations f ∘ f → f and Identity → f. Doesn't this look familiar? It's very similar to a monoid, which was just some type τ with operations τ × τ → τ and () → τ.

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

So a monad is just like a monoid, except instead of having a type we have a functor. It's the same sort of algebra, just in a different category. (This is where the phrase "A monad is just a monoid in the category of endofunctors" comes from as far as I know.)

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

Now, we have these two operations: f ∘ f → f and Identity → f. To get the corresponding coalgebra, we just flip the arrows. This gives us two new operations: f → f ∘ f and f → Identity. We can turn them into Haskell types by adding type variables as above, giving us ∀α. f α → f (f α) and ∀α. f α → α. This looks just like the definition of a comonad:

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

所以共谐子是一类内函子中的代数.

So a comonad is then a coalgebra in a category of endofunctors.

这篇关于“代数"是什么意思在编程的上下文中是什么意思?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！