Почему Data.Set требует, чтобы элементы были экземпляром Ord?

Это не работает

data Cutlery = Knife | Fork deriving (Show,Eq)
let x = [Knife,Fork]
let set1 = Set.fromList x

при определении

data Cutlery = Knife | Fork deriving (Show,Ord,Eq)

решает проблему, но не имеет смысла. Является ли Data.Set отличным от математического определения набора?

Ответы

Ответ 1

A Data.Set фиксирует математическую абстракцию набора, но не идентична. Основное отличие состоит в том, что a Data.Set требует, чтобы его элементы упорядочивались, тогда как математический набор требовал, чтобы его элементы были сопоставимы для равенства.

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

data Set a = Set [a]

то есть. под капотом это всего лишь список, и мы убеждаемся, что мы никогда не вставляем повторяющиеся элементы. Операции elem и insert были бы

elem a (Set as) = any (a ==) as

insert a (Set as) | a `elem` as = Set as
                  | otherwise   = Set (a:as)

Однако это означает, что оба elem и insert являются операциями O (n). Если мы хотим сделать что-то лучше этого, стандартными подходами являются

  • Храните элементы в сбалансированном двоичном дереве (для которого требуется экземпляр Ord)
  • Хешируйте элементы и храните их в массиве (для чего требуется экземпляр Hashable).

TreeSet

Реализация, выбранная авторами Data.Set, заключалась в использовании двоичного дерева, которое вы можете увидеть, перейдя в источник . Реализация более или менее

data Set a = Bin a (Set a) (Set a)
           | Tip

Теперь вы можете написать функцию elem как

elem :: Ord a => a -> Set a -> Bool
elem = go
  where
    go _  Tip = False
    go x (Bin y l r) = case compare x y of
      LT -> go x l
      GT -> go x r
      EQ -> True

который является операцией O (log n), а не O (n). Вставки сложнее (так как вам нужно держать дерево сбалансированным), но схожим.

HashSet

В наборе хэшей вы не сравниваете элементы напрямую при их вставке и удалении. Вместо этого каждый элемент хэшируется до целого числа и сохраняется в местоположении на основе этого целого.

Теоретически это не требует экземпляра Ord. На практике вам нужен какой-то способ отслеживания нескольких элементов, хэш которых имеет одинаковое значение, а метод, выбранный разработчиками Data.HashSet, состоит в том, чтобы хранить несколько элементов в регулярном Data.Set, поэтому, оказывается, вам нужно экземпляр Ord в конце концов!

data HashSet a = HashSet (Data.IntMap.IntMap (Data.Set.Set a))

Его можно было бы написать вместо

data HashSet a = HashSet (Data.IntMap.IntMap [a])

вместо этого, который удаляет требование Ord за счет некоторой неэффективности, если существует много элементов, имеющих одинаковое значение.

Ответ 2

Является ли Data.Set отличным от математического определения множества?

Очевидно, что математические множества могут быть бесчисленными бесконечными - вы не сможете представить это во всей общности с помощью компьютера или даже машины Тьюринга.

Но ответ, который вы ищете, таков: Data.Set - это тип данных, основанный на двоичных деревьях, и ему требуется полный линейный порядок для элементов, чтобы знать, следует ли положить, а затем найти что-то в левом или правом поддереве a node. Поэтому, хотя можно было бы реализовать набор типов данных без ограничения Ord, эта конкретная, более эффективная реализация не будет.

Ответ 4

Это для эффективности. Data.Set реализуется как дерево двоичного поиска (ака упорядоченное или сортированные бинарные деревья). Использование этой структуры данных означает, что мы можем написать функцию поиска, member, которая принимает логарифмическое время O (logn), а не что будет линейным временем, O (n). При заказе элементов мы можем выполнять экспоненциально меньшее сравнение при выполнении поиска.

Из Wikipedia:

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

Если элементы не были экземпляром Ord, не было бы способа упорядочить элементы дерева двоичного поиска - мы могли бы только сформировать двоичное дерево, а не двоичное дерево поиска. В результате мы не смогли бы быстро найти время поиска.