“ coalgebra”在编程环境中是什么意思？

#1 楼

代数

我认为应该从理解代数的概念入手。这只是群，环，类群等代数结构的概括。大多数时候，这些东西都是以集合的形式介绍的，但是由于我们是朋友，所以我将讨论Haskell类型。 （不过，我无法抗拒使用一些希腊字母，它们使所有内容看起来都更酷！）这些函数采用不同数量的类型为τ的参数，并产生一个τ：未咖喱，它们看上去都像τ。它们也可以具有“身份”，即(τ, τ,…, τ) → τ的某些功能在某些行为上具有特殊的行为。

最简单的示例是类人动物。 Monoid是具有函数τ和标识τ的任何类型mappend ∷ (τ, τ) → τ。其他示例包括组（类似于monoid，除了具有额外的mzero ∷ τ函数），环，晶格等。我们可以将它们写为invert ∷ τ → τ，其中τ映射到τⁿ → τ q 4312079q的元组。这样，将身份视为τⁿ是有意义的，其中n只是空元组τ。因此，我们现在实际上可以简化代数的概念：它只是一种类型，上面有许多函数。我们使用代码。人们注意到，一大堆有趣的事物（上述的monoid，组，格子等）都遵循相似的模式，因此将其抽象出来。这样做的好处与编程相同：可以创建可重用的证明并简化某些推理。

F-代数

但是，我们还没有完全完成分解。到目前为止，我们有一堆函数τ⁰ → τ。实际上，我们可以做一个巧妙的技巧将它们全部组合成一个函数。特别地，让我们看一下monoid：我们有τ⁰和()。我们可以使用求和类型τⁿ → τ将它们转换为单个函数。看起来像这样：

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

对于任何代数，我们实际上可以重复使用此转换将所有mappend ∷ (τ, τ) → τ函数组合为一个函数。 （实际上，我们可以对任意数量的函数mempty ∷ () → τ，Either等执行此操作。）

这使我们将代数作为类型τⁿ → τ的单一函数从一些混乱的话题中讨论出来。将a → τ转换为单个b → τ。对于monoid，此混乱情况为：a, b,…;对于组（具有额外的τ操作），它是：Either。每个不同的结构都有不同的类型。那么所有这些类型有什么共同点？最明显的是，它们都是乘积之和-代数数据类型。例如，对于Monoid，我们可以创建一个适用于任何Monoidτ的monoid参数类型：

所有其他可能的结构。

所有这些类型还有什么特别之处？好吧，他们都是τ！例如：

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

所以我们可以进一步推广代数的概念。它只是带有函数Either (τ, τ) ()的某些τ → τ类型的函子Either (Either (τ, τ) τ) ()。实际上，我们可以将其写为类型类：如果我们可以部分应用类型类，则可以定义类似Functors的内容。

Coalgebras

现在，希望您能掌握什么是代数，以及它如何只是普通代数结构的推广。那么什么是F代数？好吧，co表示它是代数的“对偶”-也就是说，我们取一个代数并翻转一些箭头。我在上述定义中只看到一个箭头，因此我将其翻转：

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

就这样！现在，这个结论似乎有些浮躁（heh）。它可以告诉您什么是合并代数，但实际上并没有提供任何有用的见解或我们为何关心的见解。一旦找到或提出一个或两个很好的示例，便会讲到这一点：

类和对象

阅读了几篇之后，我认为我对如何使用合并代数表示类和对象有一个好主意。我们有一个τ类型，它包含该类中对象的所有可能的内部状态。该类本身是f τ → τ上的一个代数，它指定了对象的方法和属性。如代数示例所示，如果对于任何f我们都有一堆函数F和class Monoid = Algebra MonoidArgument，则使用求和类型C将它们组合成一个函数。双重“概念”将组合类型为C，a → τ等的一系列功能。我们可以使用总和类型（产品类型）的对偶来完成此操作。因此，鉴于上述两个函数（分别称为b → τ和a, b,…），我们可以创建一个像这样的单个函数：因此它确实符合我们的F-coalgebra概念。这个特殊的技巧使我们可以将一堆不同的函数（对于OOP来说，方法）打包成Either类型的单个函数。我们类型τ → a的元素表示对象的内部状态。如果对象具有某些可读属性，则它们必须能够依赖状态。最明显的方法是使它们具有τ → b的功能。因此，如果我们想要一个length属性（例如f），我们将有一个函数g。

