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

0

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

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

import Data.Map (Map)

import qualified  Data.Map as Map

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

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

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

Тип: Map

Описание: тип для представления отображения  ключей типа k на значения типа a.

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

data  Map  k  a

= Tip

| Bin  !Size !k a !(Map  k  a)  !(Map  k  a) type  Size  = Int

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

Foldable,  Functor,  Traversable, Data, Eq, Monoid, Ord, Read и Show.

Функция: insertWith’

Описание: вариант функции insertWith (см. стр. 328), в котором комбинирующая функция применяется строго.

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

insertWith’ :: Ord k  => (a  ->  a ->  a)  ->  k  ->  a ->  Map  k  a ->  Map  k  a insertWith’ f k  x  m   = insertWithKey’ (\k  x  y  ->  f x  y)  k  x  m

Функция: insertWithKey’

Описание: вариант функции insertWithKey (см. стр. 328), в котором комбинирующая функция применяется строго.

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

insertWithKey’ :: Ord k  => (k ->  a ->  a ->  a)  ->  k  ->  a ->  Map  k  a ->  Map  k  a insertWithKey’ f kx  x  t

=  case  t  of

Tip                         ->  singleton kx  x

Bin  sy  ky  y  l r ->  case compare kx  ky  of

LT ->  balance  ky  y  (insertWithKey’ f  kx  x  l) r GT  ->  balance  ky  y  l  (insertWithKey’ f kx  x  r)

EQ  ->  let x’ = f kx  x  y  in seq x’ (Bin sy  kx  x’ l r)

Функция: alter

Описание: модифицирует  значение по заданному ключу. Если ключа  не  существует в отображении, то функция создаёт его, записывая  заданное значение. Сложность — O(log n), где n — размер  отображения.

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

alter :: Ord k  => (Maybe a ->  Maybe a)  ->  k  ->  Map  k  a ->  Map  k  a alter f k  t

=  case  t  of

Tip                         ->  case f  Nothing  of Nothing  ->  Tip

Just  x   ->  singleton k  x Bin  sx  kx  x  l r ->  case  compare k  kx  of

LT ->  balance  kx  x  (alter  f  k  l) r GT  ->  balance  kx  x  l (alter f k  r) EQ  ->  case f (Just x) of

Just  x’ ->  Bin  sx  kx  x’ l r Nothing  ->  glue  l r

Функция: mapKeys

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

Сложность — O(n ? log n), где n — размер отображения.

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

mapKeys  :: Ord k2 => (k1  ->  k2)  ->  Map  k1 a  ->  Map  k2 a mapKeys  = mapKeysWith  (\x y  ->  x)

Функция: mapKeysWith

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

разных входных ключах. Сложность — O(n ? log n), где n — размер отображения.

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

mapKeysWith  :: Ord k2 => (a  ->  a ->  a)  ->  (k1  ->  k2)  ->  Map  k1 a  ->  Map  k2 a mapKeysWith  c  f = fromListWith c  . List.map fFirst .  toList

where

fFirst (x, y)  = (f x, y)

Функция: mapKeysMonotonic

Описание: вариант функции mapKeys, который применяется для строго монотонных функций. Данную функцию можно применять тогда, когда известно, что заданная функция для ключей строго монотонна (то есть не проводится проверка на совпадение ключей в результирующем отображении). Проверка на монотонность не производится, а потому разработчик программного обеспечения должен сам гарантировать это свойство у функции. Сложность — O(n), где n — размер  отображения.

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

mapKeysMonotonic :: (k1  ->  k2)  ->  Map  k1 a  ->  Map  k2 a mapKeysMonotonic f Tip                           =  Tip

mapKeysMonotonic f (Bin sz  k  x  l r) = Bin  sz  (f k) x  (mapKeysMonotonic  f l) (mapKeysMonotonic  f r)

Функция: lookupIndex

Описание: возвращает позицию заданного ключа в отображении. Позиция ключа находится в интервале от 0 до размера отображения без единицы. Поскольку  ключ может быть не найден в отображении,  результат функции заключён в монаду (функция обобщена для произвольной монады). Сложность — O(log n), где n — размер отображения.

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

lookupIndex :: (Monad m,Ord k) => k  ->  Map  k  a  ->  m   Int lookupIndex k  t = case lookup  0 t of

Nothing  ->  fail "Data.Map.lookupIndex: Key not  found." Just  x   ->  return  x

where

lookup  idx   Tip                           = Nothing

lookup  idx   (Bin _ kx  x  l r) = case compare  k  kx  of LT  ->  lookup  idx   l

GT  ->  lookup  (idx + size  l  + 1)  r EQ  ->  Just  (idx  +  size l)

Функция: elemAt

Описание: возвращает пару вида (ключ, значение) по заданному  индексу. Если  индекс  выходит  за  границы  отображения,   вызывается функция  error (см. стр. 133). Сложность — O(log n), где n — размер  отображения.

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

elemAt  :: Int ->  Map  k  a  ->  (k, a)

elemAt  i Tip                           = error  "Map.elemAt: index  out  of  range"  elemAt  i (Bin _ kx  x  l r) = case compare i sizeL  of

LT ->  elemAt  i  l

GT  ->  elemAt  (i  sizeL  1)  r EQ  ->  (kx,  x)

