814 |
814 |
815 (*Occurs check: type variable occurs in type?*) |
815 (*Occurs check: type variable occurs in type?*) |
816 fun occ v tye = |
816 fun occ v tye = |
817 let fun occ(Type(_, Ts)) = exists occ Ts |
817 let fun occ(Type(_, Ts)) = exists occ Ts |
818 | occ(TFree _) = false |
818 | occ(TFree _) = false |
819 | occ(TVar(w, _)) = v=w orelse |
819 | occ(TVar(w, _)) = eq_ix(v,w) orelse |
820 (case assoc(tye, w) of |
820 (case assoc(tye, w) of |
821 None => false |
821 None => false |
822 | Some U => occ U); |
822 | Some U => occ U); |
823 in occ end; |
823 in occ end; |
824 |
824 |
832 (* use add_to_tye(t,tye) instead of t::tye |
832 (* use add_to_tye(t,tye) instead of t::tye |
833 to avoid chains of the form 'a |-> 'b |-> 'c ... *) |
833 to avoid chains of the form 'a |-> 'b |-> 'c ... *) |
834 |
834 |
835 fun add_to_tye(p,[]) = [p] |
835 fun add_to_tye(p,[]) = [p] |
836 | add_to_tye(vT as (v,T),(xU as (x,TVar(w,S)))::ps) = |
836 | add_to_tye(vT as (v,T),(xU as (x,TVar(w,S)))::ps) = |
837 (if v=w then (x,T) else xU) :: (add_to_tye(vT,ps)) |
837 (if eq_ix(v,w) then (x,T) else xU) :: (add_to_tye(vT,ps)) |
838 | add_to_tye(v,x::xs) = x::(add_to_tye(v,xs)); |
838 | add_to_tye(v,x::xs) = x::(add_to_tye(v,xs)); |
839 |
839 |
840 (* 'dom' returns for a type constructor t the list of those domains |
840 (* 'dom' returns for a type constructor t the list of those domains |
841 which deliver a given range class C *) |
841 which deliver a given range class C *) |
842 |
842 |
873 (* Precondition: both types are well-formed w.r.t. type constructor arities *) |
873 (* Precondition: both types are well-formed w.r.t. type constructor arities *) |
874 fun unify1 (tsig as TySg{subclass, arities, ...}) = |
874 fun unify1 (tsig as TySg{subclass, arities, ...}) = |
875 let fun unif ((T, U), tye) = |
875 let fun unif ((T, U), tye) = |
876 case (devar(T, tye), devar(U, tye)) of |
876 case (devar(T, tye), devar(U, tye)) of |
877 (T as TVar(v, S1), U as TVar(w, S2)) => |
877 (T as TVar(v, S1), U as TVar(w, S2)) => |
878 if v=w then tye else |
878 if eq_ix(v,w) then tye else |
879 if sortorder subclass (S1, S2) then add_to_tye((w, T),tye) else |
879 if sortorder subclass (S1, S2) then add_to_tye((w, T),tye) else |
880 if sortorder subclass (S2, S1) then add_to_tye((v, U),tye) |
880 if sortorder subclass (S2, S1) then add_to_tye((v, U),tye) |
881 else let val nu = gen_tyvar (union_sort subclass (S1, S2)) |
881 else let val nu = gen_tyvar (union_sort subclass (S1, S2)) |
882 in add_to_tye((v, nu),add_to_tye((w, nu),tye)) end |
882 in add_to_tye((v, nu),add_to_tye((w, nu),tye)) end |
883 | (T as TVar(v, S), U) => |
883 | (T as TVar(v, S), U) => |