F # Split Function

Question

I am creating a merge sort function, and my split method gives me a value restriction error. I use 2 cumulative parameters, 2 lists as a result of the separation, which I pack in a tuple at the end for return. However, I get a value limit error, and I cannot figure out what the problem is. Does anyone have any ideas?

let split lst = let a = [] let b = [] let ctr = 0 let rec helper (lst,l1,l2,ctr) = match lst with | [] -> [] | x::xs -> if ctr%2 = 0 then helper(xs, x::l1, l2, ctr+1) else helper(xs, l1, x::l2, ctr+1) helper (lst, a, b, ctr) (a,b) 

Any input is appreciated.

Answer 1

The code, as you wrote it, does not really make sense. F # uses immutable defaults, so your function, as it is currently written, can be simplified:

 let split lst = let a = [] let b = [] (a,b) 

This is probably not what you want. In fact, due to immutable bindings, there is no value in predeclaring a, b and ctr .

Here is a recursive function that will do the trick:

 let split lst = let rec helper lst l1 l2 ctr = match lst with | [] -> l1, l2 // return accumulated lists | x::xs -> if ctr%2 = 0 then helper xs (x::l1) l2 (ctr+1) // prepend x to list 1 and increment else helper xs l1 (x::l2) (ctr+1) // prepend x to list 2 and increment helper lst [] [] 0 

Instead of using a recursive function, you can also solve this problem using List.fold , fold is a higher-order function that generalizes the accumulation process, which we described explicitly in the recursive function above.

This approach is a bit more concise, but most likely less familiar to someone new to functional programming, so I tried to describe this process in more detail.

 let split2 lst = /// Take a running total of each list and a index*value and return a new /// pair of lists with the supplied value prepended to the correct list let splitFolder (l1, l2) (i, x) = match i % 2 = 0 with |true -> x :: l1, l2 // return list 1 with x prepended and list2 |false -> l1, x :: l2 // return list 1 and list 2 with x prepended lst |> List.mapi (fun ix -> i, x) // map list of values to list of index*values |> List.fold (splitFolder) ([],[]) // fold over the list using the splitFolder function