Home My Page Projects Code Snippets Project Openings SML/NJ
 Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

# SCM Repository

[smlnj] View of /sml/trunk/src/MLRISC/library/sorting.sml
 [smlnj] / sml / trunk / src / MLRISC / library / sorting.sml # View of /sml/trunk/src/MLRISC/library/sorting.sml

Revision 651 - (download) (annotate)
Thu Jun 1 18:34:03 2000 UTC (19 years, 2 months ago) by monnier
File size: 1840 byte(s)
```bring revisions from the vendor branch to the trunk
```
```(*
* Sorting
*
* -- Allen
*)

signature SORTING =
sig

val sort        : ('a * 'a -> bool) -> 'a list -> 'a list
val sort_uniq   : ('a * 'a -> bool) ->
('a * 'a -> bool) -> 'a list -> 'a list
val merge       : ('a * 'a -> bool) -> 'a list * 'a list -> 'a list
val merge_uniq  : ('a * 'a -> bool) ->
('a * 'a -> bool) -> 'a list * 'a list -> 'a list
val merge_uniqs : ('a * 'a -> bool) ->
('a * 'a -> bool) -> 'a list list -> 'a list
val uniq        : ('a * 'a -> bool) -> 'a list -> 'a list

end

structure Sorting : SORTING =
struct

infix ==

fun gensort merge op< l =
let fun sort [] = []
| sort (l as [x])   = l
| sort (l as [x,y]) = if x < y then l else [y,x]
| sort l =
let fun split([],a,b)    = (a,b)
| split(x::xs,a,b) = split(xs,b,x::a)
val (a,b) = split(l,[],[])
in  merge (sort a, sort b)
end
in  sort l
end

fun merge op< (a,b) =
let fun m ([],a) = a
| m (a,[]) = a
| m (a as (u::v), b as (w::x)) =
if u < w then u::m(v,b) else w::m(a,x)
in  m(a,b)
end

fun merge_uniq op< op== (a,b) =
let fun m ([],a) = uniq op== a
| m (a,[]) = uniq op== a
| m (a as (u::v), b as (w::x)) =
if u == w then m(a,x)
else if u < w then u::m(v,b)
else w::m(a,x)
in  m(a,b)
end

and uniq op== l =
let fun f []                 = []
| f (l as [x])         = l
| f (x::(l as (y::z))) = if x == y then f l else x::f l
in  f l
end

fun sort op< l = gensort (merge op<) op< l

fun sort_uniq op< op== l = gensort (merge_uniq op< op==) op< l

fun merge_uniqs op< op== l = sort_uniq op< op== (List.concat l)

end
```

 root@smlnj-gforge.cs.uchicago.edu ViewVC Help Powered by ViewVC 1.0.0
{"ft_lang_label":"__label__en","ft_lang_prob":0.50039405,"math_prob":0.979562,"size":1859,"snap":"2019-35-2019-39","text_gpt3_token_len":699,"char_repetition_ratio":0.17250673,"word_repetition_ratio":0.35784313,"special_character_ratio":0.457773,"punctuation_ratio":0.16703297,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9992293,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-08-22T20:05:58Z\",\"WARC-Record-ID\":\"<urn:uuid:ca819c0b-1f67-429a-9ae2-b2110d9477f2>\",\"Content-Length\":\"16629\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:98c40768-d853-41c4-ad67-9ad282169207>\",\"WARC-Concurrent-To\":\"<urn:uuid:88018555-d9ce-4fa4-b124-192737c01017>\",\"WARC-IP-Address\":\"128.135.164.83\",\"WARC-Target-URI\":\"http://smlnj-gforge.cs.uchicago.edu/scm/viewvc.php/sml/trunk/src/MLRISC/library/sorting.sml?view=markup&revision=651&root=smlnj&sortdir=down&pathrev=1530\",\"WARC-Payload-Digest\":\"sha1:J5YFAHINWKYNZ5FHTPH3YIMWRFRU6NJZ\",\"WARC-Block-Digest\":\"sha1:KDYD4AZZJEM7WJCQ3RCDKIY4L274BW24\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-35/CC-MAIN-2019-35_segments_1566027317359.75_warc_CC-MAIN-20190822194105-20190822220105-00305.warc.gz\"}"}