Главная » Haskell » Модуль IntSet

0

В модуле IntSet содержится описание не менее важной идиомы в программировании, как множество (на целых числах). Реализация множеств достаточно эффективна и основана на использовании  специального вида деревьев (вместо обычных сбалансированных деревьев), описанных в работах [19, 16]. В этом модуле ипользуются имена функций, которые конфликтуют со многими функциями из стандартного модуля Prelude,  поэтому использование его выглядит следующим образом:

import Data.IntSet (IntSet)

import qualified  Data.IntSet as IntSet

Реализация функций для работы с множествами, предлагаемая в этом модуле, достаточно эффективна и имеет в большинстве случаев сложность O(min(n, W )), где W — количество битов для представления ключей.

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

Главный алгебраический тип данных, описанный в этом модуле,  — IntSet.

Этот тип используется для представления множеств целых числе.

Тип: IntSet

Описание: множество целых чисел.

Определение:

data  IntSet

= Nil

| Tip  !Int

| Bin  !Prefix !Mask  !IntSet !IntSet

Для удобства здесь также  определены два синонима типов:  Prefix и Mask, которые равны типу Int.

Для  типа  IntSet определены  экземпляры следующих классов:  Data,  Eq,

Monoid, Ord, Read, Show и Typeable.

Функция: (\\)

Описание: синоним функции difference (см. стр. 353).

Определение:

(\\) :: IntSet ->  IntSet  ->  IntSet m1  \\ m2  =  difference m1  m2

Функция: null

Описание: возвращает значение True, если заданное множество пустое.

Определение:

null :: IntSet  ->  Bool null  Nil    = True

null other = False

Функция: size

