F＃：递归函数：将列表分成两个相等的部分
我在split和mergesort时遇到了一些错误。 （注意，这是一个格式化的分配，需要每个功能的特定输入和输出类型）
这是我现在的代码：
(* 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)
acc函数不能用于分割，最后一行代码中的“then”不正确。
这个想法如下：给定的列表l被分成两个相等的（如果l的长度是奇数，那么其中一个“一半”比另一个长一些）列表l1和l2。 这些列表是递归排序的，然后将结果合并回来以给出单个排序列表。 在F＃中编码。 您的算法可以使用<作为比较运算符。 你的代码必须有一个产生一对列表的函数分割，合并排序列表的函数合并和实现整个算法的函数mergesort。
编辑：我相信我不能使用|> List.splitAt在这个任务上。 我正在尝试实现一个辅助函数，它可以做同样的事情。
编辑2：谢谢Guy Coder，你的回答非常彻底。 我需要功能拆分只需要一个列表。 也许我可以在里面创建一个帮助函数，使用基于list.Length/2索引？ 假定列表输入是一个float list ，并且该函数返回2个float lists 。
编辑3：我感觉更接近：这是我的分裂功能和我收到的错误。
(* 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])
来自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 [] []
这个如何工作。
比赛有三种模式
| [] 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
此人说，我们并不需要知道列表的长度，因为如果我们在列表中至少有两个项目| x::y::tail | x::y::tail然后把一个放在列表一和列表二中。 重复此操作直到列表中有一个或没有项目。 如果列表中有一个项目放入第一个列表并重复。 现在输入列表是空的，所以返回两个列表。
来自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
Joel Huang使用延续传球风格
这是一个将函数传递给内部函数的函数。 函数是(fun x -> x)和内部函数在cont参数中接收它。 这个也有三种匹配模式。
| [] 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.
但是，由于它为每个递归调用传递一个函数，因此在列表完成递归函数传递之前，不会评估构建函数的评估。 它也使用一个计数器，但倒计数到0以避免必须传递额外的参数。 这是高级编码，所以不要花很多时间去理解它，但要知道，因为函数是一流的，所以这是可能的。
TheInnerLight的第四个版本 - 前些日发布。
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
我如何创建分割。
从格式开始
let funXYZ list =
let rec funXYZInner list acc =
match list with
| head :: tail ->
let acc = (somefunc head) :: acc
funXYZInner tail acc
| [] -> acc
funXYZInner list []
命名功能拆分
let split list =
let rec splitInner l acc =
match l with
| head :: tail ->
let acc = (somefunc head) :: acc
splitInner tail acc
| [] -> acc
split list []
现在我知道我需要一个输入列表和两个输出列表以及一个元组中的两个输出列表
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 [] []
因为分割会将列表分成两半，这可以在遍历列表之前计算
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 [] []
为了把它变成一个条件，我们需要一个计数器。 所以在splitInner l listMid 0 [] []中将计数器初始化为0并将其传递给匹配模式。 由于对于最后的匹配模式，我们不关心计数值是多少，所以使用_代替。
我们还需要知道如何对计数器，这是比较listMid这样通过传递给splitInner 。
同时增加每次使用头部的计数器。
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 [] []
现在添加条件
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 [] []
将head重命名为x并将tail重新命名为xs作为个人偏好
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 [] []
并在返回结果之前反转列表。
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])
您的Edit3中存在两个问题：
第一个由编译器标记的是当你调用splitInner (l 0 [] []) 。 你不需要在这里使用任何括号。
这编译并显示不正确的结果：
(* 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])
错误是因为if c < (l.Length/2) then你在每次比较不同的列表。
让我们看看每次递归调用会发生什么：
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
您需要的是与原始列表中计算的“固定”值进行比较。
(* 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#: Recursive functions: Split a list into two equal parts