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

0

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

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

import qualified  Data.Sequence as Seq

Реализация  конечных  последовательностей основана на  специального  вида деревьях, как описано в работе [8].

Тип: Seq

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

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

newtype Seq a = Seq (FingerTree (Elem  a))

data  FingerTree a

= Empty

|  Single  a

| Deep !Int !(Digit a)  (FingerTree (Node a)) !(Digit  a)

Для   этого  типа  данных  определены экземпляры  следующих   классов: Foldable,  Functor, Monad, MonadPlus,  Traversable, Typeable1, Data, Eq, Monoid, Ord, Read и Show.

Функция: empty

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

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

empty ::  Seq a empty =  Seq Empty

Функция: singleton

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

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

singleton :: a ->  Seq a

singleton x  = Seq (Single (Elem  x))

Функция: (<|)

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

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

infixr 5 <|

(<|)  :: a ->  Seq a ->  Seq a

x  <| Seq xs  = Seq (Elem  x  ‘consTree‘ xs)

consTree  :: Sized  a => a ->  FingerTree a ->  FingerTree a consTree  a Empty                                              =  Single a

consTree  a (Single b)                                    = deep (One a)  Empty (One b)

consTree  a (Deep s  (Four  b c  d e)  m   sf) = m   ‘seq‘ Deep (size a + s) (Two a b)

(node3  c  d e  ‘consTree‘ m) sf consTree  a (Deep s  (Three  b c  d)  m   sf)  = Deep (size a +  s) (Four  a b c  d)  m   sf consTree  a (Deep s  (Two b c) m   sf)        = Deep  (size a + s) (Three  a b c) m   sf consTree  a (Deep s  (One b)  m   sf)          =  Deep (size a + s) (Two a b)  m   sf

Функция: (|>)

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

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

infixr 5 |>

(|>)  :: Seq a ->  a ->  Seq a

Seq xs  |> x  = Seq (xs  ‘snocTree‘ Elem x)

snocTree  :: Sized  a => FingerTree a ->  a ->  FingerTree a snocTree  Empty a                                              =  Single a

snocTree  (Single a)  b                                    = deep (One a)  Empty (One b) snocTree  (Deep s  pr  m   (Four  a b c  d)) e = m  ‘seq‘ Deep (s + size e)  pr

(m ‘snocTree‘  node3 a b c) (Two d e)

snocTree  (Deep s  pr  m   (Three  a b c)) d   = Deep (s + size d)  pr  m  (Four  a b c  d) snocTree  (Deep s  pr  m   (Two a b)) c           = Deep (s +  size c) pr  m   (Three  a b c) snocTree  (Deep s  pr  m   (One a)) b               =  Deep (s + size b)  pr  m   (Two a b)

Функция: (><)

Описание: конкатенирует две последовательности.

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

infixr 5 ><

(><)  :: Seq a ->  Seq a ->  Seq a

Seq xs  >< Seq ys  = Seq (appendTree0  xs  ys)

appendTree0 :: FingerTree (Elem  a)  ->  FingerTree (Elem  a)  ->  FingerTree  (Elem  a) appendTree0 Empty xs                                                                = xs

appendTree0 xs  Empty                                                                = xs

appendTree0 (Single x) xs                                                       = x  ‘consTree‘ xs appendTree0 xs  (Single x)                                                       =  xs  ‘snocTree‘ x appendTree0 (Deep s1 pr1  m1  sf1) (Deep s2 pr2  m2  sf2) = Deep (s1  + s2)  pr1

(addDigits0 m1  sf1  pr2  m2) sf2

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

Функция: fromList

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

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

fromList :: [a] ->  Seq a

fromList = Data.List.foldl’ (|>)  empty

Функция: null

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

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

null :: Seq a ->  Bool null (Seq  Empty) = True null _                     =  False

Функция: length

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

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

length :: Seq a  ->  Int length  (Seq  xs)  = size  xs

Тип: ViewL

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

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

data  ViewL a = EmptyL | a  :< Seq a deriving (Eq,  Ord,  Show, Read)

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

Functor,  Traversable, Typeable1, Data, Eq, Ord, Read и Show.

Тип: ViewR

Описание: вид на последовательность с самого правого элемента.

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

data  ViewR a = EmptyR  |  Seq a :>  a deriving  (Eq,  Ord,  Show,  Read)

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

Functor,  Traversable, Typeable1, Data, Eq, Ord, Read и Show.

Функция: viewl

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

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

viewl :: Seq a ->  ViewL a

viewl (Seq xs)  = case viewLTree  xs  of

Nothing2                     ->  EmptyL

Just2  (Elem  x) xs’ ->  x  :<  Seq xs’

Функция: viewr

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

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

viewr   :: Seq a ->  ViewR a

viewr   (Seq xs)  = case viewRTree xs  of

Nothing2                     ->  EmptyR

Just2  xs’ (Elem  x) ->  Seq xs’ :>  x

Функция: index

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

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

index  :: Seq a ->  Int ->  a

index  (Seq xs)  i | 0 <= i &&  i < size xs  = case  lookupTree  i xs  of Place  _  (Elem  x)  -> x

| otherwise                      = error  "index out  of  bounds"

Функция: adjust

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

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

adjust :: (a  ->  a)  ->  Int ->  Seq a ->  Seq a

adjust f i (Seq xs)  | 0 <= i &&  i < size xs  = Seq (adjustTree (const (fmap  f)) i  xs)

| otherwise                      = Seq xs

Функция: update

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

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

update  :: Int ->  a ->  Seq a  ->  Seq a update  i x  = adjust  (const x) i

Функция: take

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

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

take  :: Int ->  Seq a  ->  Seq a take  i = fst  . splitAt i

Функция: drop

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

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

drop  :: Int ->  Seq a  ->  Seq a drop  i = snd  . splitAt i

Функция: splitAt

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

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

splitAt :: Int ->  Seq a ->  (Seq  a,  Seq a) splitAt i (Seq xs)  =  (Seq l, Seq r)

where

(l, r) = split i xs

split :: Int ->  FingerTree (Elem  a)  ->  (FingerTree (Elem  a),  FingerTree (Elem  a)) split i Empty                      = i ‘seq‘ (Empty,  Empty)

split i xs  | size xs  > i = (l, consTree  x  r)

| otherwise     = (xs, Empty)

where

Split l x  r = splitTree i xs

Функция: reverse

Описание: обращает заданную последовательность.

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

reverse :: Seq a ->  Seq a

reverse (Seq xs)  = Seq (reverseTree id xs)

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

Остаётся отметить, что  за этот модуль в поставке  языка  Haskell отвечает Р.  Патерсон, с которым  можно  связаться по  адресу электронной почты ross@soi.city.ac.uk.

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

По теме:

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