SML начало и образец

 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
datatype Pattern
= SEQUENCE of Term list
and Term
= SYM_LETTER of char
| SYM_WORD of string
| SYM_NUMBER of int
| STRUC of Pattern
| VAR of char * string
Составить следующие функции для обработки бинарных деревьев:
1. Функцию getStrings, возвращающую список строк в листьях дерева.
2. Функцию countLeaves, выполняющую подсчет количества листьев дерева.
3. Функцию replaceLeaves, выполняющую поиск и замену строки в дереве (должны быть скорректированы все листья, содержащие искомую строку).
4. Функцию toString, преобразующую дерево в строку (для вывода на экран).
Составить функцию высшего порядка processTree, выполняющую обход дерева, и реализовать через нее вышеперечисленные функции обработки бинарных деревьев.
datatype Tree
02 = NODE of Tree*Tree
03 | LEAF of string
04
05 fun getStrings (NODE (n1,n2)) = (getStrings n1) @ (getStrings n2)
06 | getStrings (LEAF s) = [s]
07
08 fun countLeaves (NODE (n1,n2)) = (countLeaves n1) + (countLeaves n2)
09 | countLeaves (LEAF s) = 1
10
11 fun replaceLeaves (str1,str2) (NODE (n1,n2)) =
12 NODE (replaceLeaves (str1,str2) n1,replaceLeaves (str1,str2) n1)
13 | replaceLeaves (str1,str2) (LEAF s) =
14 LEAF(if s = str1 then str2 else s)
15
16 fun toString (NODE (n1,n2)) = "(" ^ (toString n1) ^ "," ^ (toString n2) ^ ")"
17 | toString (LEAF s) = "\"" ^ s ^ "\""
18
19 fun processTree (f,g) (NODE (n1,n2)) = f (processTree (f,g) n1, processTree (f,g) n2)
20 | processTree (f,g) (LEAF s) = g s
21
22 val getStrings' = processTree (op @, fn s => [s])
23
24 val countLeaves' = processTree (op +, fn s => 1)
25
26 fun replaceLeaves' (str1,str2) =
27 processTree (fn (n1,n2) => NODE(n1,n2), fn s => LEAF(if s = str1 then str2 else s))
28
29 val toString' = processTree (fn(n1,n2) => "(" ^ n1 ^ "," ^ n2 ^ ")", fn s => "\"" ^ s ^ "\"")
30
31 (* Test *)
32 val testTree =
33 NODE(
34 NODE(
35 LEAF("Alpha"),
36 NODE(
37 LEAF("Beta"),
38 LEAF("Gamma")
39 )
40 ),
41 NODE(
42 LEAF("Delta"),
43 LEAF("Epsilon")
44 )
45 )
46
47 fun main () = print (toString' (replaceLeaves' ("Gamma","X") testTree))