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来说,它运行得很好,因为Ord实现需要一个上下文.排序要求虽然是实现工件,但对于许多有用的类型,使用的排序可能没有任何域级意义.

对于集合,更一般地说,fold :: Monoid m => t m -> m定义本身大多是正确的(因此foldMap).我之所以这么说,主要是因为它的类型包括相关性定律(通过定义Monoid)而不是所需的交换法.其他变体甚至不存在.

我不想介绍不需要它们的种类.我也不想在无法跟踪的情况下引入非确定性.我有兴趣构建一个没有toList :: Set a -> [a]任何功能的语言和库,因为它引入了以下两者之间的二分法:

1. 允许人们观察有关如何物理存储集/关系的实现细节
2. 失去对非决定论的影响

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