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

0

В модуле IntMap содержится описание такой важной идиомы в программировании, как отображения. Реализация отображений достаточно эффективна и ос-

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

import  Data.IntMap  (IntMap)

import qualified  Data.IntMap  as  IntMap

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

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

Главный алгебраический тип данных, описанный в этом модуле, —  IntMap. Этот тип используется для представления отображений с целочисленными ключами.

Тип: IntMap

Описание: отображение с целочисленными ключами.

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

data  IntMap  a

= Nil

| Tip  !Key  a

| Bin  !Prefix !Mask !(IntMap a)  !(IntMap a)

Для удобства работы определён синоним Key, который равен типу Int.

Тип  IntMap  определён в  качестве   экземпляра для  следующих   классов:

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

Функция: (!)

Описание: осуществляет  поиск элемента в отображении. Вызывает  функцию

error, если элемент не найден.

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

(!) :: IntMap  a  ->  Key ->  a m   !  k  = find’ k  m

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

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

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

(\\) :: IntMap  a ->  IntMap  b  ->  IntMap  a m1  \\ m2  =  difference m1  m2

Функция: null

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

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

null ::  IntMap a ->  Bool null Nil      = True

null other = False

Функция: size

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

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

size ::  IntMap  a ->  Int size t =  case t of

Bin  p m   l r ->  size  l + size r Tip  k  x         ->  1

Nil            ->  0

Функция: member

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

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

member  :: Key ->  IntMap a ->  Bool member  k  m   = case  lookup  k  m   of

Nothing  ->  False Just  x    ->  True

Функция: nonMember

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

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

notMember :: Key ->  IntMap  a  ->  Bool notMember k  m   = not  $  member  k  m

Функция: lookup

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

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

lookup  :: (Monad m) => Key ->  IntMap  a  ->  m   a lookup  k  t = case lookup’ k  t  of

Just  x   ->  return  x

Nothing  ->  fail "Data.IntMap.lookup: Key not  found"

lookup’ :: Key ->  IntMap  a ->  Maybe a lookup’ k  t = let nk  =  natFromInt  k

in  seq nk (lookupN  nk t)

lookupN :: Nat  ->  IntMap  a ->  Maybe a lookupN k  t = case t  of

Bin  p m   l r | zeroN k  (natFromInt m) ->  lookupN k  l

| otherwise

->  lookupN  k  r

Tip  kx  x

| (k == natFromInt kx)

->  Just  x

| otherwise

->  Nothing

Nil

->  Nothing

Функция: findWithDefault

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

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

findWithDefault :: a ->  Key ->  IntMap  a ->  a findWithDefault def  k  m  = case lookup  k  m   of

Nothing  ->  def Just  x    ->  x

Функция: empty

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

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

empty  ::  IntMap  a empty  = Nil

Функция: singleton

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

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

singleton :: Key ->  a  ->  IntMap  a singleton  k  x  = Tip  k  x

Функция: insert

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

insert :: Key ->  a ->  IntMap  a  ->  IntMap  a insert k  x  t = case  t of

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

| zero  k  m

->  Bin  p m  (insert k  x  l)  r

| otherwise

->  Bin  p m   l  (insert k  x  r)

Tip  ky  y

| k  == ky

->  Tip  k  x

| otherwise

->  join k  (Tip  k  x) ky  t

Nil

->  Tip  k  x

Функция: insertWith

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

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

insertWith :: (a  ->  a ->  a)  ->  Key ->  a ->  IntMap  a  ->  IntMap  a insertWith f k  x  t = insertWithKey (\k  x  y  ->  f x  y) k  x  t

Функция: insertWithKey

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

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

insertWithKey :: (Key  ->  a ->  a ->  a)  ->  Key ->  a ->  IntMap  a ->  IntMap  a insertWithKey f k  x  t

=  case  t  of

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

| zero  k  m

->  Bin  p m   (insertWithKey f k  x  l) r

| otherwise

->  Bin  p m   l (insertWithKey f  k  x  r)

Tip  ky  y

| k  == ky

->  Tip  k  (f k  x  y)

| otherwise

->  join k  (Tip k  x) ky  t

Nil

->  Tip  k  x

Функция: insertLookupWithKey

Описание: возвращает пару вида ((Maybe a,  IntMap  a)), где первый элемент является результатом выполнения функции lookup, а второй — результатом функции insertLookupWithKey.

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

