Haskell数据类型co

我试图让我的脑袋围绕F-代数,而这篇文章做得很好。 我理解分类理论中的双重概念,但我很难理解F-coalgebras(F-代数的对偶)如何与Haskell中的懒惰数据结构相关。

用代数函数描述F-代数的函数:F a - > a,如果将F a看作一个表达式,并且作为评估该表达式的结果,就像链接文章解释它一样,这是有意义的。

作为F-代数的对偶,F-代数的相应函数是a→F a。 维基百科说,F-代数可以用来创建无限的,懒惰的数据结构。 a - > F函数如何允许创建无限的,懒惰的数据结构? 另外,考虑到这一点,由于Haskell处于核心惰性,Haskell F-代数中的大多数数据类型而不是F-代数? F-代数是否不被懒惰地评估?

如果数据类型(或者至少那些能够有无限数据的类型)基于Haskell中的F-余代数,例如什么是a - > F是列表的函数? 什么是列表的终端F-coalgebra?

在Haskell中创建无限列表[1,2,3,4 ...]可能如下所示:

list = 1 : map (+ 1) list

这是否以某种方式使用F-余代数? 无限的数据结构是否需要懒惰评估和递归的概念以及F-余代数的使用? 我在这里错过了什么吗?


可以使用余代数A -> FA来剥离(可能是无限的)数据结构的外层。 对于X列表,函子是F a = Maybe (X, a) ,与代数视图中相同。 在haskell中,余代数的功能是

headView :: [a] -> Maybe (a, [a])
headView [] = Nothing
headView (x:xs) = Just (x,xs)

unfoldr是与这个代数相对应的展开,就像foldr是与这个代数相对应的折叠一样。

如果你认为[a]不是列表的类型,而是列表或程序的类型描述,那么这可以让你构建(看似)无限的值,只是必要的描述。

正如你所看到的,一个Haskell列表看起来既像F-代数又是F-代数。 这是可能的,因为Haskell实际上并不一致。 你可以折叠展开,并获得无限循环。 像coq和agda这样的语言明确地区分了数据类型(F-代数)和编码类型(F-代数)。 在这些语言有两种列表类型,代数List和coalgebraic Colist

链接地址: http://www.djcxy.com/p/80201.html

上一篇: Are haskell data types co

下一篇: How do functional languages represent algebraic data types in memory?