我最近有点“从所有东西中提炼出它的基本原理”,我一直无法找到定义可遍历类型类的明确的理论原因,只有“能够遍历应用性余代数是有用的,很多数据类型都可以做到”和大量的提示。
我知道有一个应用“族”,如https://duplode.github.io/posts/divisible-and-the-monoidal-quartet.html所描述的。
我还知道,虽然可遍历遍历是应用余代数,但来自“半群”的可遍历1类型类描述了应用余代数,而来自“分配”的分配类型类描述了函子代数。
另外,我知道Foldable、Foldable 1和理论上的fold族成员描述了可以使用幺半群、半群和相应的幺半群族成员折叠的数据类型,例如magmas(用于折叠为二叉树)和每个的交换版本(用于折叠为每个的无序版本)。
因此,由于Traversable是Foldable的子类,我假设它本质上是幺半群,类似地,我假设Traversable 1本质上是半群,而Distributive本质上是comonoidal(正如在“distributative”包中的描述中提到的)。
这似乎是正确的思路,但“应用型”和“应用型”从何而来?是否存在岩浆型和交换型?在一个具有非平凡共生体的范畴中是否存在分配族?
本质上,我的问题是“这些类型类存在吗?它们是什么?如果不存在,为什么不存在?":
class FoldableMagma t => TraversableMagma t where
traverseMagma :: ??? f => (a -> f b) -> (t a -> f (t b))
class FoldableCommute t => TraversableCommute t where
traverseCommute :: ??? f => (a -> f b) -> (t a -> f (t b))
class Foldable t => ContraTraversable t where
contraTraverse :: Divisible f => (b -> f a) -> (t a -> f (t b))
-- im really not sure on this last one
-- but it's how i'd expect an endofunctor over coalgebras to look
-- which seems potentially related to traversables?
大概是不太重要的额外问题:在尝试研究这个问题时,我遇到了“data-functor-logistic”包https://hackage.haskell.org/package/data-functor-logistic
这描述了逆变函子上的分配--是否有等价的整除函子(或判定函子)上的可遍历?
2条答案
按热度按时间9nvpjoqh1#
我不知道有哪个库实现了这些类,但我会尝试解释这些类代表了什么。我是一个程序员,不是一个类别理论家,所以对此持保留态度。
Applicative
变体ApplyMagma
(第一次)ApplyMagma
类与Apply
类具有完全相同的方法,但它不需要遵循结合律。如果
Apply
类似于半群,则ApplyMagma
类似于岩浆。ApplyCommute
(第一次)ApplyCommute类等效于Apply类,但具有以下交换性法则:
如果
Apply
类似于半群,则ApplyCommute
类似于交换半群。Traversable1
变体Traversable1Magma
的第一个字符一个
Traversable1Magma
可以被看作是一个Traversable1
,并提供了更多关于结构的信息。当Foldable1
类有一个toNonEmpty
方法时,Foldable1Magma
类可以有一个toBinaryTree
方法。Traversable1Commute
的第一个字符一个
Traversable1Commute
可以被看作是一个Traversable1
,没有定义元素的顺序。如果它不需要Ord a
约束,那么containers
中的Set
可以是这个类的一个示例。Traversable1Commute可以是Traversable1的一个超类。请注意,这些是
Traversable1
的变体,因为ApplyMagma
和ApplyCommute
都没有与pure
等效的函数。ContraTraversable
型ContraTraversable
没有任何示例。要了解原因,请查看contraTraverse
函数的类型。我们可以将其专门化为以下内容:
其等效于以下内容:
使用
const
和Divisible中的conquer
函数,我们可以创建任何类型的值,这是不可能的。bgtovc5b2#
自从问了这个问题并得到了前面的(很好的)答案后,我了解到了为什么使用应用型的另一个原因:代数数据类型!
如果没有任何约束,它只能描述无人居住的数据类型,如下所示:
如果它是Functor,它可以描述如下所示的代数数据类型:
本质上,它是任何一种数据类型,具有任意数量(如果Haskell中可以描述的话,可能是无限的)的单个FTraverable参数的构造函数(其中
a
~Identity a
)。这就是说,任何可遍历的f a
都同构于(f (), a)
,即Writer函子。引入Apply可启用如下额外的数据类型:
现在构造函数可以有任意多个参数,只要它是一个大于零的有限数!现在同构到
(f (), NonEmpty a)
,它们的大小相等。“适用性”启用以下功能:
现在允许空的构造函数!同构现在是
(f (), [a])
。假设的可交换的可应用性将用于可交换的代数数据类型,如果它们是一个东西的话--也许,如果Set强制它只能与可交换的幺半群折叠,它们将是相关的!但是据我所知,可交换的数据类型不是Haskell的核心部分,所以这种遍历形式不会出现在代数数据类型中。
分布函数也是类似的,它用一个构造函数来描述任意多个记录(可能是无限的)。
据我所知,逻辑斯蒂与这种代数解释无关--因为Reader函子通常与Distributes一起使用来创建getter函数的集合,逻辑斯蒂被设计为与Op逆变函子一起工作来创建setter函数的集合。
这对我来说意味着可遍历的等价物并不存在,因为刻画可遍历的Writer函子是它自己的对立面(
(r,a)
同构于(a,r)
)。