CODEWITHSUNDEEP
arraysocaml
Tadej Vozlic
Tadej Vozlic

Reputation: 447

Recursive splitting array on smaller arrays in ocaml

I am trying to recursively divide array with n-length on 2 arrays, until I get n arrays of 1 element: 

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

That function returns only last element, but I want it to return something like [|3|];[|2|];[|4|];[|1|]

Upvotes: 0

Views: 576

Answers (1)

Andreas Rossberg
Andreas Rossberg

Reputation: 36108

If you really want to solve this by divide and conquer and create increasingly smaller arrays recursively then this would be a way to write it, ultimately returning the list of singleton arrays:

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))

But of course, creating all the intermediate arrays is both overcomplicated and inefficient. The following definition computes the same list but more succinctly and more efficiently:

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

Upvotes: 5

Related Questions