insertLookupWithKey :: (Key  ->  a ->  a ->  a)  ->  Key ->  a ->  IntMap  a ->  (Maybe a,  IntMap  a) insertLookupWithKey f k  x  t

=  case  t  of

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

| zero  k  m                  ->  let  (found, l’) = insertLookupWithKey  f k  x  l in   (found, Bin  p m   l’ r)

| otherwise        ->  let  (found, r’) = insertLookupWithKey  f k  x  r in   (found, Bin  p m   l r’)

Функция: delete

Описание: удаляет из отображения запись по ключу. Если заданного ключа нет в отображении, ничего не происходит.

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

delete :: Key ->  IntMap  a ->  IntMap  a delete k  t = case t  of

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

| zero  k  m

->  bin  p m   (delete  k  l) r

| otherwise

->  bin  p m   l (delete  k  r)

Tip  ky  y

| k  == ky

->  Nil

| otherwise

->  t

Nil

->  Nil

Функция: adjust

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

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

adjust ::  (a  ->  a)  ->  Key ->  IntMap  a  ->  IntMap  a adjust f k  m   =  adjustWithKey  (\k x  ->  f x) k  m

Функция: adjustWithKey

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

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

adjustWithKey ::  (Key  ->  a ->  a)  ->  Key ->  IntMap  a  ->  IntMap  a adjustWithKey f k  m   = updateWithKey  (\k  x  ->  Just  (f k  x)) k  m

Функция: update

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

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

update  ::  (a  ->  Maybe a)  ->  Key ->  IntMap  a  ->  IntMap  a update  f k  m   = updateWithKey  (\k  x  ->  f x) k  m

Функция: updateWithKey

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

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

updateWithKey  ::  (Key  ->  a ->  Maybe a)  ->  Key ->  IntMap  a  ->  IntMap  a updateWithKey  f k  t = case t of

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

| zero  k  m                  ->  bin  p m   (updateWithKey  f k  l) r

| otherwise        ->  bin  p m   l  (updateWithKey  f k  r) Tip  ky  y       | k  == ky             ->  case (f k  y) of

Just  y’  -> Tip  ky  y’ Nothing  -> Nil

|  otherwise          ->  t

Nil                                  ->  Nil

Функция: updateLookupWithKey

Описание: одновременно выполняет действия функций lookup и updateWithKey

для заданных значений. Результат возвращается в виде пары.

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

updateLookupWithKey ::  (Key  ->  a ->  Maybe a)  ->  Key ->  IntMap  a ->  (Maybe  a,IntMap   a) updateLookupWithKey f k  t

=  case  t  of

Bin  p m   l r | nomatch k  p m   ->  (Nothing, t)

| zero  k  m                  ->  let  (found, l’) =  updateLookupWithKey f k  l in    (found,  bin  p m   l’ r)

| otherwise        ->  let  (found, r’) =  updateLookupWithKey f k  r in    (found,  bin  p m   l r’)

Tip  ky  y       | k  == ky             ->  case (f k  y) of

Just  y’ ->  (Just y,  Tip  ky  y’) Nothing  ->  (Just y, Nil)

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

Функция: union

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

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

union  :: IntMap  a ->  IntMap  a ->  IntMap  a

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 k  x) t = insert k  x  t

union  t (Tip k  x) = insertWith (\x y  ->  y) k  x  t  – right bias  union  Nil t        = t

union  t Nil       = t

Функция: unionWith

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

unionWith   :: (a  ->  a ->  a)  ->  IntMap  a ->  IntMap  a  ->  IntMap  a unionWith   f m1  m2  = unionWithKey  (\k x  y  ->  f x  y) m1  m2

Функция:  unionWithKey

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

