Data.Set

 import Data.Set (Set)
 import qualified Data.Set as Set

Свойства строгости

Этот модуль удовлетворяет следующему свойству строгости:

• Ключевые аргументы оцениваются до WHNF

Вот несколько примеров, которые иллюстрируют это свойство:

delete undefined s  ==  undefined

Тип множества

data Set a Источник

Множество значений a.

Операторы

(\\) :: Ord a => Set a -> Set a -> Set a infixl 9 Источник

O(n+m). См. difference.

Запрос

null :: Set a -> Bool Источник

O(1). Является ли это пустым множеством?

size :: Set a -> Int Источник

O(1). Количество элементов в множестве.

member :: Ord a => a -> Set a -> Bool Источник

O(log n). Находится ли элемент в множестве?

notMember :: Ord a => a -> Set a -> Bool Источник

O(log n). Элемент не входит в множество?

lookupLT :: Ord a => a -> Set a -> Maybe a Источник

O(log n). Найти наибольший элемент, меньший, чем заданный.

lookupLT 3 (fromList [3, 5]) == Nothing
lookupLT 5 (fromList [3, 5]) == Just 3

lookupGT :: Ord a => a -> Set a -> Maybe a Источник

O(log n). Найти наименьший элемент, больший, чем заданный.

lookupGT 4 (fromList [3, 5]) == Just 5
lookupGT 5 (fromList [3, 5]) == Nothing

lookupLE :: Ord a => a -> Set a -> Maybe a Источник

O(log n). Найти наибольший элемент, меньший или равный заданному.

lookupLE 2 (fromList [3, 5]) == Nothing
lookupLE 4 (fromList [3, 5]) == Just 3
lookupLE 5 (fromList [3, 5]) == Just 5

lookupGE :: Ord a => a -> Set a -> Maybe a Источник

O(log n). Найти наименьший элемент, больший или равный заданному.

lookupGE 3 (fromList [3, 5]) == Just 3
lookupGE 4 (fromList [3, 5]) == Just 5
lookupGE 6 (fromList [3, 5]) == Nothing

isSubsetOf :: Ord a => Set a -> Set a -> Bool Источник

O(n+m). Является ли это подмножеством? (s1 isSubsetOf s2) показывает, является ли s1 подмножеством s2.

isProperSubsetOf :: Ord a => Set a -> Set a -> Bool Источник

O(n+m). Является ли это собственным подмножеством? (т.е. подмножество, но не равно).

Конструкции

empty :: Set a Источник

O(1). Пустое множество.

singleton :: a -> Set a Источник

O(1). Создать множество-одиночку.

insert :: Ord a => a -> Set a -> Set a Источник

O(log n). Вставить элемент в множество. Если множество уже содержит элемент, равный заданному значению, он заменяется новым значением.

delete :: Ord a => a -> Set a -> Set a Source

O(log n). Удалить элемент из множества.

Комбинирование

union :: Ord a => Set a -> Set a -> Set a Source

O(n+m). Объединение двух множеств, отдавая предпочтение первому множеству при совпадении элементов. Реализация использует эффективный алгоритм hedge-union.

unions :: Ord a => [Set a] -> Set a Source

Объединение списка множеств: (unions == foldl union empty).

difference :: Ord a => Set a -> Set a -> Set a Source

O(n+m). Разность двух множеств. Реализация использует эффективный алгоритм hedge, сопоставимый с hedge-union.

intersection :: Ord a => Set a -> Set a -> Set a Source

O(n+m). Пересечение двух множеств. Реализация использует эффективный алгоритм hedge, сопоставимый с hedge-union. Элементы результата берутся из первого множества, поэтому, например

import qualified Data.Set as S
data AB = A | B deriving Show
instance Ord AB where compare _ _ = EQ
instance Eq AB where _ == _ = True
main = print (S.singleton A `S.intersection` S.singleton B,
              S.singleton B `S.intersection` S.singleton A)

выводит (fromList [A],fromList [B]).