我们需要可以接受参数并修改状态的方法。为此，我们需要采用所有参数并产生一个新的(a, a)。让我们想象一个τ → f τ方法，它采用一个C和一个C坐标：object.length。看起来像这样：C → Int。这里的重要模式是对象的“方法”和“属性”将对象本身作为第一个参数。就像Python中的C参数和许多其他语言的隐式setPosition一样。凝聚态本质上只是封装了采用x参数的行为：这就是y中第一个object.setPosition(1, 2)的含义。让我们想象一个具有C → ((Int, Int) → C)属性，self属性和this函数的类：

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

我们需要两部分来表示该类。首先，我们需要表示对象的内部状态；在这种情况下，它仅包含两个self和一个C。 （这是我们的类型C → F C。）然后，我们需要给出代表该类的合并代数。它们非常简单：

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

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

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

这就像带有显式position变量的Python类。现在我们有了一堆name函数，我们需要将它们组合成一个合并函数。我们可以使用一个简单的元组来做到这一点：

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

setPosition类型（对于任何Int而言）都是函子，因此String确实具有我们想要的形式：C。鉴于此，self与self →一起构成了一个定理，它指定了我上面给出的类。您可以看到我们如何使用这种相同的技术为对象指定任意数量的方法和属性。

这使我们可以使用联合代数推理处理类。例如，我们可以引入“ F-coalgebra同态”的概念来表示类之间的转换。这是一个令人生畏的冠冕堂皇的术语，仅表示在保持结构的各组成部分之间进行转换。简而言之，F-coalgebra通过具有一堆属性和方法来表示一个类，这些属性和方法都依赖于包含每个对象的((Int, Int), String, (Int, Int) → c)参数，这代表简化了将类映射到其他类的工作。内部状态。

其他类别

到目前为止，我们已经讨论过Haskell类型的代数和余代数。代数只是具有函数c的coop类型，而代数只是具有函数Functor f ⇒ C → f C的C类型。

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

我们可以为某个类别coop定义F代数。首先，我们需要一个函子self-即endofunctor。 （所有Haskell τ实际上都是来自f τ → τ的内爆字符。）然后，代数只是来自τ的同构τ → f τ的对象C。除F : C → C之外，余数是相同的。

通过考虑其他类别，我们可以获得什么？好吧，我们可以在不同的上下文中使用相同的想法。像单子。在Haskell中，单子是Functor的某种类型，具有三个操作：

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

Hask → Hask函数只是A是C的事实的证明。因此，我们可以说一个monad只是一个有两个运算的函子：q4​​312079q和F A → A。

函子本身构成一个类别，它们之间的态射是所谓的“自然变换”。自然转换只是在保留其函子的同时将一个函子转换为另一个函子的一种方法。这是一篇很好的文章，有助于解释这个想法。它讨论的是A → F A，对于列表来说只是M ∷ ★ → ★。

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

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

name ∷ C → String
name self = _name self

这有助于我们将map视为来自M的映射。 Functor的类型是return。直观地，我们可以看到对所有类型join有效的函数如何被视为concat的转换。

join是类似的转换。它的类型是join。这看起来有所不同-第一个f ∘ f → f不在函子中！幸运的是，我们可以通过在其中添加一个身份函子join来解决此问题。所以∀α. f (f α) → f α是一个α的变换。这看起来不熟悉吗？它非常类似于一个Monoid，它只是带有操作f和return的∀α. α → f α类型。

