Data.IntSet

 import Data.IntSet (IntSet)
 import qualified Data.IntSet as IntSet

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

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

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

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

delete undefined s  ==  undefined

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

data IntSet Источник

Множество целых чисел.

type Ключ = Int Источник

Операторы

(\\) :: IntSet -> IntSet -> IntSet infixl 9 Источник

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

Запрос

пустое :: IntSet -> Bool Источник

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

размер :: IntSet -> Int Источник

O(n). Мощность множества.

принадлежит :: Ключ -> IntSet -> Bool Источник

O(min(n,W)). Является ли значение элементом множества?

неПринадлежит :: Ключ -> IntSet -> Bool Источник

O(min(n,W)). Не является ли элемент элементом множества?

lookupLT :: Ключ -> IntSet -> Maybe Ключ Источник

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

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

lookupGT :: Ключ -> IntSet -> Maybe Ключ Источник

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

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

lookupLE :: Ключ -> IntSet -> Maybe Ключ Источник

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

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

lookupGE :: Ключ -> IntSet -> Maybe Ключ Источник

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

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

являетсяПодмножеством :: IntSet -> IntSet -> Bool Источник

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

являетсяПравильнымПодмножеством :: IntSet -> IntSet -> Bool Источник

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

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

пустоеМножество :: IntSet Источник

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

одиночныйЭлемент :: Ключ -> IntSet Источник

O(1). Множество из одного элемента.

вставить :: Ключ -> IntSet -> IntSet Источник

O(min(n,W)). Добавить значение в множество. Нет левого или правого смещения для IntSet.

delete :: Ключ -> МножествоЦелых -> МножествоЦелых Источник

O(min(n,W)). Удаление значения из множества. Возвращает исходное множество, если значение отсутствовало.

Объединение

union :: МножествоЦелых -> МножествоЦелых -> МножествоЦелых Источник

O(n+m). Объединение двух множеств.

unions :: [МножествоЦелых] -> МножествоЦелых Источник

Объединение списка множеств.

difference :: МножествоЦелых -> МножествоЦелых -> МножествоЦелых Источник

O(n+m). Разность между двумя множествами.

intersection :: МножествоЦелых -> МножествоЦелых -> МножествоЦелых Источник

O(n+m). Пересечение двух множеств.

Фильтр

filter :: (Ключ -> Булево) -> МножествоЦелых -> МножествоЦелых Источник

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

partition :: (Ключ -> Булево) -> МножествоЦелых -> (МножествоЦелых, МножествоЦелых) Источник

O(n). Разделение множества по некоторому предикату.

split :: Ключ -> МножествоЦелых -> (МножествоЦелых, МножествоЦелых) Источник

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

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

splitMember :: Ключ -> МножествоЦелых -> (МножествоЦелых, Булево, МножествоЦелых) Источник

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

splitRoot :: МножествоЦелых -> [МножествоЦелых] Источник

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

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

Примеры:

splitRoot (fromList [1..120]) == [fromList [1..63],fromList [64..120]]
splitRoot empty == []

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

Преобразование

map :: (Ключ -> Ключ) -> МножествоЦелых -> МножествоЦелых Источник

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

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

Склады

foldr :: (Ключ -> b -> b) -> b -> МножествоЦелых -> b Источник

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

Например,

toAscList set = foldr (:) [] set

foldl :: (a -> Ключ -> a) -> a -> МножествоЦелых -> a Источник

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

Например,

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

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

foldr' :: (Ключ -> b -> b) -> b -> МножествоЦелых -> b Источник

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

foldl' :: (a -> Ключ -> a) -> a -> МножествоЦелых -> a Источник

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

Устаревшие склады

fold :: (Ключ -> b -> b) -> b -> МножествоЦелых -> b Источник

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

Обратите внимание, что fold будет устаревшим в будущем и удаленным.

Минимум/Максимум

findMin :: МножествоЦелых -> Ключ Источник

O(min(n,W)). Минимальный элемент множества.

findMax :: МножествоЦелых -> Ключ Источник

O(min(n,W)). Максимальный элемент множества.

deleteMin :: МножествоЦелых -> МножествоЦелых Источник

O(min(n,W)). Удаление минимального элемента. Возвращает пустое множество, если множество пусто.

Обратите внимание, что это изменение поведения для соответствия Set — версии до 0.5 выбрасывали ошибку, если IntSet было пустым.

deleteMax :: МножествоЦелых -> МножествоЦелых Источник

O(min(n,W)). Удаление максимального элемента. Возвращает пустое множество, если множество пусто.

Обратите внимание, что это изменение поведения для соответствия Set — версии до 0.5 выбрасывали ошибку, если IntSet было пустым.

deleteFindMin :: МножествоЦелых -> (Ключ, МножествоЦелых) Источник

O(min(n,W)). Удаление и поиск минимального элемента.

deleteFindMin set = (findMin set, deleteMin set)

deleteFindMax :: IntSet -> (Ключ, IntSet) Источник

O(min(n,W)). Удаление и поиск максимального элемента.

deleteFindMax set = (findMax set, deleteMax set)

maxView :: IntSet -> МожетБыть (Ключ, IntSet) Источник

O(min(n,W)). Возвращает максимальный ключ множества и множество без этого элемента, или Nothing если передано пустое множество.

minView :: IntSet -> МожетБыть (Ключ, IntSet) Источник

O(min(n,W)). Возвращает минимальный ключ множества и множество без этого элемента, или Nothing если передано пустое множество.

Преобразование

Список

elems :: IntSet -> [Ключ] Источник

O(n). Псевдоним toAscList. Элементы множества в порядке возрастания. Поддерживается слияние списков.

toList :: IntSet -> [Ключ] Источник

O(n). Преобразование множества в список элементов. Поддерживается слияние списков.

fromList :: [Ключ] -> IntSet Источник

O(n*min(n,W)). Создание множества из списка целых чисел.

Отсортированный список

toAscList :: IntSet -> [Ключ] Источник

O(n). Преобразование множества в отсортированный по возрастанию список элементов. Поддерживается слияние списков.

toDescList :: IntSet -> [Ключ] Источник

O(n). Преобразование множества в отсортированный по убыванию список элементов. Поддерживается слияние списков.

fromAscList :: [Ключ] -> IntSet Источник

O(n). Построение множества из отсортированного по возрастанию списка элементов. Предпосылка (входной список отсортирован по возрастанию) не проверяется.

fromDistinctAscList :: [Ключ] -> IntSet Источник

O(n). Построение множества из отсортированного по возрастанию списка уникальных элементов. Предпосылка (входной список строго возрастающий) не проверяется.

Отладка

showTree :: IntSet -> Строка Источник

O(n). Вывод дерева, реализующего множество. Дерево выводится в сжатом висячем формате.

showTreeWith :: Булево -> Булево -> IntSet -> Строка Источник

O(n). Выражение (showTreeWith hang wide map) показывает дерево, реализующее множество. Если hang равно True, отображается висячее дерево, в противном случае вращающееся дерево. Если wide равно True, отображается версия с дополнительной шириной.