Фильтрация

filter :: (a -> Bool) -> Set a -> Set a Source

O(n). Фильтрует все элементы, удовлетворяющие предикату.

partition :: (a -> Bool) -> Set a -> (Set a, Set a) Source

O(n). Разделяет множество на два множества: одно содержит все элементы, удовлетворяющие предикату, а другое — все элементы, которые не удовлетворяют предикату. См. также split.

split :: Ord a => a -> Set a -> (Set a, Set a) Source

O(log n). Выражение (split x set) представляет собой пару (set1,set2), где set1 содержит элементы set, меньшие x, а set2 содержит элементы set, большие x.

splitMember :: Ord a => a -> Set a -> (Set a, Bool, Set a) Source

O(log n). Выполняет split, а также возвращает, был ли элемент-опорный найден в исходном множестве.

splitRoot :: Set a -> [Set a] Source

O(1). Разделяет множество на части, основываясь на структуре базового дерева. Эта функция полезна для параллельной обработки множества.

Гарантии относительно размеров частей не даётся; внутренний, но детерминированный процесс определяет это. Однако гарантируется, что возвращаемые части будут в порядке возрастания (все элементы в первой подмножестве меньше всех элементов во второй и так далее).

Примеры:

splitRoot (fromList [1..6]) ==
  [fromList [1,2,3],fromList [4],fromList [5,6]]

splitRoot empty == []

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

Индексирование

lookupIndex :: Ord a => a -> Set a -> Maybe Int Source

O(log n). Найти индекс элемента, который является его нулевым индексом в отсортированной последовательности элементов. Индекс — число от 0 до, но не включая, size множества.

isJust   (lookupIndex 2 (fromList [5,3])) == False
fromJust (lookupIndex 3 (fromList [5,3])) == 0
fromJust (lookupIndex 5 (fromList [5,3])) == 1
isJust   (lookupIndex 6 (fromList [5,3])) == False

findIndex :: Ord a => a -> Set a -> Int Source

O(log n). Возвращает индекс элемента, который является его нулевым индексом в отсортированной последовательности элементов. Индекс — число от 0 до, но не включая, size множества. Вызывает error, если элемент не является member множества.

findIndex 2 (fromList [5,3])    Error: element is not in the set
findIndex 3 (fromList [5,3]) == 0
findIndex 5 (fromList [5,3]) == 1
findIndex 6 (fromList [5,3])    Error: element is not in the set

elemAt :: Int -> Set a -> a Source

O(log n). Получить элемент по его индексу, т.е. по его нулевому индексу в отсортированной последовательности элементов. Если индекс вне диапазона (меньше нуля, больше или равен size множества), вызывается error.

elemAt 0 (fromList [5,3]) == 3
elemAt 1 (fromList [5,3]) == 5
elemAt 2 (fromList [5,3])    Error: index out of range

deleteAt :: Int -> Set a -> Set a Source

O(log n). Удалить элемент по индексу, т.е. по его нулевому индексу в отсортированной последовательности элементов. Если индекс вне диапазона (меньше нуля, больше или равен size множества), вызывается error.

deleteAt 0    (fromList [5,3]) == singleton 5
deleteAt 1    (fromList [5,3]) == singleton 3
deleteAt 2    (fromList [5,3])    Error: index out of range
deleteAt (-1) (fromList [5,3])    Error: index out of range

Картирование

map :: Ord b => (a -> b) -> Set a -> Set b Source

O(n*log n). map f s — множество, полученное путём применения f к каждому элементу s.

Стоит отметить, что размер результата может быть меньше, если для некоторых (x,y), x /= y && f x == f y

mapMonotonic :: (a -> b) -> Set a -> Set b Source

O(n).

mapMonotonic f s == map f s, но работает только, когда f монотонная. Предпосылка не проверяется. Полуформально, имеем:

and [x < y ==> f x < f y | x <- ls, y <- ls]
                    ==> mapMonotonic f s == map f s
    where ls = toList s

