F#:递归函数:将列表分为两个相等的部分 [英] F#: Recursive functions: Split a list into two equal parts
问题描述
我在split和mergesort时遇到一些错误. (请注意，这是格式化的分配，每个功能都需要特定的输入和输出类型)
I'm having some errors with split and mergesort. (Note this is a formatted assignment requiring specific input & output types for each function)
这是我的代码:
(* 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函数无法与split一起使用，并且最后一行代码中的"then"不正确.
The acc function is not working with split and the "then" in the last line of code is not right.
想法如下:将给定的列表l分为两个相等的列表(如果l的长度为奇数，则一半"之一比另一个长)一个列表l1和l2.这些列表以递归方式排序，然后将结果合并回以给出单个排序的列表.用F#编写代码.您的算法可以使用<作为比较运算符.您的代码必须具有产生一对列表的函数拆分，合并已排序列表的函数合并以及实现整体算法的函数mergesort.
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.
我相信我不允许在此作业上使用|> List.splitAt.我正在尝试实现一个辅助功能，该功能将执行相同的操作.
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.
谢谢Guy Coder，您的回答非常详尽.我需要将功能拆分为仅包含一个列表.也许我可以在内部创建一个使用基于list.Length/2的索引的辅助函数?假定列表输入为float list，并且该函数返回2 float lists.
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.
我感觉更近了:这是我的分割函数和收到的错误.
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])
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 [] []
这是如何工作的.
比赛有3种模式
| [] 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，则将其中一个放在列表一中，将另一个放在列表二中.重复此过程，直到列表中没有一个或没有任何项目为止.如果列表中有一项，则将其放入第一个列表并重复.现在输入列表为空，因此返回两个列表.
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.
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参数中接收它.这也有三种匹配模式.
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.
但是，由于它要为每个递归调用传递一个函数，因此，在列表通过递归函数传递完成之前，不会评估所构建函数的评估.它还使用一个计数器，但递减至0，以避免必须传递额外的参数.这是高级编码，因此不必花费大量时间来理解它，但是请注意，因为函数是一流的，所以这是可能的.
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.
TheInnerLight 的第四种变化-我如何创建拆分.
以格式开头
let funXYZ list =
let rec funXYZInner list acc =
match list with
| head :: tail ->
let acc = (somefunc head) :: acc
funXYZInner tail acc
| [] -> acc
funXYZInner list []
将函数命名为split
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 [] []
要将其转换为有条件的，我们需要一个计数器.因此，将计数器初始化为splitInner l listMid 0 [] []中的0，并将其传递给匹配模式.由于对于最后一个匹配模式，我们不在乎计数的值是什么，因此使用_代替.
我们还需要知道将计数器与之比较的内容，即listMid，因此将其传递给splitInner.
每次使用磁头也要增加计数器.
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 [] []
现在添加条件
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
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 [] []
这篇关于F#:递归函数:将列表分为两个相等的部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
