无序容器的Data.Foldable

Question

我正在开发一种用于数据库操作的Haskell-meets SQL语言，并开发一个通用类型类库，只要它有意义，就可以从Haskell-meets SQL语言中下载。

因为数据库查询优化器的一个重要目标是消除不必要的排序，因此保留排序实际上是必要的静态表示是很重要的。这就给我们定义了折叠的类型。

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来说，它工作得很好，因为实现需要一个Ord上下文。然而，订购需求是一个实现工件，对于许多有用的类型，所使用的排序可能没有任何领域级别的意义。

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

我不想介绍那些不需要它们的地方。我也不想在无法跟踪的地方引入non-determinism。我对构建一个没有toList :: Set a -> [a]函数的语言和库感兴趣，因为它引入了以下两种方法：

stored

• Losing

• 允许人们观察有关集合/关系在物理上是如何跟踪非决定论的实现细节，从而影响

。

显然，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样式折叠的名称，但我认为这并不常见)