F#: Recursive functions: Split a list into two equal parts

Question

I'm having some errors with split and mergesort. (Note this is a formatted assignment requiring specific input & output types for each function)

Here is my code right now:

(* val split : l:'a list -> 'a list * 'a list *)
let split (l:'a list -> 'a list * 'a list) = 
    let rec splitInner = function
        | [],[] -> [],[]
        | x::xs, acc ->
            if xs.Length>(acc.Length) then splitInner (xs x::acc)
            else xs acc
    splitInner (l, acc)

error FS0001: This expression was expected to have type
    'a list * 'b list    
but here has type
    'c list

(* val merge : 'a list * 'a list -> 'a list when 'a : comparison *)
let rec merge l = 
    match l with
    | (xs,[])->xs
    | ([],ys)->ys
    | (x::xs, y::yr) ->
        if x<=y then x::merge(xr,y::yr)
        else y::merge(x::xr,yr)

(* val mergesort : l:'a list -> 'a list when 'a : comparison *)
let rec mergesort l = 
    match l with
    | [] -> []
    | [x] -> [x]
    | xs -> let (ys,zs) = split xs then merge(mergesort ys, mergesort zs)

The acc function is not working with split and the "then" in the last line of code is not right.

The idea is as follows: the given list l is split into two equal (if the length of l is odd then one of the “halves” is one item longer than the other) lists l1 and l2. These lists are sorted recursively and then the results are merged back to give a single sorted list. Code this in F#. Your algorithm can use < as a comparison operator. Your code must have a function split that produces a pair of lists, a function merge that merges sorted lists and a function mergesort that implements the overall algorithm.

EDIT: I believe I am not allowed to use |> List.splitAt on this assignment. I am trying to implement a helper function which will do the same thing.

EDIT2: Thank you Guy Coder, your answers are very thorough. I need the function split to take in only a list. Perhaps I may create a helper function inside that uses index based upon list.Length/2? It is assumed that the list input is a float list, and the function returns 2 float lists.

EDIT3: I feel much closer: here is my split function and the error I receive.

(* val split : l:'a list -> 'a list * 'a list *)
let split l = 
    let rec splitInner l counter list1 list2 =
        match (l, counter) with
        | (x::xs,c) ->
            if c < (l.Length/2) then
                let list1 = x :: list1
                let counter = counter+1
                splitInner xs counter list1 list2
            else
                let list2 = x :: list2
                let counter = counter+1
                splitInner xs counter list1 list2
        | ([],_) -> ((reverse list1), (reverse list2))
    splitInner (l 0 [] [])
split [1;2;3;4;5;6;7;8;9;10]

error FS0001: This expression was expected to have type
    int -> 'a list -> 'b list -> 'c list    
but here has type
    'd list

Answer 1

let halve xs = xs |> List.splitAt (xs.Length / 2)

Examples:

> halve [1..10];;
val it : int list * int list = ([1; 2; 3; 4; 5], [6; 7; 8; 9; 10])
> halve [1..9];;
val it : int list * int list = ([1; 2; 3; 4], [5; 6; 7; 8; 9])

Answer 2

// val reverse : l:'a list -> 'a list
let reverse l =
    let rec reverseInner l acc =
        match l with
        | x::xs -> 
            let acc = x :: acc
            reverseInner xs acc
        | [] -> acc
    reverseInner l []

// val split : l:'a list -> 'a list * 'a list
let split l = 
    let listMid = (int)((length l)/2)
    let rec splitInner l index counter list1 list2 =
        match (l,counter) with 
        | (x::xs,c) ->  
            if c < index then
                let list1 = x :: list1
                let counter = counter + 1
                splitInner xs index counter list1 list2
            else
                let list2 = x :: list2
                let counter = counter + 1
                splitInner xs index counter list1 list2
        | ([], _) -> ((reverse list1), (reverse list2))
    splitInner l listMid 0 [] []

split [1;2;3;4;5;6;7;8;9;10]
val it : int list * int list = ([1; 2; 3; 4; 5], [6; 7; 8; 9; 10])

split [1;2;3;4;5;6;7;8;9;10;11]
val it : int list * int list = ([1; 2; 3; 4; 5], [6; 7; 8; 9; 10; 11])

Another variation from RosettaCode

let split list =
    let rec aux l acc1 acc2 =
        match l with
            | [] -> (acc1,acc2)
            | [x] -> (x::acc1,acc2)
            | x::y::tail ->
                aux tail (x::acc1) (y::acc2)
    in aux list [] []

How this one works.

The match has three patterns

| []           which only matches when the input list is empty
| [x]          which only matches when there is only one item in the list
| x::y::tail   which matches all the other patterns 

This one says we don't need to know the length of the list because if we have at least two items in the list | x::y::tail then put one in list one and the other in list two. This is repeated until there is one or no items in the list. If there is one item in the list put it into the first list and repeat. Now the input list is empty so return the two list.

A third variation from fssnip.net

let splitList divSize lst = 
  let rec splitAcc divSize cont = function
    | [] -> cont([],[])
    | l when divSize = 0 -> cont([], l)
    | h::t -> splitAcc (divSize-1) (fun acc -> cont(h::fst acc, snd acc)) t
  splitAcc divSize (fun x -> x) lst

by Joel Huang which uses Continuation-passing style

This one passes a function to the inner function. The function being (fun x -> x) and the inner function receiving it in the cont parameter. This one also has three match patterns.

| []   only matches on empty list  
| l    only matches on list with one item  
| h::t matches when there are two or more items in the list.  

However since it is passing a function for each recursive call, the evaluation of the function that is built up is not evaluated until the list is done being passed through the recursive functions. It also uses a counter, but counts down to 0 to avoid having to pass an extra parameter. This is advanced coding so don't spend a lot of time trying to understand it, but be aware that because functions are first-class this is possible.

A fourth variation from TheInnerLight - posted just the other day.

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

How I created split.

Starting with the format

let funXYZ list =
    let rec funXYZInner list acc =
        match list with
        | head :: tail ->
            let acc = (somefunc head) :: acc
            funXYZInner tail acc
        | [] -> acc
    funXYZInner list []

name the function split

let split list =
    let rec splitInner l acc =
        match l with
        | head :: tail ->
            let acc = (somefunc head) :: acc
            splitInner tail acc
        | [] -> acc
    split list []

Now I know I need one input list and two output list with the two output list in a tuple

let split l =
    let rec splitInner l list1 list2 =
        match l with
        | head :: tail ->
            let list1 = (somefunc head)
            let list2 = (somefunc head)
            splitInner tail list1 list2
        | [] -> (list1, list2)
    split l [] []

since the split will divide the list in half, that can be calculated before iterating through the list

let split l =
    let listMid = (int)((length l)/2)
    let rec splitInner l list1 list2 =
        match l with
        | head :: tail ->
            let list1 = (somefunc head)
            let list2 = (somefunc head)
            splitInner tail list1 list2
        | [] -> (list1, list2)
    split l [] []

To turn this into a conditional we need a counter. So initialize the counter to 0 in splitInner l listMid 0 [] [] and pass it through to the match patterns. Since for the last match pattern we do not care what the value of the count is, _ is used instead.
We also need to know what to compare the counter against, which is listMid so pass that through to splitInner.
Also increment the counter for each use of head.

let split l =
    let listMid = (int)((length l)/2)
    let rec splitInner l listMid counter list1 list2 =
        match (l ,counter) with
        | (head :: tail, c) ->
            let list1 = (somefunc head)
            let list2 = (somefunc head)
            let counter = counter + 1
            splitInner tail listMid counter list1 list2
        | ([],_) -> (list1, list2)
    splitInner l listMid 0 [] []

and now add the conditional

let split l =        
    let listMid = (int)((length l)/2)
    let rec splitInner l listMid counter list1 list2 =
        match (l,counter) with
        | (head :: tail, c) ->
            if c < listMid then
                let list1 = head :: list1
                let counter = counter + 1
                splitInner tail listMid counter list1 list2
            else
                let list2 = head :: list2
                let counter = counter + 1
                splitInner tail listMid counter list1 list2
        | ([],_)-> (list1, list2)
    splitInner l listMid 0 [] []

rename head to x and tail to xs as a personal preference

let split l =
    let listMid = (int)((length l)/2)
    let rec splitInner l listMid counter list1 list2 =
        match (l,counter) with
        | (x::xs, c) ->
            if c < listMid then
                let list1 = x :: list1
                let counter = counter + 1
                splitInner xs listMid counter list1 list2
            else
                let list2 = x :: list2
                let counter = counter + 1
                splitInner xs listMid counter list1 list2
        | ([],_)-> (list1, list2)
    splitInner l listMid 0 [] []

and reverse the list before returning them as the result.

let split l =
    let listMid = (int)((length l)/2)
    let rec splitInner l listMid counter list1 list2 =
        match (l, counter) with
        | (x :: xs, c) ->
            if c < listMid then
                let list1 = x :: list1
                let counter = counter + 1
                splitInner xs listMid counter list1 list2
            else
                let list2 = x :: list2
                let counter = counter + 1
                splitInner xs listMid counter list1 list2
        | ([],_)-> (reverse list1, reverse list2)
    splitInner l listMid 0 [] []

Answer 3

You stil have two problems in your Edit3:

The first one, marked by the compiler, is when you call splitInner (l 0 [] []). You don´t need to use any parenthesis here.

This compiles and shows an incorrect result:

(* val split : l:'a list -> 'a list * 'a list *)
let split l = 
    let rec splitInner l counter list1 list2 =
        match (l, counter) with
        | (x::xs, c) ->
            if c < (l.Length/2) then
                let list1 = x :: list1
                let counter = counter+1
                splitInner xs counter list1 list2
            else
                let list2 = x :: list2
                let counter = counter+1
                splitInner xs counter list1 list2
        | ([],_) -> ((reverse list1), (reverse list2))
    splitInner l 0 [] []

split [1;2;3;4;5;6;7;8;9;10]

> split [1;2;3;4;5;6;7;8;9;10];;
val it : int list * int list = ([1; 2; 3], [4; 5; 6; 7; 8; 9; 10])

The error is because in the line if c < (l.Length/2) then you are comparing against a different list each time.

Lets see what happens on each recursive call:

First call to `splitInner`
Parameters
    l = [1;2;3;4;5;6;7;8;9;10]
    counter = 0
    list1 = []
    list2 = []

Values     
    l.Length / 2 = 5
    x = 1
    xs = [2;3;4;5;6;7;8;9;10]
    c = 0
    c < l.Length/2 = True


Second call to `splitInner`
Parameters
    l = [2;3;4;5;6;7;8;9;10]
    counter = 1
    list1 = [1]
    list2 = []

Values     
    l.Length / 2 = 4
    x = 2
    xs = [3;4;5;6;7;8;9;10]
    c = 1
    c < l.Length/2 = True


Third call to `splitInner`
Parameters
    l = [3;4;5;6;7;8;9;10]
    counter = 2
    list1 = [2;1]
    list2 = []

Values     
    l.Length / 2 = 4
    x = 3
    xs = [4;5;6;7;8;9;10]
    c = 2
    c < l.Length/2 = True


Third call to `splitInner`
Parameters
    l = [4;5;6;7;8;9;10]
    counter = 3
    list1 = [3; 2;1]
    list2 = []

Values     
    l.Length / 2 = 3
    x = 4
    xs = [5;6;7;8;9;10]
    c = 3
    c < l.Length/2 = False

What you need is to compare against a "fixed" value calculated on your original list.

(* val split : l:'a list -> 'a list * 'a list *)
let split (l: 'a list) =
    let middle = l.Length / 2

    let rec splitInner l counter list1 list2 =
        match (l, counter) with
        | (x::xs, c) ->
            if c < middle then
                let list1 = x :: list1
                let counter = counter+1
                splitInner xs counter list1 list2
            else
                let list2 = x :: list2
                let counter = counter+1
                splitInner xs counter list1 list2
        | ([],_) -> ((reverse list1), (reverse list2))

    splitInner l 0 [] []

split [1;2;3;4;5;6;7;8;9;10]
val it : int list * int list = ([1; 2; 3; 4; 5], [6; 7; 8; 9; 10])

Answer 4

Guy Coder proposed quite a number of way to split a list into two parts, here is another one I have been taught when studying mergeSort (and, I believe, one of the easiest) :

let split lst = 
   let rec helper lst l1 l2 =
      match lst with
      | [] -> l1, l2 // return accumulated lists
      | x::xs -> helper xs l2 (x::l1) // prepend x to list 1 and swap lists
helper lst [] []