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

Question

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

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

Хаскеля 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 экземпляры идут с заказом.

Как называется обобщение этой концепции, которая применяется к контейнерам, которые не упорядочивают свои элементы?

Для Хаскелла 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, но я не думаю, что это обычное использование)