所以monad就像一个monoid一样，只是我们没有函子。这是同一种代数，只是类别不同。 （据我所知，“ monad在endofunctors类别中只是一个monoid”这句话来自这里。）

现在，我们有两个操作：α和∀α. Identity α → f α。要获得相应的gegebra，我们只需翻转箭头。这给了我们两个新的操作：return和Identity → f。通过添加上述类型变量，我们可以将它们转换为Haskell类型，分别为f和f ∘ f → f。这看起来像是共母的定义：

#2 楼

F代数和F代数是数学结构，可在推理归纳类型（或递归类型）时发挥作用。

F代数

我们首先从F开始-代数。我将尝试尽可能简单。

我想您知道什么是递归类型。例如，这是整数列表的类型：

data IntList = Nil | Cons (Int, IntList)

很明显，它是递归的-实际上，其定义指的是自身。它的定义由两个数据构造函数组成，这些数据构造函数具有以下类型：从理论的角度来看，这些实际上是等价的类型，因为Nil类型只有一个居民。 >

Nil  :: () -> IntList
Cons :: (Int, IntList) -> IntList

其中() -> IntList是一个单元集（带有一个元素的集合），而IntList操作是两组()和1（即，成对的A × B对的集合）的叉积通过A和B的所有元素都遍历(a, b)的所有元素。本质上，它是a和A的所有元素的集合，但是每个元素都被“标记”为b或B的元素，因此，当我们从A中选择任何元素时，我们将立即知道该元素是否来自B或从A | B开始。

我们可以“连接” {(a, 1) : a in A}和{(b, 2) : b in B}函数，因此它们将在一个A集合上形成单个函数：
>确实，如果将B函数应用于A值（显然属于B集），则其行为就好像是A | B一样；如果将A应用于B类型的任何值（此类值也位于Nil集合中，则其行为与Cons相同。 >
它具有以下构造函数：

Nil  :: 1 -> IntList
Cons :: Int × IntList -> IntList

它也可以连接到一个函数中：
可以看出，这两个1 | (Int × IntList)函数的类型相似：它们看起来都像
并给出更复杂的类型，包括Nil|Cons和()操作，1 | (Int × IntList)的用法以及其他可能的类型，例如，对于Nil和Nil|Cons，(Int, IntList)如下所示：

Nil|Cons :: 1 | (Int × IntList) -> IntList

>我们立即注意到可以用这种方式写任何代数类型，的确，这就是为什么它们被称为“代数”的原因：它们由多个“和”（联合）和“乘积”（叉积）组成其他类型。

现在我们可以定义F代数了。 F代数只是一对1 | (Int × IntList)，其中Cons是某种类型，joined是F类型的函数。在我们的示例中，F代数是x和|。但是请注意，尽管每种F的T函数类型相同，但IntList和IntTree本身可以是任意的。例如，某些F和(T, f)的T或f也是对应F的F代数。实际上，f :: F T -> T是初始F1代数，而(IntList, Nil|Cons)是初始F2代数。我不会提供这些术语和属性的确切定义，因为它们比所需的更为复杂和抽象。

但是，例如(IntTree, Leaf|Branch)是F代数的事实使我们可以在这种类型上定义类似f的函数。如您所知，fold是一种将一个递归数据类型转换为一个有限值的操作。例如，我们可以将整数列表折叠为一个单个值，该值是列表中所有元素的总和：

data IntTree = Leaf Int | Branch (IntTree, IntTree)

可以在任何递归数据类型。

以下是T函数的签名：

Leaf   :: Int -> IntTree
Branch :: (IntTree, IntTree) -> IntTree

请注意，我已经使用花括号将前两个参数与最后一个。这不是真正的f函数，但是它是同构的（也就是说，您可以轻松地从另一个函数中获取一个，反之亦然）。部分应用的(String, g :: 1 | (Int x String) -> String)将具有以下签名：

Leaf|Branch :: Int | (IntTree × IntTree) -> IntTree