where

sizeL  =  size  l

Функция: updateAt

Описание: применяет заданную функцию к элементу отображения по заданному индексу, записывая результат функции в качестве  нового  значения по использованному ключу.  Если индекс выходит за  границы отображения, вызывается функция error (см. стр. 133). Сложность — O(log n), где n — размер отображе ния.

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

updateAt  :: (k ->  a ->  Maybe a)  ->  Int ->  Map  k  a ->  Map  k  a

updateAt  f i Tip                             = error  "Map.updateAt: index  out of range"  updateAt  f i (Bin sx  kx  x  l r) = case compare i  sizeL   of

LT ->  updateAt  f  i l

GT  ->  updateAt  f (i  sizeL   1)  r EQ  ->  case  f kx  x  of

Just  x’ ->  Bin  sx  kx  x’ l r Nothing  ->  glue  l r

where

sizeL  =  size  l

Функция: deleteAt

Описание: удаляет элемент из отображения по заданному индексу. Сложность —

O(log n), где n — размер отображения.

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

deleteAt :: Int ->  Map  k  a  ->  Map  k  a

deleteAt i map  = updateAt  (\k x  ->  Nothing) i map

Функция: valid

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

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

valid :: Ord k  => Map  k  a ->  Bool

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

balanced  :: Map  k  a ->  Bool balanced  t =  case t of

Tip                           ->  True

Bin  sz  kx  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  kx  x  l r ->  (lo  kx)  && (hi  kx)  &&

bounded lo (<  kx)  l && bounded (>  kx)  hi r

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

realsize t =  case t of

Tip                         ->  Just  0

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

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

Все последующие функции имеют сложность O(log n), где n — размер отображения, поэтому этот факт указываться не будет. Это связано с тем, что все нижеследующие функции работают с ключами отображения.

Функция: findMin

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

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

findMin :: Map  k  a ->  (k, a)

findMin (Bin _ kx  x  Tip  r) =  (kx, x) findMin (Bin _ kx  x  l  r)   = findMin l

findMin Tip                               = error "Map.findMin: empty map  has no minimal  element"

Функция: findMax

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

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

findMax  :: Map  k  a ->  (k, a)

findMax  (Bin _ kx  x  l Tip) =  (kx, x) findMax  (Bin _ kx  x  l  r)   = findMax  r

findMax  Tip                               = error  "Map.findMax: empty map  has no maximal  element"

Функция: deleteMin

Описание: удаляет из отображения элемент по минимальному ключу.

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

deleteMin :: Map  k  a  ->  Map  k  a deleteMin  (Bin _ kx  x  Tip  r) =  r

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

Функция: deleteMax

Описание: удаляет из отображения элемент по максимальному ключу.

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

deleteMax  :: Map  k  a  ->  Map  k  a deleteMax  (Bin _ kx  x  l Tip) =  l

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

Функция: deleteFindMin

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

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

deleteFindMin :: Map  k  a ->  ((k,  a), Map  k  a) deleteFindMin t

=  case  t  of

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

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

Tip                         ->  (error "Map.deleteFindMin: can not  return the  minimal  element of an empty map",  Tip)

Функция: deleteFindMax

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

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

deleteFindMax  :: Map  k  a ->  ((k, a),  Map  k  a) deleteFindMax  t

=  case  t  of

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

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

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

the  maximal element  of an empty map",  Tip)

Функция: updateMin

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

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

updateMin  :: (a  ->  Maybe a)  ->  Map  k  a ->  Map  k  a updateMin  f m   = updateMinWithKey  (\k x  ->  f x) m

Функция: updateMax

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

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

updateMax :: (a  ->  Maybe a)  ->  Map  k  a ->  Map  k  a updateMax f m   = updateMaxWithKey  (\k x  ->  f x) m

Функция: updateMinWithKey

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

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

updateMinWithKey :: (k ->  a ->  Maybe a)  ->  Map  k  a ->  Map  k  a updateMinWithKey f t = case t of

Bin  sx  kx  x  Tip  r ->  case f  kx  x  of Nothing  ->  r

Just  x’ ->  Bin  sx  kx  x’ Tip  r

Bin  sx  kx  x  l r   ->  balance  kx  x  (updateMinWithKey  f l) r Tip                             ->  Tip

Функция: updateMaxWithKey

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

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

updateMaxWithKey :: (k ->  a ->  Maybe a)  ->  Map  k  a  ->  Map  k  a updateMaxWithKey f t = case t of

Bin  sx  kx  x  l Tip  ->  case  f  kx  x  of Nothing  ->  l

Just  x’ ->  Bin  sx  kx  x’ l  Tip

Bin  sx  kx  x  l r   ->  balance  kx  x  l  (updateMaxWithKey f r) Tip                             ->  Tip

Функция: minView

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

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

minView :: Monad  m   => Map  k  a ->  m   (Map  k  a, (k, a)) minView Tip  = fail  "Map.minView:  empty map"

minView x     = return (swap $  deleteFindMin x)

Функция: maxView

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

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

maxView  :: Monad  m   => Map  k  a ->  m   (Map  k  a, (k, a)) maxView  Tip  = fail  "Map.maxView: empty map"

maxView  x     = return (swap $  deleteFindMax  x)

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

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

По теме:

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