unionWithKey  :: (Key  ->  a ->  a ->  a)  ->  IntMap  a ->  IntMap  a  ->  IntMap  a unionWithKey  f 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  (unionWithKey   f l1 l2) (unionWithKey   f 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  (unionWithKey   f l1 t2) r1

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

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

| otherwise             = Bin  p2 m2  l2 (unionWithKey   f t1 r2)

unionWithKey  f (Tip k  x) t = insertWithKey f k  x  t

unionWithKey  f t (Tip k  x) = insertWithKey (\k  x  y  ->  f k  y  x) k  x  t  – right bias  unionWithKey  f Nil t        = t

unionWithKey  f t Nil       = t

Функция: unions

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

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

unions  :: [IntMap a] ->  IntMap  a

unions  xs  = foldlStrict union  empty xs

Функция: unionsWith

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

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

unionsWith  :: (a->a->a) ->  [IntMap a] ->  IntMap  a unionsWith  f ts = foldlStrict  (unionWith f) empty ts

Функция: difference

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

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

difference :: IntMap  a ->  IntMap  b ->  IntMap  a 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  k  x) t2

| member  k  t2   = Nil

| otherwise      = t1

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

Функция: differenceWith

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

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

differenceWith :: (a  ->  b ->  Maybe a)  ->  IntMap  a ->  IntMap  b  ->  IntMap  a differenceWith f m1  m2  = differenceWithKey (\k  x  y  ->  f x  y) m1  m2

Функция: differenceWithKey

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

differenceWithKey :: (Key  ->  a ->  b ->  Maybe a)  ->  IntMap  a ->  IntMap  b  ->  IntMap  a differenceWithKey f 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  (differenceWithKey f l1 l2)  (differenceWithKey  f r1  r2)

|  otherwise          =  t1 where

difference1 | nomatch p2 p1 m1    = t1

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

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

| zero  p1 m2                    = differenceWithKey f t1 l2

| otherwise               = differenceWithKey f t1 r2

differenceWithKey f t1@(Tip  k  x) t2 = case lookup  k  t2 of

Just  y   ->  case f k  x  y  of

Just  y’  ->  Tip  k  y’ Nothing  ->  Nil

Nothing  ->  t1

differenceWithKey f Nil t             = Nil

differenceWithKey f t (Tip k  y) = updateWithKey  (\k x  ->  f  k  x  y) k  t differenceWithKey f t Nil       = t

Функция: intersection

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

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

intersection :: IntMap  a ->  IntMap  b ->  IntMap  a 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  k  x) t2

| member  k  t2   = t1

| otherwise      = Nil

intersection t (Tip k  x) = case lookup  k  t of Just  y   ->  Tip  k  y Nothing  ->  Nil

intersection Nil  t = Nil intersection t  Nil = Nil

Функция: intersectionWith

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

intersectionWith :: (a  ->  b ->  a)  ->  IntMap  a ->  IntMap  b ->  IntMap  a intersectionWith f m1  m2  = intersectionWithKey (\k  x  y  ->  f x  y) m1  m2

Функция: intersectionWithKey

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

intersectionWithKey :: (Key  ->  a ->  b ->  a)  ->  IntMap  a ->  IntMap  b ->  IntMap  a intersectionWithKey f 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  (intersectionWithKey f l1  l2)  (intersectionWithKey f  r1  r2)

| otherwise        = Nil

where

intersection1 | nomatch p2 p1 m1    = Nil

| zero  p2 m1                    =  intersectionWithKey f l1 t2

| otherwise               =  intersectionWithKey f r1  t2 intersection2 | nomatch  p1 p2 m2    = Nil

| zero  p1 m2                    =  intersectionWithKey f t1 l2

| otherwise               =  intersectionWithKey f t1 r2 intersectionWithKey f  t1@(Tip  k  x) t2 = case lookup  k  t2 of

Just  y   ->  Tip  k  (f k  x  y) Nothing  ->  Nil

intersectionWithKey f t1 (Tip k  y) = case lookup  k  t1 of

Just  x   ->  Tip  k  (f k  x  y) Nothing  ->  Nil

intersectionWithKey f  Nil t = Nil intersectionWithKey f  t Nil = Nil

Функция: map

Описание: применяет заданную функцию ко всем значениям  в отображении.

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

map  :: (a  ->  b)  ->  IntMap  a  ->  IntMap  b map  f m   =  mapWithKey  (\k x  ->  f x) m

Функция: mapWithKey

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

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

mapWithKey  :: (Key  ->  a ->  b)  ->  IntMap  a  ->  IntMap  b mapWithKey  f t = case t of

Bin  p m   l r ->  Bin  p m   (mapWithKey f l)  (mapWithKey f r) Tip  k  x         ->  Tip  k  (f k  x)

Nil            ->  Nil

Функция: mapAccum

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

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

