余代数和自动机

# 余代数与自动机 来源：https://web.archive.org/web/20071014215938/http://homepage.mac.com/sigfpe/Computing/fold.html Wayback Machine \- https://web\.archive\.org/web/20071014215938/http://homepage\.mac\.com:80/sigfpe/Computing/fold\.html `` 余代数与自动机 ----------------------- 本文档是文学化Haskell，这意味着它混合了实际可运行的代码和注释。 （此网页曾用错误标题。它与数据类型的微分无关，且不适用于非函数式程序员。） （另外，我后来了解到，下面所有fold和unfold的定义可以合并为一对定义。参见，例如：http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/hodgp.pdf） 本文档的非HTML化版本可在以下地址获取： http://www.sigfpe.com/Computing/fold.lhs 你可以在hugs或ghc中运行它。 引言 ------------ 许多年前，我尝试为有限状态自动机编写代码。我想写一个函数，它接受状态标签和输入，然后返回一个新的状态标签。但后来我疑惑状态标签的意义何在。难道我不能直接写一个函数，它接受某些输入，然后返回另一个相同类型的函数吗？换句话说，我想要一个类型X，使得X = A -> X。总之，我当时觉得这也许有点反常，便忽略了这个问题多年。但后来我尝试玩转fold和unfold的推广，惊讶地发现这个类型以一种非常自然的方式重新出现。更有趣的是，将使用状态标签的状态机转换为不引用标签的函数，实际上是unfold操作的一个特例。 F-代数 ---------- 从头开始... 我正在看Pierce的《计算机科学家基础范畴论》中问题2.2.4.2。我构造了所需的逆，但抽象层次让我有点困惑，无法证明它是逆。于是我作弊，查看了Wadler的论文： http://homepages.inf.ed.ac.uk/wadler/papers/free-rectypes/free-rectypes.txt 然后我决定，应该实际为一些例子推导细节，并对发现感到惊讶。 给定范畴C中的一个函子F，一个F-代数是一个箭头 fin : F(X) -> X，其中X为某对象。我们也将一个F-代数写作(X,fin)，以明确其对底层范畴对象的依赖。 我们可以将F-代数画为： F(X) | | fin V X 在Haskell中我们可以这样定义： class (Functor f) => Algebra f x where fin :: (f x) -> x （我们使用多参数类，因此在ghc中用-fglasgow-exts，在hugs中用-98运行。） F-代数构成一个范畴，其中的箭头是C中的箭头h : X -> X，使得以下图表交换： F(h) F(X) --> F(Y) | | | | V h V X --> Y 考虑一个简单例子，F = Maybe。记住Maybe函子定义为Maybe x = Nothing | Just x。类型Maybe x的对象要么是特定对象'Nothing'，要么是一个x。我们可以将其写作F(X) = 1+X，其中+是不交并，1是终对象（例如单元素集合）。因此一个F-代数是一个函数fin : Maybe X -> X。 所以当我们对F(X)的一个元素应用fin时，需要考虑两种情况：它作用于Nothing的可能性，以及作用于Just x的可能性。对于前者，fin(Nothing)就是X中的一个元素，记为g。对于后者，它本质上是一个函数X -> X，记为h。因此，选择一个函数Maybe X -> X等同于选择X中的一个元素和一个函数X -> X。 让我们在自然数上定义这个例子： instance Algebra Maybe Integer where fin Nothing = 0 fin (Just a) = a+1 （Haskell没有提供自然数类，所以我们用Integer伪造。） 注意fin是如何按照上述两种情况编写的。 现在考虑另一个Maybe-代数(Y,f)，其中f(Nothing) = g，f(Just x) = h(x)。 定义p : Integer -> Y为p(n) = h^n(g)。（h^n表示h应用n次。）显然以下图表交换： 1+N --> 1+Y | | |fin |f V V N --> Y （记住，函数f: X -> Y提升为函数f' : 1+X -> 1+Y，其中f(Nothing) = Nothing，f(Just x) = Just f(x)。参见Prelude中Maybe的fmap定义。） 让我们创建另一个Maybe-代数： instance Algebra Maybe Float where fin Nothing = 1.0 fin (Just x) = 2.0*x 在这种情况下，我们有 p :: Integer -> Float p n = 1.0*2^n 我们声称p是一个Maybe-代数箭头，因此我们应该比较p . fin和fin . (fmap p)在一些值上的结果： ex0 = map (fin . (fmap p)) [Nothing,Just 0,Just 1,Just 16] ex1 = map (p . fin) [Nothing,Just 0,Just 1,Just 16] 你应该看到ex0等于ex1。 因此我们展示了一个从F-代数(N,fin)到(Y,f)的F-代数箭头。更重要的是，从(N,s)到(Y,f)只可能存在唯一的F-代数箭头。由于我们的构造是完全通用的，它适用于任何(Y,f)。这意味着对于每个F-代数，存在唯一的F-代数箭头从(N,fin)指向它。换句话说，(N,fin)是F-代数范畴中的初始对象。假设对于某个F，我们有一个初始F-代数(X,fin)。那么对于任何F-代数(Y,f)，使得以下图表交换的唯一映射h显然是f的函数。 F(h) F(X) --> F(Y) | | fin| | f V h V X --> X h = fold f 这个函数被称为'fold'。我们现在可以定义： class (Algebra f x) => Initial f x | x -> f where fold :: (f y -> y) -> (x -> y) 我们有一个箭头fin : F(N) -> N。由于F是函子，我们也有箭头F(fin) : F(F(N)) -> F(N)。这也是一个F-代数。现在考虑fold(F(fin))。这必须映射N -> F(N)。不难证明这是fin的逆。实际上它减1，但如果试图从0减去1，我们得到Nothing。可以证明，对于初始代数，一般情况下fold(F(fin))是fin的逆。即fold(F(fin))是fout的逆，这本质上是"Lambek引理"。我们现在可以通过在Haskell中编写所有内容来完成Initial的定义： fout :: x -> (f x) fout = fold (fmap fin) fout是fin的逆。Haskell使用fold自动为我们构造fout。 instance Initial Maybe Integer where fold f 0 = f Nothing fold f (n+1) = f $ Just $ fold f n 我们现在可以通过将其应用于整数来证明fin是fout的逆： --ex2 = fin $ fout $ (4::Integer) ex2 = map (fin . fout) [0,1,16 :: Integer] ex3 = map (fout . fin) [Nothing,Just 0,Just 1,Just 16 :: Maybe Integer] F-余代数 ------------ 我们现在可以开始对偶化我们的构造，看看会出现什么新对象。 我们首先定义F-余代数： class (Functor f) => Coalgebra f x where outf :: x -> f x 这次一个F-余代数是一个箭头f : X -> F(X)，当需要显示对X的依赖时，我们将余代数写作(X,f)。F-余代数之间的箭头以明显的方式定义。我们现在考虑的不是F-余代数范畴中的初始对象，而是终对象。这次存在一个从任何F-余代数到终F-余代数的唯一箭头。如果F-余代数是(Y,f)，则从(Y,f)到终F-余代数的唯一映射由一个称为'unfold'的函数指定。以下是终F-余代数的完整签名。 class (Coalgebra f x) => Final f x | x -> f where unfold :: (y -> f y) -> (y -> x) 同样我们可以构造outf的逆，这次使用unfold： inf :: (f x) -> x inf = unfold (fmap outf) 是时候举个例子了。定义自然数上的以下函数。 collatz :: Integer -> Maybe Integer collatz 1 = Nothing collatz n | even n = Just $ n `div` 2 | odd n = Just $ 3*n+1 这定义了一个Maybe-余代数 instance Coalgebra Maybe Integer where outf n = collatz n 著名的Collatz猜想指出，如果我们对任何自然数反复应用collatz，最终会到达1。假设Collatz猜想为真。那么我们可以问，对一个数应用多少次collatz才能到达1？定义： count f x = case f x of Nothing -> 0 Just x -> 1+count f x 这也应该给出为什么我们使用Maybe Natural而不是仅仅Natural的线索。我们想要计算在到达选定值之前需要迭代函数的次数，而不仅仅是零。我们可以通过让函数将选定值映射到Nothing来实现这一点。因此方便的是，函数f既描述了迭代，又指明了迭代结束的位置。 然而有一个陷阱。如果Collatz猜想为假，那么c collatz x可能不会终止。因此答案可能是'无限'。所以严格来说，c应该映射到由无穷大扩展的自然数： data Count = Infinity | Natural Integer deriving (Show) plusOne (Natural n) = Natural (1+n) plusOne Infinity = Infinity Count类型是一个Maybe-余代数： instance Coalgebra Maybe Count where outf (Natural 0) = Nothing outf (Natural (x+1)) = Just $ Natural x outf Infinity = Just Infinity 因此，如果我们调整count f使其类型为Count而不是integer，那么它给出一个Maybe-余代数箭头。它是到Count的唯一这样的箭头。我们没有使用任何关于collatz函数的特殊性质，因此我们构造了unfold。我们现在可以实现Count作为终Maybe-余代数： instance Final Maybe Count where unfold f x = case f x of Nothing -> Natural 0 (Just x) -> plusOne $ unfold f x 让我们展示inf . outf是恒等映射： ex4 = map (inf . outf) [Natural 0,Natural 1,Natural 17,Infinity] 你可能会注意到一个陷阱：它在列表的最后一个元素上失败。如果函数重复迭代从未到达Nothing，unfold返回Infinity。但我们没有办法仅仅通过迭代来知道这一点。所以，从数学上讲，inf是outf的逆。但我们并不总能计算它。 列表与树 --------------- 到了这个点，你肯定在想为什么这些函数被称为fold和unfold。 好吧，让我们定义一个函子F： data F a = One | Pair Integer a deriving (Eq,Show) F a 本质上是 Maybe (Integer,a) 我们需要一个函数将数据从F中提取出来： F是一个函子，因为我们可以定义： instance Functor F where fmap f One = One fmap f (Pair a b) = Pair a (f b) 这满足通常的函子规则。 不难看出，([Integer],fin)（其中fin定义如下）实际上是一个F-代数： instance Algebra F [Integer] where fin One = [] fin (Pair a b) = a:b （一个小前提：我们实际上是在讨论有限列表。） fin将一个整数和一个整数列表粘合在一起形成另一个列表。它还提供了一种创建空列表的方法。因此，和之前一样，我们使用fin编码一对元素：一个特指的元素[]和函数(:)。 假设我们有一个X中的元素g，以及一个函数f: X -> Integer -> X。那么我们可以使用标准Prelude函数foldr将任何整数列表映射到X。我们得到foldr f g : [Integer] -> X。事实上，如果我们把像[1,2,3]这样的列表视为函数的组合：(:) 1 ((:) 2 ((:) 3 []))，那么fold f g [1,2,3]就是用f替换(:)，用g替换[]。现在应该容易看出([Integer],fin)是一个初始F-代数，并且fold和foldr本质上是相同的： instance Initial F [Integer] where -- 将f解包成适合foldr的形式 fold f = foldr (cons f) (f One) where cons f a b = f $ Pair a b 像往常一样，我们可以检查同构： ex5 = fin $ fout [1::Integer,2,3,4,5] 许多论文讨论unfold。我们在这里称它为unfoldr，因为它与foldr自然配对。 unfoldr p f g x = if p x then [] else f x : unfoldr p f g (g x) g是机器的把手。每次我们转动把手，g将一个对象映射到一个新对象，并通过将f应用于这个对象来收集输出。我们将所有输出收集到一个列表中，直到函数p告诉我们停止。例如 ex6 = unfoldr (>20) id (2*) 1 这返回不超过20的2的幂的列表。我们转动(2*)把手直到条件满足。 unfoldr本质上是列表的unfold操作（除了这次我们*允许*无限列表——例如如果你有p _ = False）。 instance Coalgebra F [Integer] where outf [] = One outf (a:b) = Pair a b instance Final F [Integer] where -- 将f解包成适合unfoldr的形式 unfold f = unfoldr (isOne . f) (fst . pair . f) (snd . pair . f) where isOne One = True isOne _ = False ex7 = inf $ outf [1::Integer,2,3,4,5] 我们现在可以对树而不是列表进行类似的分析。树是函子G的G-代数： data G a = One' | Triple Integer a a deriving (Show) instance Functor G where fmap f One' = One' fmap f (Triple a b b') = Triple a (f b) (f b') data Tree a = Empty | Tree a (Tree a) (Tree a) deriving (Show) instance Algebra G (Tree Integer) where fin One' = Empty fin (Triple a b b') = Tree a b b' instance Initial G (Tree Integer) where fold f Empty = f One' fold f (Tree a b b') = f (Triple a (fold f b) (fold f b')) 正如fold可以通过在连续元素之间应用一个函数来折叠列表，fold以完全相同的方式折叠树。 这里是我们通常的例子，展示同构的作用： ex8 = fin $ fout $ Tree (6::Integer) (Tree 2 Empty Empty) (Tree 7 Empty (Tree 0 Empty Empty)) 现在我们进入有趣的例子。 自动机 -------- 考虑函子H data H x = H (Char -> Maybe x) instance Functor H where fmap f (H g) = H (fmap f . g) 为方便起见，我们定义unH： 一个H-余代数是一个函数X -> H(X)。本质上它是一个函数X -> Char -> Maybe X。暂时忽略Maybe。我们有一个函数f : X -> Char -> X。这本质上是一个自动机，其中X标记状态，f定义转移。这是你用来识别字符串的正则表达式那种。但我们还需要最后一件事：一种标记字符串已被识别的方法。这就是为什么我们使用Maybe。Nothing值（而不是一个状态）表示字符串已被匹配。（这被称为部分自动机，因为它在此处停止。） 这是一个例子： f :: Integer -> Char -> Maybe Integer f 0 'c' = Just 1 f 0 _ = Just 0 f 1 'a' = Just 2 f 1 _ = Just 0 f 2 't' = Nothing f 2 _ = Just 0 这个函数可用于识别字符串"cat"出现在另一个字符串中作为子串时。事实上，我们可以定义 runMachine f state "" = False runMachine f state (c:cs) = case f state c of Nothing -> True (Just state') -> runMachine f state' cs ex9 = map (runMachine f 0) ["cat","dog","wildcats"] 现在Integer标签被安全地锁在(runMachine f 0)内部，但我们为此付出的代价是不能再引用状态。我们成功地隐藏了标签，却完全隐藏了状态。我们想要的是在不费心于标签的情况下操纵状态。 因此现在我们构造H-余代数。我称之为超树（Hypertree），因为它与上面的树例子有一些相似之处。从某种意义上说，超树是一棵树，对X的每个元素都有一个子节点（尽管使用Maybe意味着子节点"可能"是一个死胡同，没有进一步子节点）。 data Hypertree x = HTree (x -> Maybe (Hypertree x)) 注意我不是凭空想出那个定义的。我显式地定义了一些看起来应该给出H(X) = X的解的东西。 instance Coalgebra H (Hypertree Char) where outf (HTree f) = H f instance Final H (Hypertree Char) where