ocaml中较小数组的递归分割数组

Question

我试图将长度为 n 的数组递归地划分为 2 个数组，直到得到 n 个包含 1 个元素的数组：

let rec split array = 
    if Array.length array = 1 then
        array
    else if Array.length array mod 2 = 0 then
        let a = Array.make (Array.length array /2) 0 in
        for i = 0 to Array.length a-1 do 
            a.(i) <- array.(i) done;
        let b = Array.make (Array.length array/2) 0 in 
        for i = Array.length a to Array.length array -1 do
            b.(i-Array.length a) <- array.(i) done;
        split a;
        split b;
    else
        let a = Array.make(Array.length array/2 +1) 0 in
        for i = 0 to Array.length a-1 do
            a.(i) <- array.(i) done;
        let b = Array.make (Array.length array/2) 0 in 
        for i = Array.length a to Array.length array -1 do
            b.(i-Array.length a) <- array.(i) done;
            split a;
            split b;


split [|3;2;4;1|];; 

该函数仅返回最后一个元素，但我希望它返回类似的内容[|3|];[|2|];[|4|];[|1|]

Answer 1

如果你真的想通过分而治之的方法来解决这个问题，并递归地创建越来越小的数组，那么这将是一种编写方法，最终返回单例数组的列表：

let rec split = function
  | [||] -> []
  | [|x|] as a -> [a]
  | a ->
    let i = Array.length a / 2 in
    split (Array.sub a 0 i) @ split (Array.sub a i (Array.length a - i))

但当然，创建所有中间数组既过于复杂又低效。以下定义计算相同的列表，但更简洁、更高效：

let split a = Array.fold_right (fun x l -> [|x|]::l) a []