mapAccum  :: (a  ->  b ->  (a,c)) ->  a ->  IntMap  b ->  (a,IntMap c) mapAccum  f a m   = mapAccumWithKey  (\a k  x  -> f a x) a m

Функция: mapAccumWithKey

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

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

mapAccumWithKey  :: (a  ->  Key ->  b ->  (a, c)) ->  a ->  IntMap  b ->  (a,  IntMap  c) mapAccumWithKey  f a t = mapAccumL  f a t

mapAccumL  :: (a  ->  Key ->  b ->  (a, c)) ->  a ->  IntMap  b ->  (a,  IntMap  c) mapAccumL  f a t = case t of

Bin  p m   l r ->  let (a1, l’) =  mapAccumL  f a l (a2,  r’) =  mapAccumL  f a1 r

in   (a2, Bin  p  m  l’ r’) Tip  k  x         ->  let  (a’, x’) = f a k  x

in  (a’,  Tip  k  x’) Nil            ->  (a, Nil)

mapAccumR  :: (a  ->  Key ->  b ->  (a, c)) ->  a ->  IntMap  b ->  (a,  IntMap  c) mapAccumR  f a t = case t of

Bin  p m   l r ->  let (a1, r’)  =  mapAccumR  f a r (a2,  l’) =  mapAccumR  f a1 l

in   (a2, Bin  p  m  l’ r’) Tip  k  x         ->  let  (a’, x’) = f a k  x

in  (a’,  Tip  k  x’) Nil            ->  (a, Nil)

Функция: fold

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

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

fold :: (a  ->  b ->  b)  ->  b ->  IntMap  a  ->  b fold f z  t = foldWithKey (\k  x  y  ->  f x  y) z  t

Функция: foldWithKey

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

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

foldWithKey :: (Key  ->  a ->  b ->  b)  ->  b ->  IntMap  a ->  b foldWithKey f z  t = foldr f z  t

foldr :: (Key  ->  a ->  b ->  b)  ->  b ->  IntMap  a ->  b foldr f z  t = case t of

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

Tip  k  x                         ->  f k  x  z Nil                                ->  z

Функция: elems

Описание: возвращает список всех значений, хранящихся в заданном отображении.

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

elems :: IntMap  a ->  [a]

elems m   = foldWithKey (\k  x  xs  ->  x:xs) [] m

Функция:  keys

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

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

keys  :: IntMap  a ->  [Key]

keys  m   = foldWithKey (\k  x  ks  ->  k:ks) [] m

Функция: keysSet

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

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

keysSet  :: IntMap  a ->  IntSet.IntSet

keysSet  m   = IntSet.fromDistinctAscList (keys  m)

Функция: assocs

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

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

assocs  :: IntMap  a ->  [(Key,a)] assocs  m   =  toList m

Функция: toList

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

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

toList :: IntMap  a ->  [(Key,a)]

toList t = foldWithKey (\k  x  xs  ->  (k,  x):xs) [] t

Функция: fromList

Описание: создаёт отображение на основе ассоциированного списка, содержащего значения вида (ключ, значение).

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

fromList :: [(Key,a)] ->  IntMap  a fromList xs  =  foldlStrict ins   empty xs

where

ins   t (k, x) = insert k  x  t

Функция: fromListWith

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

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

fromListWith :: (a  ->  a ->  a)  ->  [(Key,a)]  ->  IntMap  a fromListWith f xs  = fromListWithKey (\k  x  y  ->  f x  y) xs

Функция: fromListWithKey

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

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

fromListWithKey :: (Key  ->  a ->  a ->  a)  ->  [(Key,a)]  ->  IntMap  a fromListWithKey f xs  = foldlStrict ins   empty xs

where

ins   t (k, x) = insertWithKey f k  x  t

Функция: toAscList

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

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

toAscList :: IntMap  a ->  [(Key,a)]

toAscList t = let (pos, neg)  = span (\(k, x) ->  k  >=0)  (foldr (\k x  xs  ->  (k,  x):xs) [] t) in neg ++ pos

Функция: fromAscList

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

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

fromAscList :: [(Key,a)]  ->  IntMap  a fromAscList  xs  = fromList  xs

Функция: fromAscListWith

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

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

fromAscListWith :: (a  ->  a ->  a)  ->  [(Key,a)]  ->  IntMap  a fromAscListWith f xs  =  fromListWith  f xs