我们可以看到，这是一个接受整数列表并返回单个整数的函数。让我们根据我们的(Double, h :: Int | (Double, Double) -> Double)类型来定义此类函数。第二部分定义函数在g部分上的行为。类型通过元组和h数据类型，但这将导致不必要的冗长。考虑一个函数：

f :: F T -> T

可以看出(IntList, Nil|Cons)是(IntTree, Leaf|Branch)类型的函数，就像F-代数的定义一样！实际上，对(IntList, Nil|Cons)是F1代数。

由于fold是初始的F1代数，因此对于每种类型foldr和每种函数foldr，都有一个称为foldr的同态的函数，它将IntList转换为Nil，并且该函数是唯一的。实际上，在我们的示例中，IntList的同构是Cons。请注意Either a b和reductor的相似之处：它们的结构几乎相同！在F1 Int -> Int定义中，(Int, reductor)参数的用法（其类型对应于IntList）对应于T定义中r :: F1 T -> T的计算结果的用法。

只是为了使其更清楚并帮助您查看模式，此处是另一个示例，我们再次从生成的折叠函数开始。考虑将第一个参数附加到第二个参数的r函数：

F1 T = 1 | (Int × T)
F2 T = Int | (T × T)

这在我们的IntList上看起来是这样的：
再次，让我们尝试写出减速器：

foldr (+) 0 [1, 2, 3, 4] -> 1 + 2 + 3 + 4 = 10

是


T是reductor的变种，它将sumFold转换为reductor。 >因此，从本质上讲，F代数允许我们在递归数据结构上定义“折叠”，即，将我们的结构缩减至一定值的运算。

F-coalgebras

F-代数是F-代数的所谓“双重”术语。它们使我们能够为递归数据类型定义sumFold，即一种从某些值构造递归结构的方法。

假设您具有以下类型：

foldr :: ((a -> b -> b), b) -> [a] -> b

这是一个无限的整数流。其唯一的构造函数具有以下类型：

foldr ((+), 0) :: [Int] -> Int

或者就集合而言

sumFold :: IntList -> Int
sumFold Nil         = 0
sumFold (Cons x xs) = x + sumFold xs

Haskell允许您可以在数据构造函数上进行模式匹配，因此可以定义对reductor s起作用的以下函数：

reductor :: () | (Int × Int) -> Int
reductor ()     = 0
reductor (x, s) = x + s

您自然可以将这些函数“联接”为单个类型的函数s：

(append [4, 5, 6]) [1, 2, 3] = (foldr (:) [4, 5, 6]) [1, 2, 3] -> [1, 2, 3, 4, 5, 6]

请注意，函数的结果如何与我们的T类型的代数表示相一致。对于其他递归数据类型，也可以执行类似的操作。也许您已经注意到了这种模式。我指的是类型为

appendFold :: IntList -> IntList -> IntList
appendFold ys ()          = ys
appendFold ys (Cons x xs) = x : appendFold ys xs

的一系列函数，其中sumFold xs是某种类型。从现在开始，我们将定义

appendReductor :: IntList -> () | (Int × IntList) -> IntList
appendReductor ys ()      = ys
appendReductor ys (x, rs) = x : rs

现在，F-coalgebra是一对sumFold，其中append是类型，而IntList是appendFold的函数。例如，appendReductor是F1代数。同样，就像在F代数中一样，IntList和IntList可以是任意的，例如，unfolds也是对于某些h的F1代数。 -代数，与初始F代数对偶。例如，IntStream是终端F-coalgebra。这意味着对于每种类型的IntStream -> Int × IntStream和每种函数IntStream，都有一个称为变形的函数，它将T转换为(T, g)，并且该函数是唯一的。从给定的整数开始的连续整数：

data IntStream = Cons (Int, IntStream)

现在让我们检查一个函数T，即g：

Cons :: (Int, IntStream) -> IntStream

再次，我们可以看到g :: T -> F T和(IntStream, head&tail)之间有些相似之处。这非常类似于我们之前观察到的与减速器和折页的连接。 g是T的变形。

