haskell 从根本上说,为什么遍历是在应用程序上定义的?

siotufzp  于 2022-11-14  发布在  其他
关注(0)|答案(2)|浏览(146)

我最近有点“从所有东西中提炼出它的基本原理”,我一直无法找到定义可遍历类型类的明确的理论原因,只有“能够遍历应用性余代数是有用的,很多数据类型都可以做到”和大量的提示。
我知道有一个应用“族”,如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
这描述了逆变函子上的分配--是否有等价的整除函子(或判定函子)上的可遍历?

9nvpjoqh

9nvpjoqh1#

我不知道有哪个库实现了这些类,但我会尝试解释这些类代表了什么。我是一个程序员,不是一个类别理论家,所以对此持保留态度。

Applicative变体

ApplyMagma(第一次)

ApplyMagma类与Apply类具有完全相同的方法,但它不需要遵循结合律。

class Functor f => ApplyMagma f where
    (<.>) :: f (a -> b) -> f a -> f b

如果Apply类似于半群,则ApplyMagma类似于岩浆。

ApplyCommute(第一次)

ApplyCommute类等效于Apply类,但具有以下交换性法则:

f <$> x <.> y = flip f <$> y <.> x

如果Apply类似于半群,则ApplyCommute类似于交换半群。

Traversable1变体

Traversable1Magma的第一个字符

一个Traversable1Magma可以被看作是一个Traversable1,并提供了更多关于结构的信息。当Foldable1类有一个toNonEmpty方法时,Foldable1Magma类可以有一个toBinaryTree方法。

class (FoldableMagma t, Traversable1 t) => Traversable1Magma t where
    traverseMagma :: ApplyMagma f => (a -> f b) -> (t a -> f (t b))

Traversable1Commute的第一个字符

一个Traversable1Commute可以被看作是一个Traversable1,没有定义元素的顺序。如果它不需要Ord a约束,那么containers中的Set可以是这个类的一个示例。Traversable1Commute可以是Traversable1的一个超类。

class (FoldableCommute t, Functor t) => Traversable1Commute t where
    traverseCommute :: ApplyCommute f => (a -> f b) -> (t a -> f (t b))

请注意,这些是Traversable1的变体,因为ApplyMagmaApplyCommute都没有与pure等效的函数。

ContraTraversable

ContraTraversable没有任何示例。要了解原因,请查看contraTraverse函数的类型。

contraTraverse :: Divisible f => (b -> f a) -> (t a -> f (t b))

我们可以将其专门化为以下内容:

contraTraverse :: Monoid b => (b -> Op b a) -> (t a -> Op b (t b))

其等效于以下内容:

contraTraverse ~ Monoid b => (b -> a -> b) -> t a -> t b -> a

使用const和Divisible中的conquer函数,我们可以创建任何类型的值,这是不可能的。

bgtovc5b

bgtovc5b2#

自从问了这个问题并得到了前面的(很好的)答案后,我了解到了为什么使用应用型的另一个原因:代数数据类型!
如果没有任何约束,它只能描述无人居住的数据类型,如下所示:

data V1 a
instance VTraversable V1 where
    vtraverse _ = \case
-- uninhabited types can be pattern matched to create any result type

如果它是Functor,它可以描述如下所示的代数数据类型:

data FTrav1 a = FTrav1 a
instance FTraversable FTrav1 where
    ftraverse strat (FTrav1 a) = FTrav1 <$> strat a

data FTrav2 a = FTrav2_1 a | FTrav2_2 (FTrav1 a)
instance FTraversable FTrav2 where
    ftraverse strat (FTrav2_1 a) = FTrav2_1 <$> strat a
    ftraverse strat (FTrav2_2 fa) = FTrav2_2 <$> ftraverse strat fa

本质上,它是任何一种数据类型,具有任意数量(如果Haskell中可以描述的话,可能是无限的)的单个FTraverable参数的构造函数(其中a ~ Identity a)。这就是说,任何可遍历的f a都同构于(f (), a),即Writer函子。
引入Apply可启用如下额外的数据类型:

data ApplyTrav1 a = ApplyTrav1 a a
instance Traversable1 ApplyTrav1 where
    traverse1 strat (ApplyTrav1 a a) = ApplyTrav1 <$> strat a <*> strat a

data ApplyTrav2 a = ApplyTrav2_1 a (ApplyTrav1 a) | ApplyTrav2_2 (ApplyTrav1 a) a
instance Traversable1 ApplyTrav2 where
    traverse1 strat (ApplyTrav2_1 a fa) = ApplyTrav2_1 <$> strat a <*> traverse1 strat fa
    traverse1 strat (ApplyTrav2_2 fa a) = ApplyTrav2_2 <$> traverse1 strat fa <*> traverse1 strat a

现在构造函数可以有任意多个参数,只要它是一个大于零的有限数!现在同构到(f (), NonEmpty a),它们的大小相等。
“适用性”启用以下功能:

data ApplicTrav a = ApplicTrav0 | ApplicTrav a a
instance Traversable ApplicTrav where
    traverse _ ApplicTrav0 = pure ApplicTrav0
    traverse strat (ApplicTrav a a) = ApplicTrav <$> strat a <*> strat a

现在允许空的构造函数!同构现在是(f (), [a])
假设的可交换的可应用性将用于可交换的代数数据类型,如果它们是一个东西的话--也许,如果Set强制它只能与可交换的幺半群折叠,它们将是相关的!但是据我所知,可交换的数据类型不是Haskell的核心部分,所以这种遍历形式不会出现在代数数据类型中。
分布函数也是类似的,它用一个构造函数来描述任意多个记录(可能是无限的)。
据我所知,逻辑斯蒂与这种代数解释无关--因为Reader函子通常与Distributes一起使用来创建getter函数的集合,逻辑斯蒂被设计为与Op逆变函子一起工作来创建setter函数的集合。
这对我来说意味着可遍历的等价物并不存在,因为刻画可遍历的Writer函子是它自己的对立面((r,a)同构于(a,r))。

相关问题