Функция: fromAscListWithKey

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

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

fromAscListWithKey :: (Key  ->  a ->  a ->  a)  ->  [(Key,a)]  ->  IntMap  a fromAscListWithKey f xs  = fromListWithKey f  xs

Функция: fromDistinctAscList

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

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

fromDistinctAscList :: [(Key,a)]  ->  IntMap  a fromDistinctAscList  xs  = fromList  xs

Функция: filter

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

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

filter :: (a  ->  Bool)   ->  IntMap  a ->  IntMap  a filter p m   = filterWithKey  (\k x  ->  p x) m

Функция: filterWithKey

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

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

filterWithKey :: (Key  ->  a ->  Bool)   ->  IntMap  a ->  IntMap  a filterWithKey pred  t = case t of

Bin  p m   l r          ->  bin  p m   (filterWithKey  pred  l) (filterWithKey  pred  r)

Tip  k  x  | pred  k  x   ->  t

|  otherwise  ->  Nil Nil                                ->  Nil

Функция: partition

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

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

partition :: (a  ->  Bool)   ->  IntMap  a ->  (IntMap  a,IntMap   a) partition p m   = partitionWithKey (\k  x  ->  p x) m

Функция: partitionWithKey

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

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

partitionWithKey :: (Key  ->  a ->  Bool)   ->  IntMap  a ->  (IntMap  a,IntMap   a) partitionWithKey pred  t = case t of

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

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

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

Функция: mapMaybe

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

mapMaybe  :: (a  ->  Maybe b)  ->  IntMap  a  ->  IntMap  b mapMaybe  f m   =  mapMaybeWithKey  (\k x  ->  f x) m

Функция: mapMaybeWithKey

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

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

mapMaybeWithKey  :: (Key  ->  a ->  Maybe b)  ->  IntMap  a ->  IntMap  b

mapMaybeWithKey  f (Bin p m   l r) = bin  p m   (mapMaybeWithKey  f l)  (mapMaybeWithKey  f r) mapMaybeWithKey  f (Tip k  x)       = case f k  x  of

Just  y    ->  Tip  k  y Nothing  ->  Nil

mapMaybeWithKey  f Nil            = Nil

Функция: mapEither

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

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

mapEither  :: (a  ->  Either b c) ->  IntMap  a ->  (IntMap  b, IntMap  c) mapEither  f m   = mapEitherWithKey  (\k x  ->  f  x) m

Функция: mapEitherWithKey

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

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

mapEitherWithKey  :: (Key  ->  a ->  Either b c) ->  IntMap  a ->  (IntMap   b,  IntMap  c) mapEitherWithKey  f (Bin p m   l r) = (bin p m   l1 r1, bin  p m   l2  r2)

where

(l1, l2) =  mapEitherWithKey  f l (r1, r2) =  mapEitherWithKey  f r

mapEitherWithKey  f (Tip k  x)       = case  f  k  x  of

Left y   ->  (Tip  k  y, Nil) Right   z  ->  (Nil, Tip  k  z)

mapEitherWithKey  f Nil            =  (Nil, Nil)

Функция: split

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

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

split :: Key ->  IntMap  a ->  (IntMap  a,IntMap   a) split k  t = case t of

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

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

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

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

| k  < ky             ->  (Nil, t)

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

split’ :: Key ->  IntMap  a ->  (IntMap  a,IntMap   a) split’ k  t = case t of

Bin  p m   l r | nomatch k  p m   ->  if k  > p

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

| zero  k  m                  ->  let (lt, gt) =  split k  l in    (lt, union  gt r)

| otherwise        ->  let (lt, gt) =  split k  r in    (union l lt, gt)

Tip  ky  y  | k  > ky                     ->  (t, Nil)

| k  < ky                     ->  (Nil, t)

| otherwise             ->  (Nil, Nil)

Nil                                  ->  (Nil, Nil)

Функция: splitLookup

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

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

splitLookup :: Key ->  IntMap  a ->  (IntMap   a,Maybe  a,IntMap   a) splitLookup k  t

=  case  t  of

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

then  let (lt, found, gt) =  splitLookup’ k  l in (union  r lt, found, gt)

else  let (lt, found, gt) =  splitLookup’ k  r in (lt,  found, union  gt l))

