30

我最近一直在 Elm 中研究一个 API，其中一种主要类型是逆变的。所以，我用谷歌搜索看看可以用逆变类型做什么，发现Haskell 中的逆变包定义了 Divisible 类型 class。

定义如下：

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

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

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

非常感谢您的帮助。

4

3 回答 3

21

一个例子：

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

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

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

当我第一次遇到 Divisible 时，我想要它divide，并且不知道conquer除了作弊之外还有什么可能的用途（不知f a何故，对于任何人a？）。但是为了让可分法则检查我的序列化conquer程序成为一个“序列化程序”，它将任何内容编码为零字节，这很有意义。

于 2015-08-17T22:23:54.357 回答
16

这是一个可能的用例。

在流式库中，可以有类似foldl包中的类似折叠的构造，它们被提供一系列输入并在序列耗尽时返回一个汇总值。

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

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

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

于 2015-08-17T21:43:54.090 回答
10

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

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

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

如果你有一个 type 的值，Group a你基本上必须有一个等价关系，a因为如果我给你一个as 和b你完全不知道的类型之间的关联，那么你可以给我 的“分组” b。

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

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

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

好吧，f :: Group a -> Group b -> Group (a, b)这非常重要，因为它可以让我们创建类似产品的类型组。通常，我们会从ApplicativeandliftA2但是Group，你会注意到，isContravaiant不是 a Functor。

所以我们使用Divisible

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

请注意，这是以一种奇怪的方式出现的

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

因为它具有逆变事物的典型“反向箭头”特征。我们现在可以根据它们divide的conquer解释来理解Group.

Dividea说，如果我想使用等于bs 和s的策略来构建一个等于s 的策略c，我可以对任何类型执行以下操作x

  1. 使用你的部分关系并用一个函数和一些元组操作来[(a, x)]映射它，以获得一个新的关系。f :: a -> (b, c)[(b, (c, x))]

  2. Use my Group b to discriminate [(b, (c, x))] into [[(c, x)]]

  3. Use my Group c to discriminate each [(c, x)] into [[x]] giving me [[[x]]]

  4. Flatten the inner layers to get [[x]] like we need

    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

We also get interpretations of the more tricky 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

These read as saying that for any type a of which we can guarantee there are no values (we cannot produce values of Void by any means, a function a -> Void is a means of producing Void given a, thus we must not be able to produce values of a by any means either!) then we immediately get a grouping of zero values

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

We also can go a similar game as to divide above except instead of sequencing our use of the input discriminators, we alternate.

Using these techniques we build up a library of "Groupable" things, namely Grouping

class Grouping a where
  grouping :: Group a

and note that nearly all the definitions arise from the basic definition atop groupingNat which uses fast monadic vector manipuations to achieve an efficient radix sort.

于 2015-08-19T13:26:49.643 回答