Описание: возвращает  кардинальное  число заданного множества  (количество элементов в множестве.

Определение:

size ::  IntSet  ->  Int size t = case  t of

Bin  p m   l r ->  size l  +  size r Tip  y             ->  1

Nil            ->  0

Функция: member

Описание: предикат, возвращающий значение True, если заданный элемент принадлежит заданному множеству.

Определение:

member  :: Int ->  IntSet  ->  Bool member  x  t =  case t of

Bin  p m   l r | nomatch x  p m   ->  False

| zero  x  m

->  member  x  l

| otherwise

->  member  x  r

Tip  y

->  (x == y)

Nil

->  False

Функция: notMember

Описание: обращение предиката member.

Определение:

notMember :: Int ->  IntSet ->  Bool notMember k  = not  .  member  k

Функция: isSubsetOf

Описание: предикат, возвращающий значение True, если заданное множество является подмножеством множества, передаваемого вторым аргументом. Определение:

isSubsetOf :: IntSet ->  IntSet ->  Bool

isSubsetOf t1@(Bin  p1 m1  l1 r1) t2@(Bin  p2 m2  l2 r2)

| shorter m1  m2  = False

| shorter m2  m1  = match p1 p2 m2  &&  (if zero  p1 m2

then  isSubsetOf  t1 l2 else  isSubsetOf  t1 r2)

| otherwise        = (p1  == p2)  &&  isSubsetOf l1  l2  &&  isSubsetOf r1  r2 isSubsetOf (Bin  p m   l r) t = False

isSubsetOf (Tip  x) t             =  member  x  t isSubsetOf Nil  t           = True

Функция: isProperSubsetOf

Описание: предикат, возвращающий значение True, если заданное множество является собственным подмножеством (подмножеством, не равным самому множеству) множества, передаваемого вторым аргументом.

Определение:

isProperSubsetOf :: IntSet ->  IntSet  ->  Bool isProperSubsetOf t1  t2  = case  subsetCmp t1 t2 of

LT  ->  True ge  ->  False

subsetCmp t1@(Bin  p1 m1  l1 r1) t2@(Bin  p2 m2  l2 r2)

| shorter m1  m2  = GT

| shorter m2  m1  = subsetCmpLt

| p1 == p2           = subsetCmpEq

|  otherwise          =  GT where

subsetCmpLt | nomatch p1 p2 m2  = GT

| zero  p1 m2                 = subsetCmp t1 l2

| otherwise             = subsetCmp t1  r2 subsetCmpEq  = case (subsetCmp l1 l2,  subsetCmp r1  r2) of

(GT,  _  ) ->  GT

(_  ,  GT) ->  GT (EQ,  EQ) ->  EQ other        ->  LT

subsetCmp (Bin p m   l r)  t = GT subsetCmp (Tip  x) (Tip y)

| x  == y        = EQ

|  otherwise =  GT subsetCmp  (Tip x) t

| member  x  t = LT

|  otherwise    =  GT subsetCmp  Nil Nil = EQ subsetCmp Nil  t      = LT

Функция: empty

Описание: создаёт пустое множество.

Определение:

empty  ::  IntSet empty =  Nil

Функция: singleton

Описание: создаёт множество из одного элемента.

Определение:

singleton :: Int  ->  IntSet singleton  x  = Tip  x

Функция: insert

Описание: добавляет новый элемент в заданное множество. Если  элемент уже присутствует в множестве, он заменяется.

Определение:

insert :: Int ->  IntSet  ->  IntSet insert x  t =  case t of

Bin  p m   l r | nomatch x  p m   ->  join x  (Tip x) p t

| zero  x  m

->  Bin  p m   (insert  x  l) r

| otherwise

->  Bin  p m   l (insert  x  r)

Tip  y

| x  == y

->  Tip  x

| otherwise

->  join x  (Tip x) y  t

Nil

->  Tip  x

Функция: delete

Описание: удаляет элемент из множества. Если в заданном множестве нет удаляемого элемента, возвращается оригинальное множество.

Определение:

delete :: Int ->  IntSet ->  IntSet delete x  t = case t  of

Bin  p m   l r | nomatch x  p m   ->  t

| zero  x  m

->  bin  p m  (delete  x  l) r

| otherwise

->  bin  p m   l  (delete x  r)

Tip  y

| x  == y

->  Nil

| otherwise

->  t

Nil

->  Nil

Функция: union

Описание: возвращает объединение двух множеств.

Определение:

union  :: IntSet ->  IntSet ->  IntSet

union  t1@(Bin  p1 m1  l1 r1) t2@(Bin  p2 m2  l2 r2)

| shorter m1  m2  = union1

| shorter m2  m1  = union2

| p1 == p2           = Bin  p1 m1  (union l1 l2)  (union r1  r2)

| otherwise        = join  p1 t1 p2 t2 where

union1  | nomatch p2 p1 m1  = join p1 t1 p2 t2

| zero  p2 m1                 = Bin  p1 m1  (union l1 t2) r1

| otherwise             = Bin  p1 m1  l1  (union r1  t2) union2  | nomatch p1 p2 m2  =  join p1 t1 p2 t2

| zero  p1 m2                 = Bin  p2 m2  (union t1 l2)  r2

| otherwise             = Bin  p2 m2  l2  (union t1 r2) union  (Tip x) t = insert x  t

union  t (Tip x) =  insertR x  t union  Nil t      = t

union  t Nil     = t

insertR :: Int ->  IntSet ->  IntSet insertR x  t = case t  of

Bin  p m   l r | nomatch x  p m   ->  join x  (Tip x) p t

| zero  x  m

->  Bin  p m  (insert x  l) r

| otherwise

->  Bin  p m   l  (insert x  r)

Tip  y

| x  == y

->  t

| otherwise

->  join x  (Tip  x)  y  t

Nil                                  ->  Tip  x

Функция: unions

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

Определение:

unions  :: [IntSet] ->  IntSet

unions  xs  = foldlStrict union  empty xs

Функция: difference

Описание: возвращает разность двух множеств.

Определение:

difference :: IntSet ->  IntSet ->  IntSet

difference t1@(Bin  p1 m1  l1 r1) t2@(Bin  p2 m2  l2 r2)

| shorter m1  m2  = difference1

| shorter m2  m1  = difference2

| p1 == p2           = bin  p1 m1  (difference l1 l2) (difference r1  r2)

| otherwise          =  t1 where

difference1 | nomatch p2 p1 m1  = t1

| zero  p2 m1                 = bin  p1 m1  (difference l1 t2) r1

| otherwise             = bin  p1 m1  l1  (difference  r1  t2) difference2 | nomatch p1 p2 m2  = t1

| zero  p1 m2                 = difference t1 l2

| otherwise             =  difference t1 r2 difference t1@(Tip  x) t2 |  member  x  t2 = Nil

|  otherwise      = t1 difference Nil t          =  Nil

difference t (Tip x) =  delete x  t difference t  Nil       = t

Функция: intersection

Описание: возвращает пересечение двух множеств.

Определение:

intersection :: IntSet ->  IntSet ->  IntSet

intersection t1@(Bin  p1 m1  l1 r1) t2@(Bin  p2 m2  l2 r2)

| shorter m1  m2  = intersection1

| shorter m2  m1  = intersection2

| p1 == p2           = bin  p1 m1  (intersection l1 l2) (intersection r1  r2)

| otherwise          =  Nil where

intersection1 | nomatch p2 p1 m1  = Nil

| zero  p2 m1                 = intersection l1 t2

| otherwise             =  intersection r1  t2 intersection2 | nomatch  p1 p2 m2  = Nil

| zero  p1 m2                 = intersection t1 l2

| otherwise             =  intersection t1 r2 intersection t1@(Tip  x) t2  |  member  x  t2 = t1

|  otherwise     = Nil intersection t  (Tip x) = case lookup  x  t of

Just  y    ->  Tip  y Nothing  ->  Nil

intersection  Nil t = Nil intersection  t Nil = Nil

Функция: filter

Описание: фильтрует заданное множество в соответствии с некоторым предикатом.

Определение:

filter :: (Int ->  Bool)   ->  IntSet ->  IntSet filter pred  t =  case t of

Bin  p m   l r        ->  bin  p m   (filter pred  l)  (filter pred  r) Tip  x  | pred  x       ->  t

|  otherwise ->  Nil Nil                             ->  Nil

Функция: partition

Описание: возвращает пару подмножеств заданного множества,  первое из которых составляют элементы, удовлетворяющие заданному предикату, второе  — не удовлетворяющие соответственно.

Определение:

partition :: (Int ->  Bool)   ->  IntSet ->  (IntSet, IntSet) partition pred  t = case t of

Bin  p m   l r ->  let (l1, l2) =  partition pred  l (r1, r2) =  partition pred  r

in   (bin p m   l1 r1,  bin  p m   l2 r2) Tip  x  | pred  x       ->  (t,  Nil)

| otherwise ->  (Nil, t) Nil                             ->  (Nil,  Nil)

Функция: split

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

Определение:

split :: Int ->  IntSet ->  (IntSet,IntSet) split  x  t = case  t  of

Bin  p m   l r | m   < 0         ->  if x  >= 0

then  let (lt, gt) =  split’ x  l in    (union r lt, gt)

else  let (lt, gt) =  split’ x  r in    (lt,  union  gt l)

| otherwise ->  split’ x  t Tip  y  | x  > y                     ->  (t, Nil)

| x  < y                     ->  (Nil, t)

| otherwise           ->  (Nil, Nil) Nil                                        ->  (Nil, Nil)

split’ :: Int ->  IntSet ->  (IntSet,  IntSet) split’ x  t = case t of

Bin  p m   l r | match x  p m   ->  if zero  x  m

then  let (lt, gt) =  split’ x  l in    (lt, union  gt r)

else  let (lt, gt) =  split’ x  r in  (union l lt, gt)

| otherwise     ->  if x  < p

then  (Nil,  t) else  (t,  Nil)

Tip  y  | x  > y                        ->  (t, Nil)

| x  < y                        ->  (Nil, t)

| otherwise              ->  (Nil, Nil) Nil                                            ->  (Nil, Nil)

Функция: splitMember

Описание: вариант функции split, который возвращает не только пару подмножеств, но и флаг присутствия заданного элемента в исходном множестве (значение типа Bool).

Определение:

splitMember   :: Int ->  IntSet ->  (IntSet,  Bool, IntSet) splitMember   x  t = case t of

Bin  p m   l r | m   < 0 ->  if x  >= 0

then  let (lt, found, gt) =  splitMember’ x  l in    (union  r lt, found, gt)

else  let (lt, found, gt) =  splitMember’ x  r in  (lt,  found, union  gt l)

| otherwise ->  splitMember’ x  t Tip  y  | x  > y                     ->  (t, False, Nil)

| x  < y                     ->  (Nil,  False, t)

| otherwise            ->  (Nil,  True,   Nil) Nil                                        ->  (Nil, False, Nil)

splitMember’ :: Int ->  IntSet ->  (IntSet,  Bool, IntSet) splitMember’ x  t = case t of

Bin  p m   l r |  match  x  p  m  -> if  zero  x  m

then  let (lt, found, gt) =  splitMember   x  l in  (lt,  found, union  gt r)

else  let (lt, found, gt) =  splitMember   x  r in  (union  l lt, found, gt)

| otherwise      ->  if x  < p

then  (Nil,  False,  t) else  (t,  False,  Nil)

Tip  y  | x  > y                        ->  (t, False, Nil)

| x  < y                        ->  (Nil,  False, t)

| otherwise               ->  (Nil,  True,   Nil) Nil                                            ->  (Nil, False, Nil)

Функция: map

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

Определение:

map  :: (Int->Int) ->  IntSet  ->  IntSet map  f =  fromList . List.map f .  toList

Функция: fold

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

Определение:

fold :: (Int ->  b ->  b)  ->  b ->  IntSet ->  b fold f z  t = case t of

Bin  0 m   l r | m   < 0 ->  foldr f (foldr  f  z  l) r Bin  p m   l r          ->  foldr  f  z  t

Tip  x                             ->  f x  z Nil                                ->  z

foldr :: (Int ->  b ->  b)  ->  b ->  IntSet ->  b foldr f z  t = case t of

Bin  p m   l r ->  foldr f (foldr  f  z  r) l Tip  x             ->  f x  z

Nil            ->  z

Функция: elems

Описание: возвращает список элементов множества.

Определение:

elems :: IntSet  ->  [Int] elems s  = toList  s

Функция: toList

Описание: синоним функции elems.

Определение:

toList :: IntSet  ->  [Int] toList t  = fold (:) [] t

Функция: fromList

Описание: создаёт множество на основе заданного списка целых чисел.

Определение:

fromList :: [Int] ->  IntSet

fromList xs  = foldlStrict  ins  empty xs where

ins   t x   =  insert x  t

Функция: toAscList

Описание: создаёт упорядоченный от меньшего к большему список  на основе заданного множества.

Определение:

toAscList ::  IntSet ->  [Int] toAscList t =  toList t

Функция: fromAscList

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

Определение:

fromAscList ::  [Int] ->  IntSet fromAscList xs  =  fromList  xs

Функция: fromDistinctAscList

Описание: вариант функции fromAscList, в который необходимо передавать список, не имеющий повторяющихся элементов.

Определение:

fromDistinctAscList ::  [Int] ->  IntSet fromDistinctAscList xs  =  fromList  xs

Функция: showTree

Описание: преобразует  дерево, представляющее  множество, в строку. Функция обычно используется в целях отладки.

Определение:

showTree ::  IntSet ->  String

showTree s  = showTreeWith  True  False  s

Функция: showTreeWith

Описание: преобразует дерево, представляющее  множество, в строку. Более общая функция, чем showTree. Первый аргумент отвечает за способ вывода. Если он принимает значение True, в строку выводится дерево с отступами, в противном случае  — циклическое дерево. Если второй аргумент равен True, то при преобразовании не учитывается получаемая ширина подстрок. Функция обычно используется в целях отладки.

Определение:

showTreeWith :: Bool  ->  Bool  ->  IntSet ->  String

showTreeWith hang wide  t | hang           = (showsTreeHang wide  [] t) ""

| otherwise = (showsTree  wide  []  []  t) ""

showsTree :: Bool  ->  [String] ->  [String] ->  IntSet  ->  ShowS showsTree wide  lbars rbars t

=  case  t  of

Bin  p m   l r ->  showsTree wide  (withBar rbars)  (withEmpty rbars)  r .

showWide  wide  rbars .

showsBars lbars . showString  (showBin  p m) . showString  "\n"  .

showWide  wide  lbars .

showsTree wide  (withEmpty lbars)  (withBar lbars)  l

Tip  x             ->  showsBars lbars . showString  " " . shows x  .  showString  "\n" Nil            ->  showsBars lbars . showString  "|\n"

showsTreeHang  :: Bool  ->  [String] ->  IntSet  ->  ShowS showsTreeHang  wide  bars  t

=  case  t  of

Bin  p m   l r ->  showsBars bars  . showString  (showBin  p m) . showString  "\n"  .

showWide  wide  bars  .

showsTreeHang  wide  (withBar bars) l .

showWide  wide  bars  .

showsTreeHang  wide  (withEmpty bars)  r

Tip  x             ->  showsBars bars  . showString  " " . shows x  .  showString  "\n" Nil            ->  showsBars bars  . showString  "|\n"

showBin p m   = "*" -++ show (p, m)

showWide  wide  bars  | wide           = showString  (concat (reverse bars))  . showString  "|\n"

| otherwise = id

showsBars :: [String]  ->  ShowS showsBars  bars  = case bars  of

[] ->  id

_   ->  showString  (concat (reverse (tail bars))) . showString  node

node                    =  "+–" withBar bars      =  "|    ":bars withEmpty  bars  = "      ":bars

8.16.     Модуль IORef

Модуль IORef содержит описания программных сущностей,  предоставляющих механизмы работы с изменяемыми ссылками в рамках монады IO. Использование:

import  Data.IORef

Все программные сущности, описанные в этом модуле,  определены в виде примитивов, поэтому упоминание об этом приводиться не будет.

Тип: IORef

Описание: изменяемая ссылка (переменная) в рамках монады IO.

Определение:

Для  данного типа определены  экземпляры следующих классов:  Typeable,

Typeable1 и Eq.

Функция: newIORef

Описание: создаёт новую ссылку.

Определение:

newIORef :: a ->  IO (IORef  a)

Функция:  readIORef

Описание: возвращает значение заданной ссылки.

Определение:

readIORef  :: IORef  a ->  IO a

Функция: writeIORef

Описание: записывает новое значение в заданную ссылку.

Определение:

writeIORef :: IORef  a ->  a ->  IO ()

Функция: modifyIORef

Описание: изменяет значение в заданной ссылке при помощи некоторой функции.

Определение:

modifyIORef  :: IORef  a ->  (a  ->  a)  ->  IO ()

Функция: atomicModifyIORef

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

atomicModifyIORef :: IORef  a ->  (a  ->  (a, b)) ->  IO b

Функция: mkWeakIORef

Описание: создаёт слабый указатель на ссылку.

Определение:

mkWeakIORef  :: IORef  a ->  IO () ->  IO (Weak (IORef  a))

Источник: Душкин Р. В., Справочник по языку Haskell. М.: ДМК Пресс, 2008. 544 с., ил.

По теме:

  • Комментарии