“代数”在编程中意味着什么？
在函数式编程和PLT圈子中，我多次听到“coalgebras”这个术语，特别是当讨论关于物体，连接器，镜头等时。 谷歌搜索这个术语给出了这些结构的数学描述，这对我来说是非常难以理解的。 任何人都可以解释在编程环境中什么是合数的意思，它们的意义是什么，它们如何与对象和连接器相关联？
代数
我认为开始的地方应该是理解代数的思想。 这只是代数结构的一般化，比如组，环，monids等等。 大多数情况下，这些东西都是以集合的形式介绍的，但由于我们是朋友之间的关系，所以我会讨论一下Haskell类型。 （尽管我使用了一些希腊字母，但我无法抗拒 - 它们使一切看起来更酷！）
那么代数就是一个具有一些函数和特性的τ类型。 这些函数采用不同数量的类型τ的参数，并产生一个τ ：不感冒，它们都看起来像(τ, τ,…, τ) → τ 。 它们也可以具有“身份” - 具有某些功能的特殊行为的τ元素。
最简单的例子就是monoid。 幺半群是任何类型的τ与函数mappend ∷ (τ, τ) → τ和身份mzero ∷ τ 。 其他的例子包括像群组（它们就像单撇子除了有一个额外的invert ∷ τ → τ函数），环，格子等。
所有功能都在τ运行，但可以有不同的属性。 我们可以写这些出来作为τⁿ → τ ，其中τⁿ映射到的元组n τ 。 这样，将身份考虑为τ⁰ → τ是τ⁰ → τ ，其中τ⁰只是空元组() 。 所以我们实际上可以简化一个代数的思想：它只是一些类型，其上有许多函数。
代数只是数学中的一个常见模式，它被“分解”了，就像我们用代码一样。 人们注意到一大堆有趣的东西 - 前面提到的monoids，groups，lattice等 - 都遵循类似的模式，所以他们把它抽象出来。 这样做的好处与编程相同：创建可重复使用的证明并使某些推理更容易。
F-代数
但是，我们还没有完成保理业务。 到目前为止，我们有一堆函数τⁿ → τ 。 我们实际上可以做一个巧妙的窍门，将它们全部组合成一个功能。 尤其是，我们来看一下mappend ∷ (τ, τ) → τ ：我们有mappend ∷ (τ, τ) → τ和mempty ∷ () → τ 。 我们可以使用总和类型将它们变成单个函数 - Either 。 它看起来像这样：
op ∷ Monoid τ ⇒ Either (τ, τ) () → τ
op (Left (a, b)) = mappend (a, b)
op (Right ()) = mempty
对于任何代数，我们实际上可以反复使用这种变换将所有的τⁿ → τ函数合并成一个单一函数。 （事实上，对于任何a, b,… ，我们都可以对任意数量的函数a → τ ， b → τ等进行此操作。）
这让我们谈论代数作为一种τ从一些乱七八糟的单一功能Either s到一个单一的τ 。 对于monoids，这个混乱是： Either (τ, τ) () ; 对于组（有一个额外的τ → τ操作），它是：（ Either (Either (τ, τ) τ) () 。 对于不同的结构来说，这是一种不同的类型。 那么所有这些类型有什么共同点？ 最明显的是它们都是产品的代数 - 代数数据类型。 例如，对于monoids，我们可以创建一个monoid参数类型，适用于任何单态τ：
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代数？ 那么，它意味着它是代数的“双重” - 也就是说，我们需要一个代数并翻转一些箭头。 我只在上面的定义中看到一个箭头，所以我只是翻转一下：
class Functor f ⇒ CoAlgebra f τ where
coop ∷ τ → f τ
就是这样！ 现在，这个结论可能看起来有些轻浮（heh）。 它告诉你什么是代数，但并没有真正了解它是如何有用或为什么我们关心。 一旦我找到或提出一个或两个很好的例子，我会做到这一点：P。
类和对象
在阅读了一下后，我想我对如何使用代数来表示类和对象有了一个好主意。 我们有一个类型C ，它包含类中所有可能的对象内部状态; 该类本身是C上的一个代数，它指定了对象的方法和属性。
如代数示例所示，如果我们有一堆函数，如a → τ和b → τ对于任何a, b,… ，我们可以将它们全部组合成一个函数，使用Either ，一个和类型。 双“概念”将结合τ → a ， τ → b等一系列函数。 我们可以使用总和类型（一种产品类型）的对偶来实现这一点。 因此，考虑到上述两个函数（称为f和g ），我们可以创建一个如下所示的函数：
both ∷ τ → (a, b)
both x = (f x, g x)
类型(a, a)是一种简单的函数，所以它肯定符合我们对F代数的概念。 这个特殊的技巧让我们把一堆不同的函数打包成一个单一的τ → f τ函数。
我们类型C的元素表示对象的内部状态。 如果对象具有一些可读属性，则它们必须能够依赖于状态。 最明显的做法是让它们成为C的函数。 所以如果我们想要一个长度属性（例如object.length ），我们将有一个函数C → Int 。
我们需要可以接受参数和修改状态的方法。 要做到这一点，我们需要采取所有的论据，并产生一个新的C 我们来想象一个带有x和y坐标的setPosition方法： object.setPosition(1, 2) 。 它看起来像这样： C → ((Int, Int) → C) 。
这里的重要模式是对象的“方法”和“属性”将对象本身作为第一个参数。 这就像self在Python参数和喜欢的隐性this许多其他语言的。 一个代数基本上只是封装了一个self参数的行为：这就是C → FC的第一个C
所以我们把它放在一起。 让我们想象一个具有position属性， name属性和setPosition函数的类：
class C
private
x, y : Int
_name : String
public
name : String
position : (Int, Int)
setPosition : (Int, Int) → C
我们需要两个部分来表示这个类。 首先，我们需要表示对象的内部状态; 在这种情况下，它只包含两个Int和一个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-余代数同态”的概念来表示类之间的转换。 这是一个令人恐惧的测试术语，它仅仅意味着保留结构的余代之间的转换。 这使得考虑将类映射到其他类更容易。
简而言之，F代数代表了一类，它拥有一系列属性和方法，这些属性和方法都依赖于包含每个对象内部状态的self参数。
其他类别
到目前为止，我们已经将代数和余代数描述为Haskell类型。 一个代数仅仅是一个类型τ与函数f τ → τ和一个余代数只是一个类型τ与函数τ → f τ 。
但是，没有什么能够将这些想法与Haskell本身结合在一起。 实际上，它们通常是以集合和数学函数的形式来引入的，而不是类型和Haskell函数。 的确，我们可以将这些概念概括为任何类别！
我们可以为某个类别C定义一个F-代数。 首先，我们需要一个仿函数F : C → C即，一个内核函数。 （所有的Haskell Functor实际上都是Hask → Hask 。）然后，代数就是C一个对象A ，其态射FA → A 。 除了A → FA之外，余代数是相同的。
考虑其他类别我们会获得什么？ 那么，我们可以在不同的情况下使用相同的想法。 像单子一样。 在Haskell中，monad是一些M ∷ ★ → ★类型的三种操作：
map ∷ (α → β) → (M α → M β)
return ∷ α → M α
join ∷ M (M α) → M α
map功能仅仅是M是Functor这一事实的证明。 所以我们可以说monad只是一个有两个操作的函数： return和join 。
函子本身就是一个类别，它们之间的态射是所谓的“自然变换”。 自然变换只是将一个仿函数转换成另一个仿函数的一种方式，同时保留其结构。 这是一篇很好的文章，有助于解释这个想法。 它讨论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 (f α) → f α 。 直观地说，我们可以看到，对于所有类型α有效的函数如何被认为是f的变换。
return是一个类似的转换。 它的类型是∀α. α → f α ∀α. α → f α 。 这看起来不同 - 第一个α不是“在”函数中！ 令人高兴的是，我们可以通过在那里添加一个身份∀α. Identity α → f α函数来解决这个问题： ∀α. Identity α → f α ∀α. Identity α → f α 。 所以return是一个转换Identity → f 。
现在我们可以将monad看作是一个基于某个函数f的代数，运算f ∘ f → f且Identity → f 。 这看起来不熟悉吗？ 它与幺半群非常相似，它只是一些类型τ ，其中τ × τ → τ和() → τ 。
所以monad就像一个monoid，除了有一个类型我们有一个函数。 这是同一种代数，只是属于不同的类别。 （就我所知，这就是“单子只是内生元的类别中的幺半群”一词的来源。）
现在，我们有这两个操作： f ∘ f → f和Identity → f 。 为了得到相应的余代数，我们只需要翻转箭头。 这给了我们两个新的操作： f → f ∘ f和f → Identity 。 我们可以通过添加类型变量将它们变成Haskell类型，给我们提供∀α. f α → f (f α) ∀α. f α → α ∀α. f α → f (f α) ∀α. f α → α ∀α. f α → f (f α)和∀α. f α → α ∀α. f α → α 。 这看起来就像comonad的定义：
class Functor f ⇒ Comonad f where
coreturn ∷ f α → α
cojoin ∷ f α → f (f α)
因此，一个共同体是一个内部管理者范畴的代数。
F-代数和F-代数是推理归纳类型（或递归类型）的数学结构。
F-代数
我们首先用F-algebras开始。 我会尽量做到尽可能简单。
我猜你知道什么是递归类型。 例如，这是一个整数列表的类型：
data IntList = Nil | Cons (Int, IntList)
很显然它是递归的 - 事实上，它的定义是指它自己。 其定义由两个数据构造函数组成，它们具有以下类型：
Nil :: () -> IntList
Cons :: (Int, IntList) -> IntList
请注意，我写了Nil as () -> IntList ，而不是简单的IntList 。 事实上，从理论的角度来看，这些实际上是相同的类型，因为()类型只有一个居民。
如果我们以更理论的方式写这些函数的签名，我们会得到
Nil :: 1 -> IntList
Cons :: Int × IntList -> IntList
其中1是一个单位集合（设置一个元素）， A × B操作是两个集合A和B的交叉乘积（也就是，一组对(a, b) ，其中a经过A和b所有元素通过B ）的所有元素。
两个集合A和B不相交联合是集合A | B A | B是{(a, 1) : a in A} {(b, 2) : b in B} {(a, 1) : a in A}的集合{(a, 1) : a in A}和{(b, 2) : b in B} {(a, 1) : a in A}集合。 本质上它是一组来自A和B的所有元素，但是每个这些元素都被标记为属于A或B ，所以当我们从A | B选择任何元素时， A | B我们会立即知道这个元素是来自A还是来自B
我们可以'加入' Nil和Cons函数，因此它们将形成一个集合1 | (Int × IntList)函数 1 | (Int × IntList) ：
Nil|Cons :: 1 | (Int × IntList) -> IntList
事实上，如果Nil|Cons函数应用于()值（显然，它属于1 | (Int × IntList)集合），那么它的行为就好像它是Nil ; 如果Nil|Cons应用于任何类型的值(Int, IntList) （这些值也在集合1 | (Int × IntList) ，则它表现为Cons 。
现在考虑另一种数据类型：
data IntTree = Leaf Int | Branch (IntTree, IntTree)
它有以下构造函数：
Leaf :: Int -> IntTree
Branch :: (IntTree, IntTree) -> IntTree
其中也可以加入一个功能：
Leaf|Branch :: Int | (IntTree × IntTree) -> IntTree
可以看出，这两个joined函数具有相似的类型：它们都是相似的
f :: F T -> T
其中F是一种转换，它采用我们的类型并给出更复杂的类型，它由x和| 操作， T用法以及可能的其他类型。 例如，对于IntList和IntTree F外观如下所示：
F1 T = 1 | (Int × T)
F2 T = Int | (T × T)
我们可以立即注意到，任何代数类型都可以用这种方式编写。 实际上，这就是为什么他们被称为“代数”的原因：它们包括一些其他类型的“总和”（联合）和“产品”（交叉产品）。
现在我们可以定义F-代数。 F-代数只是一对(T, f) ，其中T是某种类型， f是f :: FT -> T的函数。 在我们的例子中，F-algebras是(IntList, Nil|Cons)和(IntTree, Leaf|Branch) 。 然而，请注意，尽管f函数的类型对于每个F都是相同的，但T和f本身可以是任意的。 例如，对于某些g和h ， (String, g :: 1 | (Int x String) -> String)或(Double, h :: Int | (Double, Double) -> Double)也是对应的F-代数F。
之后，我们可以引入F-代数同态，然后引入具有非常有用属性的初始F-代数。 事实上， (IntList, Nil|Cons)是一个初始的F1代数， (IntTree, Leaf|Branch)是一个初始的F2代数。 我不会提供这些术语和属性的确切定义，因为它们比需要的更加复杂和抽象。
尽管如此，例如(IntList, Nil|Cons)是F代数的事实允许我们在这种类型上定义fold类功能。 如你所知，fold是一种将某种递归数据类型转换为一个有限值的操作。 例如，我们可以将整数列表折叠为单个值，该值是列表中所有元素的总和：
foldr (+) 0 [1, 2, 3, 4] -> 1 + 2 + 3 + 4 = 10
可以在任何递归数据类型上推广这样的操作。
以下是foldr函数的签名：
foldr :: ((a -> b -> b), b) -> [a] -> b
请注意，我使用大括号来分隔最后一个参数的前两个参数。 这不是真正的foldr函数，但它是同构的（也就是说，你可以很容易地从另一个中得到一个，反之亦然）。 部分应用的foldr将具有以下签名：
foldr ((+), 0) :: [Int] -> Int
我们可以看到这是一个函数，它接受一个整数列表并返回一个整数。 我们用我们的IntList类型来定义这样的函数。
sumFold :: IntList -> Int
sumFold Nil = 0
sumFold (Cons x xs) = x + sumFold xs
我们看到这个函数由两部分组成：第一部分在IntList Nil部分上定义了这个函数的行为，第二部分在Cons部分上定义了函数的行为。
现在假设我们不是在Haskell中编程，而是在某种语言中允许直接在类型签名中使用代数类型（从技术上讲，Haskell允许通过元组使用代数类型， Either ab数据类型，但这会导致不必要的冗长）。 考虑一个函数：
reductor :: () | (Int × Int) -> Int
reductor () = 0
reductor (x, s) = x + s
可以看出， reductor是类型F1 Int -> Int的函数，就像F代数的定义一样！ 事实上，这个对(Int, reductor)是一个F1代数。
因为IntList是初始F1-代数，对于每种类型T和每个功能r :: F1 T -> T存在的函数，称为catamorphism为r它转换IntList至T ，并且这样的功能是唯一的。 事实上，在我们的例子中， reductor的sumFold是sumFold 。 注意如何reductor和sumFold是相似的：它们有几乎相同的结构！ 在reductor定义s参数用法（其类型对应于T ）对应于计算结果的使用sumFold xs在sumFold定义。
只是为了让它更清晰，并帮助您看到图案，这里是另一个例子，我们再次从所得折叠函数开始。 考虑append函数，它将第一个参数附加到第二个参数：
(append [4, 5, 6]) [1, 2, 3] = (foldr (:) [4, 5, 6]) [1, 2, 3] -> [1, 2, 3, 4, 5, 6]
这在我们的IntList看起来如何：
appendFold :: IntList -> IntList -> IntList
appendFold ys () = ys
appendFold ys (Cons x xs) = x : appendFold ys xs
再次，我们试着写出减速器：
appendReductor :: IntList -> () | (Int × IntList) -> IntList
appendReductor ys () = ys
appendReductor ys (x, rs) = x : rs
appendFold为catamorphism appendReductor其将IntList成IntList 。
因此，本质上，F-代数允许我们在递归数据结构上定义'折叠'，即将我们的结构减少到一定价值的操作。
F-余代数
F-代数是所谓F-代数的“双重”项。 它们允许我们为递归数据类型定义unfolds ，也就是从某种价值构造递归结构的方式。
假设你有以下类型：
data IntStream = Cons (Int, IntStream)
这是一个无限的整数流。 它唯一的构造函数具有以下类型：
Cons :: (Int, IntStream) -> IntStream
或者，就集合而言
Cons :: Int × IntStream -> IntStream
Haskell允许您在数据构造函数上进行模式匹配，因此您可以定义以下用于IntStream的函数：
head :: IntStream -> Int
head (Cons (x, xs)) = x
tail :: IntStream -> IntStream
tail (Cons (x, xs)) = xs
您可以将这些函数自然地“加入” IntStream -> Int × IntStream类型的单个函数IntStream -> Int × IntStream ：
head&tail :: IntStream -> Int × IntStream
head&tail (Cons (x, xs)) = (x, xs)
注意函数的结果与IntStream类型的代数表示是否一致。 对于其他递归数据类型也可以做类似的事情。 也许你已经注意到了这种模式。 我指的是一个类型的函数族
g :: T -> F T
其中T是某种类型。 从现在起我们将定义
F1 T = Int × T
现在，F-代数是一对(T, g) ，其中T是一个类型， g是g :: T -> FT的函数。 例如， (IntStream, head&tail)是一个F1代数。 同样，就像在F代数中一样， g和T可以是任意的，例如(String, h :: String -> Int x String)也是一些h的F1代数。
在所有F-余代数中，有所谓的终端F-余代数，它与初始F-代数是双重的。 例如， IntStream是一个终端F代数。 这意味着对于每个类型T和每个函数p :: T -> F1 T ，都存在一个称为anamorphism的函数，它将T转换为IntStream ，并且此函数是唯一的。
考虑下面的函数，它从给定的一个开始产生连续的整数流：
nats :: Int -> IntStream
nats n = Cons (n, nats (n+1))
现在我们natsBuilder :: Int -> F1 Int一个函数natsBuilder :: Int -> F1 Int ，也就是natsBuilder :: Int -> Int × Int ：
natsBuilder :: Int -> Int × Int
natsBuilder n = (n, n+1)
再次，我们可以看到nats和natsBuilder之间的一些相似之处。 这与我们之前观察到的还原剂和褶皱的连接非常相似。 nats是natsBuilder的变形。
另一个例子是一个函数，它接受一个值和一个函数，并将该函数的连续应用程序流返回给该值：
iterate :: (Int -> Int) -> Int -> IntStream
iterate f n = Cons (n, iterate f (f n))
它的构建器功能如下：
iterateBuilder :: (Int -> Int) -> Int -> Int × Int
iterateBuilder f n = (n, f n)
然后iterate是iterateBuilder的变形。
结论
因此，简而言之，F-代数允许定义折叠，也就是说，将递归结构减少为单一值的操作，而F-代数则可以做相反的事情：从单个值构造一个[潜在]无限结构。
事实上，在Haskell F-代数和F-代数一致。 这是一个非常好的属性，它是每种类型中“最低”值的结果。 所以在Haskell中，可以为每个递归类型创建折叠和展开。 然而，这背后的理论模型比我上面介绍的模型更复杂，所以我故意避免了这个模型。
希望这可以帮助。
阅读教程论文关于（共）代数和（共）归纳的教程应该给你一些关于计算机科学中的联合代数的见解。
下面是引用它来说服你，
一般而言，某些编程语言中的程序操纵数据。 在过去几十年计算机科学的发展过程中，很明显，对这些数据的抽象描述是可取的，例如，以确保一个人的计划不依赖于其运行数据的特定表示。 而且，这种抽象性有利于证明正确性。
这种愿望导致在计算机科学中使用代数方法，在称为代数规范或抽象数据类型理论的分支中。 研究对象本身就是数据类型，使用代数熟悉的技术概念。 计算机科学家使用的数据类型通常是由给定的（构造函数）操作集合生成的，因此，代数的“初始性”扮演着非常重要的角色。
标准的代数技术已经证明在捕获计算机科学中使用的数据结构的各种基本方面是有用的。 但事实证明，用代数方法很难描述计算中出现的一些固有的动态结构是很困难的。 这种结构通常涉及国家概念，可以通过各种方式进行转变。 这种基于状态的动力系统的形式化方法通常使用自动机或过渡系统作为经典的早期参考。
在过去的十年里，人们逐渐认识到，这种基于状态的系统不应该被描述为代数，而应该被称为所谓的共同代数。 这些是代数的形式对偶，在本教程中将以精确的方式进行。 代数的“初始性”的双重属性，即最终结果对于这样的共同代数是至关重要的。 而这种最终的共同代数所需要的逻辑推理原则并不是归纳而是共诱导。
前奏，关于分类理论。 分类理论应该是函子的重命名理论。 由于类别是定义函数所必须定义的。 （此外，函数是为了定义自然变换必须定义的。）
什么是仿函数？ 这是一个从一套到另一套保持其结构的转变。 （更多细节在网上有很多很好的描述）。
什么是F代数？ 它是仿函数的代数。 这只是研究函子的普遍适用性。
它如何可以链接到计算机科学？ 程序可以被视为一组结构化的信息。 程序的执行对应于对这组结构化信息的修改。 执行应该保留程序结构听起来不错。 然后，可以将执行视为应用函子对这组信息。 （定义程序的人）。
为什么F-co-algebra？ 程序本质上是双重的，因为它们是通过信息来描述的，而且它们是以此为依据。 然后主要是构成程序并使它们改变的信息可以以两种方式查看。
然后在这个阶段，我想说，
在程序的生命周期中，数据和状态并存，并且彼此完成。 他们是双重的。
链接地址: http://www.djcxy.com/p/43011.html上一篇: What does "coalgebra" mean in the context of programming?
下一篇: Wadler, "Monads for Functional Programming," Section 2.8