list - F#:递归函数:将列表分为两个相等的部分

Question

我在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函数不适用于split，并且最后一行代码中的“then”不正确。

想法如下:给定的列表l分为两个相等的列表(如果l的长度为奇数，则“一半”中的一个比另一半长)则列出列表l1和l2。这些列表以递归方式排序，然后将结果合并回给单个排序列表。用F＃编写代码。您的算法可以使用<作为比较运算符。您的代码必须具有产生一对列表的函数拆分，合并已排序列表的函数合并以及实现整体算法的函数mergesort。

编辑:我相信我不允许在此作业上使用 |> List.splitAt。我正在尝试实现将执行相同操作的辅助函数。

EDIT2:谢谢Guy Coder，您的回答非常详尽。我需要将功能拆分为仅包含一个列表。也许我可以在内部创建一个辅助函数，该函数使用基于 list.Length/2的索引？假定列表输入为 float list，并且该函数返回2 float lists。

EDIT3:我感觉更近了:这是我的分割函数和收到的错误。

(* 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

// 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中至少有两项，则将其中一项放在列表一中，将另一项放在列表二中。重复此操作，直到列表中没有一个或没有任何项目。如果列表中有一项，则将其放入第一个列表并重复。现在输入列表为空，因此返回两个列表。

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使用 Continuation-passing style

该函数将一个函数传递给内部函数。函数是 (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到 posted的第四个变体。

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 []

将功能命名为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 []

现在我知道我需要一个输入列表和两个输出列表，其中两个输出列表在一个元组中

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 [] []

要将其变为有条件的，我们需要一个计数器。因此，将计数器初始化为 0中的 splitInner l listMid 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 [] []