Algebraic data types: Difference between revisions
Content added Content deleted
(added standard ml) |
|||
| Line 73: | Line 73: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
< |
<lang ocaml> |
||
type color = R | B |
type color = R | B |
||
type 'a tree = E | T of color * 'a tree * 'a * 'a tree |
type 'a tree = E | T of color * 'a tree * 'a * 'a tree |
||
(** val balance |
(** val balance : color * 'a tree * 'a * 'a tree -> 'a tree *) |
||
let balance = function |
let balance = function |
||
| B, T (R, T (R,a,x,b), y, c), z, d |
| B, T (R, T (R,a,x,b), y, c), z, d |
||
| Line 85: | Line 85: | ||
| col, a, x, b -> T (col, a, x, b) |
| col, a, x, b -> T (col, a, x, b) |
||
(** val insert |
(** val insert : 'a -> 'a tree -> 'a tree *) |
||
let insert x s = |
let insert x s = |
||
let rec ins = function |
let rec ins = function |
||
| Line 91: | Line 91: | ||
| T (col,a,y,b) as s -> |
| T (col,a,y,b) as s -> |
||
if x < y then |
if x < y then |
||
balance (col, |
balance (col, ins a, y, b) |
||
else if x > y then |
else if x > y then |
||
balance (col, a, y, |
balance (col, a, y, ins b) |
||
else |
else |
||
s |
s |
||
in let T (_,a,y,b) = ins s |
in let T (_,a,y,b) = ins s |
||
in T (B,a,y,b) |
in T (B,a,y,b) |
||
</ |
</lang> |
||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
| Line 123: | Line 123: | ||
insert(X,S,t(b,A,Y,B)) :- ins(X,S,t(_,A,Y,B)). |
insert(X,S,t(b,A,Y,B)) :- ins(X,S,t(_,A,Y,B)). |
||
</pre> |
</pre> |
||
=={{header|Standard ML}}== |
|||
<lang sml> |
|||
datatype color = R | B |
|||
datatype 'a tree = E | T of color * 'a tree * 'a * 'a tree |
|||
(** val balance = fn : color * 'a tree * 'a * 'a tree -> 'a tree *) |
|||
fun balance (B, T (R, T (R,a,x,b), y, c), z, d) = T (R, T (B,a,x,b), y, T (B,c,z,d)) |
|||
| balance (B, T (R, a, x, T (R,b,y,c)), z, d) = T (R, T (B,a,x,b), y, T (B,c,z,d)) |
|||
| balance (B, a, x, T (R, T (R,b,y,c), z, d)) = T (R, T (B,a,x,b), y, T (B,c,z,d)) |
|||
| balance (B, a, x, T (R, b, y, T (R,c,z,d))) = T (R, T (B,a,x,b), y, T (B,c,z,d)) |
|||
| balance (col, a, x, b) = T (col, a, x, b) |
|||
(** val insert = fn : int -> int tree -> int tree *) |
|||
fun insert x s = let |
|||
fun ins E = T (R,E,x,E) |
|||
| ins (s as T (col,a,y,b)) = |
|||
if x < y then |
|||
balance (col, ins a, y, b) |
|||
else if x > y then |
|||
balance (col, a, y, ins b) |
|||
else |
|||
s |
|||
val T (_,a,y,b) = ins s |
|||
in |
|||
T (B,a,y,b) |
|||
end |
|||
</lang> |
|||