Data.Foldable для неупорядоченных контейнеров - PullRequest
Новая
       27

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

10 голосов
/ 24 ноября 2011

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

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

Haskell's 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].

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

1 Ответ

2 голосов
/ 24 ноября 2011

Операция, выполняемая вашим оператором сгиба, будет работать не над моноидом, а над коммутативной полугруппой.Это дает вам op :: (CSemi a) => f a -> a -> a

В литературе, которую я видел, типичное имя для вашего оператора / класса типов будет просто CFold - сокращение от коммутативного сгиба.(YAHT также использует cfold в качестве имени для фолда в стиле cps, но я не думаю, что это обычное использование)

...