| otherwise ->  splitLookup’ k  t Tip  ky  y  | k  > ky             ->  (t,  Nothing, Nil)

| k  < ky             ->  (Nil, Nothing, t)

| otherwise      ->  (Nil,  Just  y, Nil) Nil                                        ->  (Nil, Nothing, Nil)

splitLookup’ :: Key ->  IntMap  a ->  (IntMap   a,Maybe  a,IntMap   a) splitLookup’ k  t

=  case  t  of

Bin  p m   l r | nomatch k  p m   ->  if k  > p

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

| zero  k  m                  ->  let (lt, found, gt) =  splitLookup k  l in  (lt,  found, union  gt r)

| otherwise        ->  let (lt, found, gt) =  splitLookup k  r in  (union  l lt, found, gt)

Tip  ky  y  | k  > ky                       ->  (t, Nothing, Nil)

| k  < ky                       ->  (Nil, Nothing, t)

| otherwise               ->  (Nil,  Just  y, Nil) Nil                                                 ->  (Nil, Nothing, Nil)

Функция: isSubmapOf

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

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

isSubmapOf :: Eq a => IntMap  a ->  IntMap a ->  Bool isSubmapOf m1  m2  =  isSubmapOfBy (==)  m1  m2

Функция: isSubmapOfBy

Описание: вариант функции  isSubmapOf, в котором  сравнение  производится при помощи заданного первым аргументом предиката.

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

isSubmapOfBy :: (a  ->  b ->  Bool)   ->  IntMap  a ->  IntMap  b  ->  Bool isSubmapOfBy pred  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  isSubmapOfBy  pred  t1 l2 else  isSubmapOfBy pred  t1  r2)

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

isSubmapOfBy pred  (Tip k  x) t = case lookup  k  t of Just  y    ->  pred  x  y Nothing  ->  False

isSubmapOfBy pred  Nil t = True

Функция: isProperSubmapOf

Описание: возвращает значение True, если первое отображение входит во второе, и при этом отображения не равны.

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

isProperSubmapOf :: Eq a => IntMap  a ->  IntMap  a  ->  Bool isProperSubmapOf m1  m2  =  isProperSubmapOfBy (==)  m1  m2

Функция: isProperSubmapOfBy

Описание: вариант функции isProperSubmapOf, в котором  сравнение  производится при помощи заданного первым аргументом предиката.

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

isProperSubmapOfBy :: (a  ->  b ->  Bool)   ->  IntMap  a ->  IntMap  b  ->  Bool isProperSubmapOfBy pred  t1 t2 = case submapCmp  pred  t1  t2 of

LT  ->  True ge  ->  False

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

| shorter m1  m2  = GT

| shorter m2  m1  = submapCmpLt

| p1 == p2           = submapCmpEq

| otherwise        = GT

where

submapCmpLt  | nomatch p1 p2 m2  = GT

| zero  p1 m2                 = submapCmp  pred  t1 l2

| otherwise             = submapCmp  pred  t1 r2

submapCmpEq  = case (submapCmp  pred  l1 l2, submapCmp  pred  r1  r2) of (GT,  _ ) ->  GT

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

submapCmp  pred  (Bin p m  l  r) t = GT submapCmp  pred  (Tip kx  x) (Tip ky  y)

| (kx  == ky)  &&  pred x  y  = EQ

| otherwise                           =  GT

submapCmp  pred  (Tip k  x) t = case lookup  k  t of

Just  y  |  pred  x  y  ->  LT other                         ->  GT

submapCmp  pred  Nil Nil = EQ submapCmp  pred  Nil t   = LT

Функция: showTree

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

Функция используется для отладочных целей.

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

showTree :: Show  a => IntMap  a ->  String showTree s  =  showTreeWith True  False  s

Функция: showTreeWith

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

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

showTreeWith :: Show  a => Bool  ->  Bool  ->  IntMap  a ->  String showTreeWith hang wide  t | hang           =  (showsTreeHang wide  [] t) ""

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

showsTree :: Show  a => Bool  ->  [String] ->  [String] ->  IntMap  a  ->  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  k  x         ->  showsBars lbars . showString  " "  .  shows k  .

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

showsTreeHang  :: Show  a => Bool  ->  [String] ->  IntMap  a  ->  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  k  x         ->  showsBars bars  . showString  " " . shows k  .

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

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

По теме:

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