Складывание

foldr :: (a -> b -> b) -> b -> Set a -> b Source

O(n). Складывание элементов множества с помощью заданного бинарного оператора справа налево, так что foldr f z == foldr f z . toAscList.

Например,

toAscList set = foldr (:) [] set

foldl :: (a -> b -> a) -> a -> Set b -> a Source

O(n). Складывание элементов множества с помощью заданного бинарного оператора слева направо, так что foldl f z == foldl f z . toAscList.

Например,

toDescList set = foldl (flip (:)) [] set

Строгие складывания

foldr' :: (a -> b -> b) -> b -> Set a -> b Source

O(n). Строгая версия foldr. Каждое применение оператора вычисляется до использования результата в следующем применении. Эта функция строгая по начальному значению.

foldl' :: (a -> b -> a) -> a -> Set b -> a Source

O(n). A strict version of foldl. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

Legacy folds

fold :: (a -> b -> b) -> b -> Set a -> b Source

O(n). Fold the elements in the set using the given right-associative binary operator. This function is an equivalent of foldr and is present for compatibility only.

Please note that fold will be deprecated in the future and removed.

Min/Max

findMin :: Set a -> a Source

O(log n). The minimal element of a set.

findMax :: Set a -> a Source

O(log n). The maximal element of a set.

deleteMin :: Set a -> Set a Source

O(log n). Delete the minimal element. Returns an empty set if the set is empty.

deleteMax :: Set a -> Set a Source

O(log n). Delete the maximal element. Returns an empty set if the set is empty.

deleteFindMin :: Set a -> (a, Set a) Source

O(log n). Delete and find the minimal element.

deleteFindMin set = (findMin set, deleteMin set)

deleteFindMax :: Set a -> (a, Set a) Source

O(log n). Delete and find the maximal element.

deleteFindMax set = (findMax set, deleteMax set)

maxView :: Set a -> Maybe (a, Set a) Source

O(log n). Retrieves the maximal key of the set, and the set stripped of that element, or Nothing if passed an empty set.

minView :: Set a -> Maybe (a, Set a) Source

O(log n). Retrieves the minimal key of the set, and the set stripped of that element, or Nothing if passed an empty set.

Conversion

List

elems :: Set a -> [a] Source

O(n). An alias of toAscList. The elements of a set in ascending order. Subject to list fusion.

toList :: Set a -> [a] Source

O(n). Convert the set to a list of elements. Subject to list fusion.

fromList :: Ord a => [a] -> Set a Source

O(n*log n). Create a set from a list of elements.

If the elemens are ordered, linear-time implementation is used, with the performance equal to fromDistinctAscList.

Ordered list

toAscList :: Set a -> [a] Source

O(n). Convert the set to an ascending list of elements. Subject to list fusion.

toDescList :: Set a -> [a] Source

O(n). Convert the set to a descending list of elements. Subject to list fusion.

fromAscList :: Eq a => [a] -> Set a Source

O(n). Build a set from an ascending list in linear time. The precondition (input list is ascending) is not checked.

fromDistinctAscList :: [a] -> Set a Source

O(n). Build a set from an ascending list of distinct elements in linear time. The precondition (input list is strictly ascending) is not checked.

Debugging

showTree :: Show a => Set a -> String Source

O(n). Show the tree that implements the set. The tree is shown in a compressed, hanging format.

showTreeWith :: Show a => Bool -> Bool -> Set a -> String Source

O(n). The expression (showTreeWith hang wide map) shows the tree that implements the set. If hang is True, a hanging tree is shown otherwise a rotated tree is shown. If wide is True, an extra wide version is shown.

Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1..5]
4
+--2
|  +--1
|  +--3
+--5

Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1..5]
4
|
+--2
|  |
|  +--1
|  |
|  +--3
|
+--5

Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1..5]
+--5
|
4
|
|  +--3
|  |
+--2
   |
   +--1

valid :: Ord a => Set a -> Bool Source

O(n). Test if the internal set structure is valid.