src/Pure/library.ML
changeset 2182 29e56f003599
parent 2175 21fde76bc742
child 2196 1b36ebc70487
equal deleted inserted replaced
2181:9c2b4728641d 2182:29e56f003599
   490 
   490 
   491 (*subset, optimized version for strings*)
   491 (*subset, optimized version for strings*)
   492 fun ([]:string list) subset_string ys = true
   492 fun ([]:string list) subset_string ys = true
   493   | (x :: xs) subset_string ys = x mem_string ys andalso xs subset_string ys;
   493   | (x :: xs) subset_string ys = x mem_string ys andalso xs subset_string ys;
   494 
   494 
   495 fun gen_subset eq (xs, ys) = forall (fn x => gen_mem eq (x, ys)) xs;
   495 (*set equality for strings*)
   496 
       
   497 
       
   498 (*eq_set*)
       
   499 
       
   500 fun eq_set (xs, ys) =
       
   501   xs = ys orelse (xs subset ys andalso ys subset xs);
       
   502 
       
   503 (*eq_set, optimized version for ints*)
       
   504 
       
   505 fun eq_set_int ((xs:int list), ys) =
       
   506   xs = ys orelse (xs subset_int ys andalso ys subset_int xs);
       
   507 
       
   508 (*eq_set, optimized version for strings*)
       
   509 
       
   510 fun eq_set_string ((xs:string list), ys) =
   496 fun eq_set_string ((xs:string list), ys) =
   511   xs = ys orelse (xs subset_string ys andalso ys subset_string xs);
   497   xs = ys orelse (xs subset_string ys andalso ys subset_string xs);
       
   498 
       
   499 fun gen_subset eq (xs, ys) = forall (fn x => gen_mem eq (x, ys)) xs;
   512 
   500 
   513 
   501 
   514 (*removing an element from a list WITHOUT duplicates*)
   502 (*removing an element from a list WITHOUT duplicates*)
   515 fun (y :: ys) \ x = if x = y then ys else y :: (ys \ x)
   503 fun (y :: ys) \ x = if x = y then ys else y :: (ys \ x)
   516   | [] \ x = [];
   504   | [] \ x = [];
   884 (* transitive closure (not Warshall's algorithm) *)
   872 (* transitive closure (not Warshall's algorithm) *)
   885 
   873 
   886 fun transitive_closure [] = []
   874 fun transitive_closure [] = []
   887   | transitive_closure ((x, ys)::ps) =
   875   | transitive_closure ((x, ys)::ps) =
   888       let val qs = transitive_closure ps
   876       let val qs = transitive_closure ps
   889           val zs = foldl (fn (zs, y) => assocs qs y union zs) (ys, ys)
   877           val zs = foldl (fn (zs, y) => assocs qs y union_string zs) (ys, ys)
   890           fun step(u, us) = (u, if x mem us then zs union us else us)
   878           fun step(u, us) = (u, if x mem_string us then zs union_string us 
       
   879 				else us)
   891       in (x, zs) :: map step qs end;
   880       in (x, zs) :: map step qs end;
   892 
   881 
   893 
   882 
   894 (** Recommended by Stephen K. Park and Keith W. Miller, 
   883 (** Recommended by Stephen K. Park and Keith W. Miller, 
   895       Random number generators: good ones are hard to find,
   884       Random number generators: good ones are hard to find,