haskell - Data.Foldable 用于无序容器

Question

我正在研究一种用于数据库操作的 Haskell-meets-SQL 语言，以及一个与之配套的通用类型类库，在任何有意义的地方都从 Hackage 中抄袭。

因为数据库查询优化器的一个重要目标是消除不必要的排序，所以保留对实际上需要排序的位置的静态表示非常重要。这使我们为折叠定义一个类型类。

Haskell 的 Data.Foldable有:(省略与我要表达的观点无关的默认定义)

class Foldable t where
  -- | Combine the elements of a structure using a monoid.
  fold :: Monoid m => t m -> m

  -- | Map each element of the structure to a monoid,
  -- and combine the results.
  foldMap :: Monoid m => (a -> m) -> t a -> m

  -- | Right-associative fold of a structure.
  foldr :: (a -> b -> b) -> b -> t a -> b

  -- | Left-associative fold of a structure.
  foldl :: (a -> b -> a) -> a -> t b -> a

  -- | A variant of 'foldr' that has no base case,
  -- and thus may only be applied to non-empty structures.
  foldr1 :: (a -> a -> a) -> t a -> a

  -- | A variant of 'foldl' that has no base case,
  -- and thus may only be applied to non-empty structures.
  foldl1 :: (a -> a -> a) -> t a -> a

在我看来，这个类忽略了一个区别，出于实际目的，这对大多数 Haskell 应用程序来说并不那么重要，但对数据库设置更感兴趣。即:全部Data.Foldable实例带有排序。

这个概念的概括名称是什么，适用于不对元素进行排序的容器类型？

对于 Haskell Data.Set s 它工作正常，因为有一个 Ord实现所需的上下文。但是，排序要求是一个实现工件，对于许多有用的类型，所使用的排序可能没有任何域级别的含义。

对于更一般的集合，fold :: Monoid m => t m -> m定义本身是正确的(foldMap 也是如此)。我说主要是因为它的类型包括结合律(通过 Monoid 的定义)，但不包括所需的交换律。其他变种甚至不存在。

我不想在不需要的地方引入排序。我也不想介绍不确定性无法追踪的地方。我有兴趣构建一个没有 toList :: Set a -> [a] 的语言和库。随处可见的函数，因为它引入了以下二分法:

允许人们观察有关集合/关系如何物理存储的实现细节

失去对不确定性的影响

显然都是sortBy :: (a -> a -> Ordering) -> Set a -> [a]和 shuffle :: Set a -> Data.Random.RVar [a]是有用的，无可争议的，并将被包括在内。事实上，sortBy有一个更通用的类型 sortBy :: (TheUnorderedFoldableClassIAmTryingToName f) => (a -> a -> Ordering) -> f a -> [a] .

这个想法叫什么？如果我离开基地，我在哪里离开基地路径？

Answer 1

您的折叠式运算符执行的操作不会在幺半群上运行，而是在可交换半群上运行。这给了你op :: (CSemi a) => f a -> a -> a
在我看到的文献中，您的运算符/类型类的典型名称就是 CFold - 可交换折叠的缩写。 (YAHT 也使用 cfold 作为 cps 样式折叠的名称，但我认为这不是常用的)