小编Joã*_*ira的帖子

我想知道如何编写一个有效版本的快速排序 ,其中列表在一次传递中被分区.

我有这段代码,

    let rec quicksort' = function
[] -> []
| x::xs -> let small = List.filter (fun y -> y < x ) xs
           and large = List.filter (fun y -> y > x ) xs

in quicksort' small @ (x :: quicksort' large);;

但是在这里我要经历超过1次的清单(对于小型和大型呼叫2次快速排序).

我们的想法是只需一步即可完成,而无需多次访问列表.

我想知道如何在Ocaml中构建一个函数,用于List.fold_left查明列表中是否存在元素.例:

exists 3 [1;2;3;4;5] 
=> true

这个函数的类型是: a -> bool -> 'a list -> bool

我的想法如何做到如下:

let exists k l = List.fold_left( fun a x-> a=x) k l

但显然是错的.有什么建议怎么办？

我想编写一个函数load: 'a option list -> 'a tree,它从给定列表中恢复二进制树,其中包含后缀顺序的元素.如果列表不代表任何树,则您的函数应该引发异常Load(您必须先声明它).

树被定义为:

type ‘a btree = L of ‘a | N of ‘a btree * ‘a btree

到目前为止,我所做的是:

exception Load ;;

let rec load l =
    match l with
        | [] -> raise Load
        | Some x::_ -> L x
        | None::t -> N(?,load t)
;; 

以下是输入列表的示例:

[Some 2; Some 0; None; Some 5; Some 9; Some 20; None; None; None]

如何做到这一点真是太棘手了.由于列表是后缀顺序,我想知道是否更好地使用List.foldright函数??