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