递归分裂阵列

Question

我想递归地划分与正长数组2个阵列，直到我得到1元的n个数组：

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 []