List-To-Tree/substructure.hs at master · raw-ash/List-To-Tree · GitHub

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
{-+====================================================================================+--
--+-------------------------Tree and Associated Functions------------------------------+--
--+====================================================================================+--}

data Tree a = Nil | Leaf a | Node (Tree a) (Tree a)
 deriving Show


{-+------------------+--
--+--Helper Funtion--+--
--+------------------+-}
toTree [] _ _ str
    | str == "" = Nil
    | otherwise = Node (Leaf str) Nil
toTree ('[':xs) currentLevel treeLevel str
    | currentLevel==treeLevel = Node gs hs
    | otherwise = toTree xs currentLevel treeLevel str
        where gs = toTree xs (currentLevel+1)  (treeLevel+1) str
              hs = toTree xs (currentLevel)  (treeLevel+1) str
toTree (',':xs) currentLevel treeLevel str
    | currentLevel==treeLevel = if (str=="") then hs else (Node gs hs)
    | otherwise = toTree xs currentLevel treeLevel ""
        where gs = Leaf str
              hs = toTree xs currentLevel treeLevel ""
toTree (']':xs) currentLevel treeLevel str
    | currentLevel == treeLevel = Node gs hs
    | otherwise = toTree xs (currentLevel) (treeLevel-1) ""
        where gs = Leaf str
              hs = Nil
toTree (x:xs) currentLevel treeLevel str = toTree xs currentLevel treeLevel (str++[x])


{-+----------------------------------+--
--+-Check if two trees are identical-+--
--+----------------------------------+-}
areIdentical Nil Nil = True
areIdentical Nil _ = False
areIdentical _ Nil = False
areIdentical (Node xs ys) (Node xs' ys')= (areIdentical xs xs') && (areIdentical ys ys')
areIdentical (Node xs ys) _ = False
areIdentical _ (Node xs' ys') = False
areIdentical (Leaf a) (Leaf b)
 | a==b = True
 | otherwise = False


{-+------------------+--
--+-Get left subtree-+--
--+------------------+-}
left (Node t s) = t
left (Leaf a) = Nil
left Nil = Nil

{-+-------------------+--
--+-Get right subtree-+--
--+-------------------+-}
right (Node t s) = s
right (Leaf a) = Nil
right Nil = Nil


{-+------------------+--
--+-Check if subtree-+--
--+------------------+-}
isSubtree Nil Nil = True
isSubtree Nil _ = False
isSubtree t s = if gs then gs else ((isSubtree (left t) s) || (isSubtree (right t) s))
    where gs = areIdentical t s


{-+-----------------------------------------+--
--+-Check if subtree and retrieve functions-+--
--+-to obtain this subtree form main tree---+--
--+-----------------------------------------+-}
isSubtreeFn Nil Nil f = (True,f)
isSubtreeFn Nil _ _ = (False,["id"])
isSubtreeFn t s f
    | gs == True = (gs,f)
    | ((fst as)==True && (fst bs)==True) = (True,(snd as)++(snd bs))
    | (fst as) == True = as
    | (fst bs) == True = bs
    | otherwise = (False,["id"])
    where gs = areIdentical t s
          as = isSubtreeFn (left t) s (map ("head."++) f)
          bs = isSubtreeFn (right t) s (map ("tail."++) f)


{-+====================================================================================+--
--+----------------------------------List Functions------------------------------------+--
--+====================================================================================+-}


{-+------------------+--
--+-Any data to tree-+--
--+------------------+-}
elemToTree a = Leaf p
 where p = show a


{-+------------------+--
--+-Any list to tree-+--
--+------------------+-}
listToTree l = toTree (p (show l)) 0 0 ""
 where p = init.tail                        ----to remove first and last square braces


{-+------------------+--
--+-Check if subtree-+--
--+------------------+-}
isSublist xs ys = isSubtree (listToTree xs) (listToTree ys)


{-+----------------------+--
--+-Check if subtree and-+--
--+--Get function list---+--
--+----------------------+-}
isSublistFn xs ys = isSubtreeFn (listToTree xs) (listToTree ys) ["id"]