22 struct |
22 struct |
23 |
23 |
24 |
24 |
25 (* single elements *) |
25 (* single elements *) |
26 |
26 |
27 exception ABSENT of int; |
|
28 |
|
29 fun find_index ord list x = |
27 fun find_index ord list x = |
30 let |
28 let |
31 fun find i [] = raise ABSENT i |
29 fun find i [] = ~ i |
32 | find i (y :: ys) = |
30 | find i (y :: ys) = |
33 (case ord (x, y) of |
31 (case ord (x, y) of |
34 LESS => raise ABSENT i |
32 LESS => ~ i |
35 | EQUAL => i |
33 | EQUAL => i |
36 | GREATER => find (i + 1) ys); |
34 | GREATER => find (i + 1) ys); |
37 in find 0 list end; |
35 in find 1 list end; |
38 |
36 |
39 fun member ord list x = |
37 fun member ord list x = find_index ord list x > 0; |
40 (find_index ord list x; true) handle ABSENT _ => false; |
|
41 |
38 |
42 fun insert ord x list = |
39 fun insert ord x list = |
43 let |
40 let |
44 fun insrt 0 ys = x :: ys |
41 fun insrt 1 ys = x :: ys |
45 | insrt i (y :: ys) = y :: insrt (i - 1) ys; |
42 | insrt i (y :: ys) = y :: insrt (i - 1) ys; |
46 in (find_index ord list x; list) handle ABSENT i => insrt i list end; |
43 val idx = find_index ord list x; |
|
44 in if idx > 0 then list else insrt (~ idx) list end; |
47 |
45 |
48 fun remove ord x list = |
46 fun remove ord x list = |
49 let |
47 let |
50 fun rmove 0 (_ :: ys) = ys |
48 fun rmove 1 (_ :: ys) = ys |
51 | rmove i (y :: ys) = y :: rmove (i - 1) ys; |
49 | rmove i (y :: ys) = y :: rmove (i - 1) ys; |
52 in rmove (find_index ord list x) list handle ABSENT _ => list end; |
50 val idx = find_index ord list x; |
|
51 in if idx > 0 then rmove idx list else list end; |
53 |
52 |
54 |
53 |
55 (* lists as sets *) |
54 (* lists as sets *) |
56 |
55 |
57 nonfix subset; |
56 nonfix subset; |