Data.Foldable для неупорядоченных контейнеров

Я работаю над языком Haskell-встречает-SQL для манипуляций с базой данных и над библиотекой классов общих типов, чтобы пойти с ним, заимствуя из Hackage везде, где это имеет смысл.

Поскольку важной задачей оптимизатора запросов к базе данных является устранение ненужной сортировки, важно сохранить статическое представление того, где сортировка действительно необходима. Это подводит нас к определению класса типов для складок.

Data.Foldable Haskell имеет: (исключая определения по умолчанию, которые не имеют отношения к тому, что я делаю)

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 ). Я говорю в основном потому, что его тип включает закон ассоциативности (через определение Моноид ), но не требуемый закон коммутативности. Других вариантов даже не существует.

Я не хочу вводить сорта там, где они не нужны. Я также не хочу вводить недетерминизм , где его нельзя отследить.Я заинтересован в создании языка и библиотеки, в которых нет функции 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] .

Как называется эта идея? Если я далеко от базы, где я оставил базовый путь?