另一个示例是一个函数，该函数接受一个值和一个函数，并将该函数的连续应用流返回给该值：



其生成器功能如下：

Cons :: Int × IntStream -> IntStream

然后(String, h :: String -> Int x String)是IntStream的变形。

结论

因此，简而言之，F代数允许定义折叠，即将递归结构降低为单个值的运算，而F代数允许相反的操作：从单个值构造一个[潜在的]无限结构。 br />
实际上在Haskell中F代数和F代数是重合的。这是一个非常不错的属性，这是每种类型中都存在“底”值的结果。因此，在Haskell中，可以为每种递归类型创建折叠和展开。但是，其背后的理论模型比我上面介绍的模型更复杂，因此我特意避免了它。

希望有帮助。

#3 楼

阅读本教程纸有关（共）代数和（共）归纳的教程应该使您对计算机科学中的共代数有一些了解。 />

一般而言，某种编程语言中的程序会处理数据。在过去几十年的计算机科学发展过程中，很明显，需要对这些数据进行抽象的描述，例如，确保一个人的程序不依赖于数据的特定表示形式。它运作。同样，这种抽象性有助于正确性证明。
这种愿望导致了在代数规范或抽象数据类型理论这一分支中计算机科学中代数方法的使用。研究的对象本身就是数据类型，使用的是代数熟悉的技术概念。计算机科学家使用的数据类型通常是从​​给定的（构造函数）操作集合中生成的，正是由于这个原因，代数的“初始化”扮演了如此重要的角色。
标准代数技术已被证明对捕获数据很有用计算机科学中使用的数据结构的各个基本方面。但是事实证明，很难用代数方式描述计算中出现的某些固有动力学结构。这种结构通常涉及状态的概念，可以以多种方式对其进行转换。这种基于状态的动力系统的形式化方法通常利用自动机或过渡系统，作为经典的早期参考书。
在过去的十年中，越来越多的人逐渐意识到，这种基于状态的系统不应被描述为代数，而应被称为共同代数。这些是代数的形式对偶，在本教程中将对此进行精确说明。代数的“初始性”的双重属性，即最终性，对于这类共同代数至关重要。这样的最终共代数所需要的逻辑推理原理不是归纳而是共归纳。




关于范畴论的前奏。
范畴论应该是函子的重命名理论。
因为类别是定义函子必须定义的内容。
（此外，函子是定义自然变换必须定义的东西。）

什么是函子？
是从一组到另一组的变换，保留了它们的结构。
（有关详细信息，网上有很多很好的描述）。

什么是F代数？
是函子的代数。
这只是对函子的通用性的研究。

如何与计算机科学联系起来
程序可以看作是结构化的信息集。
程序的执行对应于对该结构化信息集的修改。
执行应该保留程序的结构。 >然后xecution可以看作是函子在这组信息上的应用。
（定义程序的函数）。

为什么F-co-algebra？
程序是双重的从本质上讲，它们是由信息描述并对其起作用。可以定义为程序正在处理的信息。
可以定义为程序正在共享的信息的状态。

然后在这个阶段，我想说的是，


F-代数是作用于Data宇宙的函子变换的研究（如此处定义）。
F-代数是作用于国家的宇宙的函子变换的研究（如此处定义）。

在程序的生命周期中，数据和状态共存，并且它们彼此互补。
它们是双重的。

#4 楼

我将从明显与编程相关的东西开始，然后添加一些数学的东西，以使其尽可能具体具体。


让我们引用一些计算机专家关于共生的看法...

http://www.cs.umd.edu/~micinski/posts/2012-09-04-on-understanding-coinduction.html


归纳涉及有限数据，共归纳涉及无限数据。

无限数据的典型示例是惰性列表的类型（a
流）。例如，假设我们在
内存中有以下对象：

 let (pi : int list) = (* some function which computes the digits of
 π. *)

