F#: Recursive functions: Split a list into two equal parts
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
// 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 | 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 [] []
let halve xs = xs |> List.splitAt (xs.Length / 2)
例子：
> 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])
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])
上一篇: 在F＃中递归，期望类型为int，但得到类型“int list”
下一篇: F＃：递归函数：将列表分成两个相等的部分