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

0

представляет собой расширение модуля IntSet (см. раздел 8.16.), в котором все программные  сущности работают с ключами произвольного типа. Такие множества получаются более общими, нежели множества с целочисленными ключами.

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

import Data.Set   (Set)

import qualified  Data.Set   as Set

Реализация множеств, предлагаемая в этом модуле, основана на  так  называемых деревьях, сбалансированных  по размеру (или  деревьях ограниченного баланса), как это описано в работах [2, 17].

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

Единственный определённый в рассматриваемом модуле алгебраический тип данных — Set.

Тип: Set

Описание: тип для представления множеств.

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

data  Set  a

=  Tip

| Bin  !Size a !(Set a)  !(Set a) type  Size  = Int

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

Data, Eq, Monoid, Ord, Read и Show.

Функция: mapMonotonic

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

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

mapMonotonic :: (a  ->  b)  ->  Set  a  ->  Set  b mapMonotonic f Tip                       =  Tip

mapMonotonic f (Bin sz  x  l r) = Bin  sz  (f x) (mapMonotonic f l)  (mapMonotonic f r)

Функция: findMin

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

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

findMin :: Set  a  ->  a findMin  (Bin _ x  Tip  r)  = x

findMin (Bin _ x  l r)      =  findMin l

findMin Tip                         = error "Set.findMin: empty set  has no  minimal  element"

Функция: findMax

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

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

findMax  :: Set  a  ->  a findMax  (Bin _ x  l Tip)  = x

findMax  (Bin _ x  l r)      =  findMax  r

findMax  Tip                         = error "Set.findMax: empty set  has no  maximal element"

Функция: deleteMin

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

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

deleteMin :: Set  a  ->  Set  a deleteMin (Bin _  x  Tip  r) = r

deleteMin (Bin _ x  l r)   = balance  x  (deleteMin l) r deleteMin Tip                         =  Tip

Функция: deleteMax

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

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

deleteMax  :: Set  a  ->  Set  a deleteMax  (Bin _  x  l Tip) = l

deleteMax  (Bin _ x  l r)   = balance  x  l  (deleteMax  r) deleteMax  Tip                         =  Tip

Функция: deleteFindMin

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

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

deleteFindMin :: Set  a ->  (a,  Set  a) deleteFindMin t =  case t of

Bin  _ x  Tip  r ->  (x, r)

Bin  _ x  l r   ->  let (xm,  l’) =  deleteFindMin l in    (xm, balance  x  l’ r)

Tip                     ->  (error  "Set.deleteFindMin: can not  return

the  minimal  element  of an empty  set", Tip)

Функция: deleteFindMax

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

deleteFindMax  :: Set  a ->  (a,  Set  a) deleteFindMax  t =  case t of

Bin  _ x  l Tip  ->  (x, l)

Bin  _ x  l r   ->  let (xm,  r’) =  deleteFindMax  r in    (xm,  balance  x  l r’)

Tip                     ->  (error  "Set.deleteFindMax: can not  return

the  maximal element  of an empty  set", Tip)

Функция: minView

Описание: вариант функции deleteFindMin (см. стр. 398), который заключает результат в монаду. Соответственно, если на вход функции подано пустое дерево, вызывается монадический  метод fail (см. стр. 211).

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

minView :: Monad  m   => Set  a ->  m   (Set  a, a) minView Tip  = fail  "Set.minView:  empty set" minView x      =  return (swap $ deleteFindMin x)

Функция: maxView

Описание: вариант функции deleteFindMax  (см. стр. 399), который заключает результат в монаду. Соответственно, если на вход функции подано пустое дерево, вызывается монадический  метод fail (см. стр. 211).

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

maxView  :: Monad  m   => Set  a ->  m  (Set  a, a) maxView  Tip  = fail  "Set.maxView: empty set" maxView  x      = return (swap $ deleteFindMax  x)

Функция: valid

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

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

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

valid t = balanced  t &&  ordered  t &&  validsize t

balanced  ::  Set  a ->  Bool balanced  t =  case t of

Tip                     ->  True

Bin  sz  x  l r  ->  (size l + size r  <=  1 || (size l <=  delta * size r && size r <= delta *  size l)) && balanced l &&  balanced  r

ordered  t = bounded (const True)  (const True)  t where

bounded lo hi t = case t of

Tip                   ->  True

Bin  sz  x  l r ->  (lo x) &&  (hi x) && bounded  lo  (<  x)  l  && bounded  (>  x) hi  r

validsize t = (realsize t ==  Just (size t)) where

realsize t = case t of

Tip                   ->  Just  0

Bin  sz  x  l r ->  case (realsize l, realsize r) of

(Just n, Just  m) | n + m   + 1 == sz  ->  Just  sz other                                                         ->  Nothing

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

8.27.    Модуль STRef

В модуле STRef описаны изменяемые ссылки в строгой монаде  ST (см. подраздел 7.5.3.). Использование:

import  Data.STRef

Главным (и единственным) алгебраическим типом данных в этом модуле является тип STref.

Тип: STRef

Описание: значение STRef s a является изменяемой ссылкой в состоянии s, содержащей некоторое значение a.

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

data  STRef s  a = …

Тип определён в виде примитива.

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

и Eq.

Функция: newSTRef

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

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

newSTRef  :: a ->  ST  s  (STRef s  a)

Функция определена в виде примитива.

Функция: readSTRef

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

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

readSTRef :: STRef s  a ->  ST  s  a

Функция определена в виде примитива.

Функция: writeSTRef

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

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

writeSTRef :: STRef s  a ->  a ->  ST  s  ()

Функция определена в виде примитива.

Функция: modifySTRef

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

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

modifySTRef :: STRef s  a ->  (a  ->  a)  ->  ST  s  () modifySTRef ref f = writeSTRef ref  . f =<<  readSTRef ref

8.27.1.    Модуль Lazy

Модуль Lazy содержит те же самые определения, что и модуль STRef, за исключением того, что он поддерживает отложенные  вычисления. Поскольку он является «зависимым» модулем от STRef, его импорт должен выглядеть следующим образом:

import  Data.STRef.Lazy

Никаких иных программных сущностей, кроме одноимённых в модуле STRef, в рассматриваемом модуле не описано.

8.27.2.    Модуль Strict

В целях единообразия (по отношению к модулю Lazy) в стандартной поставке библиотек языка Haskell имеется модуль Strict, который является «подчинённым» модулю STRef. Этот модуль всего лишь реимпортирует сам модуль STRef, не добавляя никаких новых определений.

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

По теме:

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