files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.icl

   1 implementation module StdRoseTree
   2
   3 /**     This module defines rose trees.
   4 */
   5 import StdEnv
   6
   7 root                                                    :: !(RoseTree a) -> a
   8 root (Node r _)                                 = r
   9
  10 children                                                :: !(RoseTree a) -> [RoseTree a]
  11 children (Node _ ts)                    = ts
  12
  13 depth                                                   :: !(RoseTree a) -> Int
  14 depth (Node _ [])                               = 1
  15 depth (Node _ xs)                               = 1 + maxList (map depth xs)
  16
  17 prunetree                                               :: !PruneDepth !(RoseTree a) -> RoseTree a
  18 prunetree d (Node x ts)
  19 | d <= 1                                                = Node x []
  20 | otherwise                                             = Node x (map (prunetree (d-1)) ts)
  21
  22 bonsai                                                  :: !(RoseTree a) -> RoseTree a | Eq a
  23 bonsai t                                                = bonsai` [] t
  24 where
  25         bonsai`                                         :: ![a] !(RoseTree a) -> RoseTree a | Eq a
  26         bonsai` path (Node v ts)        = Node v (filter (\t -> not (isMember (root t) [v:path]))
  27                                                                                  (map (bonsai` [v:path]) ts)
  28                                                                          )
  29
  30 iteratetree                                             :: !(Children a) a -> RoseTree a
  31 iteratetree f s                                 = Node s (map (iteratetree f) (f s))
  32
  33 maptree                                                 :: (a -> b) !(RoseTree a) -> RoseTree b
  34 maptree f (Node x ts)                   = Node (f x) (map (maptree f) ts)
  35
  36 paths                                                   :: !(RoseTree a) -> [[a]]
  37 paths (Node x [])                               = [[x]]
  38 paths (Node x ts)                               = [[x:path] \\ t <- ts, path <- paths t]