Divisible Type Class 是否有有用的应用程序？

Question

我最近一直在 Elm 中研究 API，其中一种主要类型是逆变的。所以，我在谷歌上搜索了一下，看看可以用逆变类型做什么，结果发现 the Contravariant package in Haskell defines the Divisible type class.

定义如下：

class Contravariant f => Divisible f where
  divide  :: (a -> (b, c)) -> f b -> f c -> f a
  conquer :: f a

事实证明，我的特定类型确实符合 Divisible 类型的定义 class。虽然 Elm 不支持 classes 类型，但我确实不时查看 Haskell 以获取一些灵感。

我的问题：这种类型 class 有什么实际用途吗？在 Haskell（或其他语言）中是否存在受益于这种分而治之模式的已知 API？有什么我应该注意的问题吗？

非常感谢您的帮助。

Answer 1

这是一个可能的用例。

在流媒体库中，可以有类似于 foldl 包中的类似折叠的构造，它们被提供了一系列输入，并且 return 当序列耗尽时提供一个汇总值。

这些折叠在它们的输入上是逆变的，并且可以Divisible。这意味着如果你有一个元素流，其中每个元素都可以以某种方式分解为 b 和 c 部分，并且你也恰好有一个折叠消耗 bs 和另一个折叠消耗 cs，那么你可以构建一个消耗原始流的折叠。

foldl 的实际折叠没有实现 Divisible，但它们可以，使用新类型包装器。在我的 process-streaming 包中，我有一个 fold-like type 实现了 Divisible.

divide 要求构成折叠的 return 值是同一类型，并且该类型必须是 Monoid 的实例。如果折叠 return 不同的、不相关的幺半群，解决方法是将每个 return 值放在元组的单独字段中，将另一个字段保留为 mempty。这是可行的，因为一个幺半群元组本身就是一个 Monoid.

Answer 2

一个例子：

Applicative 对解析很有用，因为你可以把 Applicative 的部分解析器变成整体解析器，只需要一个将部分组合成一个整体的纯函数。

Divisible 对于序列化很有用（我们现在应该称之为 coparsing 吗？），因为你可以将部分的 Divisible 序列化器变成整体的序列化器，只需要一个纯函数来将整体拆分成部分。

我还没有真正看到一个以这种方式工作的项目，但我正在（慢慢地）为 Haskell 开发一个 Avro 实现。

当我第一次遇到 Divisible 时，我想要它用于 divide，并且不知道 conquer 除了作弊之外还有什么可能的用途（无处不在的 f a，因为任何a？）。但是为了使可分律检查我的序列化程序 conquer 变成了 "serializer" 将任何内容编码为零字节，这很有意义。

Answer 3

我将检查由 Edward Kmett 在 discrimination 包中实现的 Fritz Henglein 广义基数排序技术中的核心数据类型示例。

虽然那里发生了很多事情，但它主要集中在像这样的类型上

data Group a = Group (forall b . [(a, b)] -> [[b]])

如果你有一个 Group a 类型的值，你基本上必须在 a 上有一个等价关系，因为如果我给你一个 a 和某种类型 [=21] 之间的关联=] 你完全不知道那么你可以给我 "groupings" of b.

groupId :: Group a -> [a] -> [[a]]
groupId (Group grouper) = grouper . map (\a -> (a, a))

您可以将其视为编写分组实用程序库的核心类型。例如，我们可能想知道如果我们可以 Group a 和 Group b 那么我们就可以 Group (a, b)（稍后会详细介绍）。 Henglein 的核心思想是，如果您可以从整数的一些基本 Group 开始——我们可以通过基数排序编写非常快速的 Group Int32 实现——然后使用组合器将它们扩展到所有类型，那么您将拥有代数数据类型的广义基数排序。

那么我们如何构建我们的组合器库呢？

嗯，f :: Group a -> Group b -> Group (a, b) 非常重要，因为它让我们可以将类似产品的类型分组。通常，我们会从 Applicative 和 liftA2 得到它，但是您会注意到 Group 是 Contravaiant，而不是 Functor.

所以我们改用 Divisible

divided :: Group a -> Group b -> Group (a, b)

请注意，这是从

以一种奇怪的方式出现的

divide :: (a -> (b, c)) -> Group b -> Group c -> Group a

因为它具有逆变事物的典型"reversed arrow"特征。我们现在可以根据对 Group.

的解释来理解 divide 和 conquer 之类的东西

Divide 说如果我想建立一个策略来等同 as 使用等同于 bs 和 cs 的策略，我可以对任何类型执行以下操作 x

获取部分关系 [(a, x)] 并使用函数 f :: a -> (b, c) 映射它，并进行一些元组操作，以获得新关系 [(b, (c, x))]。
用我的Group b把[(b, (c, x))]判别成[[(c, x)]]
使用我的Group c将每个[(c, x)]区分为[[x]]给我[[[x]]]

展平内层以获得我们需要的[[x]]

instance Divisible Group where
  conquer = Group $ return . fmap snd
  divide k (Group l) (Group r) = Group $ \xs ->
    -- a bit more cleverly done here...
    l [ (b, (c, d)) | (a,d) <- xs, let (b, c) = k a] >>= r

我们还得到了更棘手的解释Decidable refinement of Divisible

class Divisible f => Decidable f where
  lose   :: (a -> Void) -> f a
  choose :: (a -> Either b c) -> f b -> f c -> f a

instance Decidable Group where
  lose   :: (a -> Void) -> Group a
  choose :: (a -> Either b c) -> Group b -> Group c -> Group a

这些读起来是说对于任何类型 a 我们可以保证没有值（我们不能以任何方式产生 Void 的值，函数 a -> Void 是一种在给定 a 的情况下产生 Void 的方法，因此我们也不能以任何方式产生 a 的值！）然后我们立即得到一组零值

lose _ = Group (\_ -> [])

我们也可以进行与上述 divide 类似的游戏，除了我们不按顺序使用输入鉴别器，而是交替进行。

使用这些技术，我们建立了一个“Group可用”的库，即 Grouping

class Grouping a where
  grouping :: Group a

并注意 nearly all the definitions arise 来自 groupingNat 顶部的基本定义，它使用快速的一元向量操作来实现有效的基数排序。

Divisible Type Class 是否有有用的应用程序？

Are there useful applications for the Divisible Type Class?

haskell

types

functional-programming

elm

type-theory