OCaml:Quicksort-尾递归,无限循环?

朱莉安娜(Juliana Souza)

当我编译代码可以,但是当我调用并执行函数Quicksort时,该程序似乎处于无限循环中。我能做什么 ?我测试了所有功能,但问题似乎出在tQuicksort函数中。我是初学者。

let h l =
    match l with
        | [] -> raise (Failure "head")
        | x::xs -> x;;

let t l =
    match l with
        | [] -> raise (Failure "tail")
        | x::xs -> xs;;

let rec trev l r = 
    match l with
        | [] -> r
        | x::xs -> trev xs (x::r);;
let rev l = trev l [];;

let rec tunir l1 l2 r =
    match l1 with
        | [] -> if l2 == [] then
                rev r
            else
                tunir [] (t l2) ((h l2)::r)
        | x1::xs1 -> tunir xs1 l2 (x1::r);;


let unir l1 l2 = tunir l1 l2 [];;

let rec tpart x l l1 l2 = 
    match l with
        | [] -> if l1 == [] then
                ((x::[]), l2)
            else
                (l1, (x::l2))
        | (lx:: lxs) -> if (h l) <= x then
                    tpart x (t l) ((h l)::l1) l2
                else
                    tpart x (t l) l1 ((h l)::l2);;

let part x l = tpart x l [] [];;

let rec tnroelem l n =
    match l with
        | [] -> n
        | x::xs -> tnroelem (t l) (n+1);;

let nroelem l = tnroelem l 0;;

let rec tunirL l r = 
    match l with
        | [] -> rev r
        | lx::lxs -> if lx == [] then tunirL lxs r
                    else tunirL((t lx)::lxs) ((h lx)::r);;

let unirL l = tunirL l [];;

let rec tquicksort lm l lM = 
    match l with
        | [] -> unirL (unir (rev lm) lM)
        | lx::lxs -> let (la, lb) = part (h l) (t l) in
                    if (nroelem la < nroelem lb) then tquicksort ((quicksort la)::lm) lb lM
                    else tquicksort lm la ((quicksort lb)::lM)
and quicksort l = tquicksort [] l [];;

let rec geraListaT n l = 
    if n == 0 then l
    else geraListaT (n-1) (n::l);;
let geraLista n = geraListaT n [];;

let lista : int list = geraLista 9;;

List.iter (fun x->print_int x) (quicksort lista)
加莱

您在尝试时缺少一个案例,quicksort lm l lM并且l只有一个元素。在这种情况下,采取的分支是

    | lx::lxs -> let (la, lb) = part (h l) (t l) in
                    if (nroelem la < nroelem lb)
                    then tquicksort ((quicksort la)::lm) lb lM
                    else tquicksort lm la ((quicksort lb)::lM)

然后,无论结果if什么,您都将执行递归调用quicksort lm' l' lM',其中l'也只有一个元素。可以通过在空列表的后面添加一个额外的大小写来解决此问题:

    | lx::[]  -> unirL (unir (rev (l :: lm)) lM)

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章