Algebraic data types: Difference between revisions

cuts away prolog version
(cuts away prolog version)
Line 82:
(** val balance :: color * 'a tree * 'a * 'a tree -> 'a tree *)
let balance = function
| B, T (R, T (R,a,x,b), y, c), z, d | B, T (R, a, x, T (R,b,y,c)), z, d
| B, a, x, T (R, T (R,b,y,c), z, d) | B, a, x, T (R, b, y, T (R,c,z,d)) -> T (R, T (B,a,x,b)z, y, T (B,c,z,d))
| B, a, x, T (R, T (R,b,y,c), z, d)
| 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))
| col, a, x, b -> T (col, a, x, b)
 
Line 106 ⟶ 108:
color(b).
 
tree(_,e).
tree(P,t(C,L,_X,R)) :- color(C), tree(P,L), call(P,X), tree(P,R).
 
balancebal(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))):-!.
balancebal(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))):-!.
balancebal(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))):-!.
balancebal(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(C, A, X, B, t(C,A,X,B)).
 
insbalance(C,A,X,eB,tS) :- ( bal(rC,eA,X,e)B,T) :-> !S = T ; S = t(C,A,X,B) ).
 
ins(X,t(C,A,Y,B),R) :- X < Y, !, ins(X,A,Ao), balance(C,Ao,Y,B,R).
ins(X,e,t(Cr,Ae,Y,B),R) :- X > Y, !, ins(X,B,Boe), balance(C,A,Y,Bo,R).
ins(X,t(C,A,Y,B),R) :- ( X < Y, !,-> ins(X,A,Ao), balance(C,Ao,Y,B,R).
ins(_,S,S).
; X > Y -> ins(X,B,Bo), balance(C,A,Y,Bo,R)
; X = Y -> R = t(C,A,Y,B)
).
 
insert(X,S,t(b,A,Y,B)) :- ins(X,S,t(_,A,Y,B)).
Anonymous user