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

0

содержит описание произвольных деревьев  (розовых кустов) для произвольных нужд.  В  модуле предлагается  наиболее  общий интерфейс для работы с деревьями. Использование:

import  Data.Tree

Главный тип данных в этом модуле: Tree.

Тип: Tree

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

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

data  Tree  a

=  Node

{

rootLabel :: a

subForest   :: (Forest a)

}

type  Forest a = [Tree   a]

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

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

Функция: drawTree

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

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

drawTree :: Tree  String  ->  String drawTree =  unlines . draw

Функция: drawForest

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

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

drawForest  :: Forest String  ->  String drawForest  =  unlines  . map  drawTree

draw :: Tree  String ->  [String]

draw (Node x  ts0) = x  : drawSubTrees ts0

where

drawSubTrees []     = []

drawSubTrees [t]    = "|"  : shift "‘" "   " (draw  t)

drawSubTrees (t:ts) = "|"  : shift "+  " "|    " (draw  t) ++  drawSubTrees ts shift first other    = zipWith (++)  (first :  repeat   other)

Функция: flatten

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

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

flatten ::  Tree  a ->  [a] flatten t  = squish  t  []

where

squish  (Node x  ts) xs  = x:Prelude.foldr squish  xs  ts

Функция: levels

Описание: возвращает список списков меток вершин на каждом уровне заданного дерева.

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

levels :: Tree  a ->  [[a]]

levels t = map  (map  rootLabel) $ takeWhile  (not . null)  $

iterate (concatMap  subForest) [t]

Функция: unfoldTree

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

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

unfoldTree :: (b  ->  (a, [b]))  ->  b ->  Tree  a unfoldTree f b = let  (a, bs)  = f b

in  Node a  (unfoldForest f bs)

Функция: unfoldForest

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

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

unfoldForest :: (b  ->  (a, [b])) ->  [b] ->  Forest a unfoldForest f = map  (unfoldTree  f)

Функция: unfoldTreeM

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

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

unfoldTreeM  :: Monad  m   => (b  ->  m   (a, [b])) ->  b ->  m  (Tree  a) unfoldTreeM  f b = do (a, bs)  < f b

ts < unfoldForestM f  bs return (Node  a  ts)

Функция: unfoldForestM

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

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

unfoldForestM :: Monad  m   => (b  ->  m   (a, [b])) ->  [b] ->  m  (Forest a) unfoldForestM f = Prelude.mapM (unfoldTreeM f)

Функция: unfoldTreeM-BF

Описание: вариант функции unfoldTreeM, который строит дерево по принципу

«сначала в ширину» (работа функции основана на материалах статьи [18]).

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

unfoldTreeM_BF :: Monad  m   => (b  ->  m   (a, [b])) ->  b ->  m  (Tree  a) unfoldTreeM_BF f b = liftM getElement  $  unfoldForestQ  f (singleton b)

where

getElement  xs  = case  viewl  xs  of x  :<  _  ->  x

EmptyL ->  error  "unfoldTreeM_BF"

Функция: unfoldForestM-BF

Описание: вариант функции unfoldForestM, который  строит лес по  принципу

«сначала в ширину» (работа функции основана на материалах статьи [18]).

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

unfoldForestM_BF  :: Monad  m   => (b  ->  m   (a, [b])) ->  [b] ->  m  (Forest a) unfoldForestM_BF  f = liftM toList . unfoldForestQ  f . fromList

unfoldForestQ :: Monad  m   => (b  ->  m   (a, [b])) ->  Seq b ->  m  (Seq (Tree  a)) unfoldForestQ f aQ  = case viewl aQ  of

EmptyL ->  return empty

a :<  aQ  ->  do (b, as)  < f a

tQ < unfoldForestQ f (Prelude.foldl  (|>)  aQ  as) let (tQ’, ts) = splitOnto  [] as tQ

return (Node b ts <| tQ’)

where

splitOnto :: [a’] ->  [b’] ->  Seq a’ ->  (Seq a’, [a’]) splitOnto as [] q = (q,  as)

splitOnto as (_:bs) q = case viewr   q of

q’ :>  a ->  splitOnto  (a:as) bs q’ EmptyR    ->  error  "unfoldForestQ"

8.29.     Модуль Tuple

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

import Data.Tuple

Соответственно, в рассматриваемый модуль вынесены определения функций:

fst (см. стр. 136), snd (см. стр. 163), curry (см. стр. 129) и uncurry  (см. стр. 166).

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

По теме:

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