计算机无法容纳全部的π，因为它只有有限的
内存！但是它可以做的是持有一个有限程序，该程序会产生所需的任意任意长的π展开。只要您仅使用列表的有限部分，就可以根据需要使用该列表无限计算。

但是，请考虑以下程序：

let print_third_element (k : int list) =   match k with
     | _ :: _ :: thd :: tl -> print thd


 print_third_element pi

该程序应打印pi的第三位。但是在某些语言中，对函数的任何参数的评估都是在将参数传递给函数之前进行的（严格的而不是惰性的评估）。如果我们使用此
降序，那么我们上面的程序将永远运行pi的
数字，然后将其传递给我们的打印机功能（这不会发生）。由于计算机没有无限的内存，
程序最终将耗尽内存并崩溃。这可能不是最佳的评估顺序。


http://adam.chlipala.net/cpdt/html/Coinductive.html


在像Haskell这样的惰性函数式编程语言中，无处不在的数据结构
无处不在。无限列表和更多奇特的数据类型为程序各部分之间的通信提供了方便的抽象。实现类似
在许多情况下，没有无限惰性结构的便利将需要控制流的杂技反转。


http://www.alexandrasilva.org/#/talks.html



将环境数学上下文与常规编程任务相关

什么是“代数”？通常看起来像：


东西
东西可以做什么

这听起来像带有1.属性和2.方法的对象。甚至更好，它听起来应该像类型签名。 Monoid就像自动机：动词序列（例如f.g.h.h.nothing.f.g.f）。始终添加历史记录而从未删除它的git日志将是一个monoid，而不是一个组。如果添加反函数（例如，负数，分数，根，删除累积的历史记录，破碎破碎的镜像），则会得到一个组。

组包含可以相加或相减的事物。例如，可以将Duration一起添加。 （但是Date不能。）持续时间存在于向量空间（不仅仅是一组）中，因为它们也可以由外部数字缩放。 （scaling :: (Number,Duration) → Duration的类型签名。）

代数⊂向量空间还可以做另一件事：有一些m :: (T,T) → T。之所以称其为“乘法”，是因为不要，因为一旦离开Integers，“乘”（或“乘幂”）应该是什么就不那么明显了。 ）通用属性：告诉他们应该做哪些乘法或像什么：


）


代数→代数代数

与乘法相比，以乘法为准的方法更容易定义非乘法，因为从T → (T,T)开始，您可以重复同一元素。 （“对角图” –就像光谱理论中的对角矩阵/算符一样）

Counit通常是迹线（对角线项的总和），尽管同样重要的是Counit的功能。 trace只是矩阵的一个很好的答案。

之所以通常要看一个对偶空间，是因为在该空间中思考更容易。例如，有时考虑法线矢量要比考虑法线平面更容易，但是您可以使用矢量控制平面（包括超平面）（现在我正在谈论熟悉的几何矢量，例如在光线跟踪器中） 。


处理（非）结构化数据

数学家可能正在建模一些有趣的东西，例如TQFT，而程序员必须与之搏斗


日期/时间（+ :: (Date,Duration) → Date），
位置（Paris≠(+48.8567,+2.3508)！这是形状，而不是点。），
在某种意义上应该是一致的非结构化JSON，
错误但紧密的XML，
应满足合理关系负荷的极其复杂的GIS数据，
正则表达式对您来说意味着一些意义，但对perl而言意义不大。保留所有高管的电话号码和别墅位置，他（现在是前任）妻子和孩子的名字，生日以及以前所有的礼物，每一个礼物都应满足“明显”的关系（明显对客户而言），这很难编写，
......

计算机科学家在谈论“代数”时，通常会想到设置操作，例如笛卡尔积。我相信这就是人们说“代数就是Haskell中的代数”的意思。但是在一定程度上，程序员必须对Place，Date/Time和Customer之类的复杂数据类型进行建模，并使这些模型看起来尽可能像真实世界（或者至少是最终用户对真实世界的看法），相信对偶，可能不仅限于设定范围。