F＃：遞歸函數：將列表拆分成兩個相等部分

Question

我在拆分和合並索引時遇到了一些錯誤。 （注意，這是一個格式化的分配需要針對每個功能特定的輸入&輸出類型）

這裏是我的代碼現在：在

(* 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功能未與拆分工作以及「然後」最後一行代碼是不正確的。

這個想法如下：給定列表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 

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

名稱的功能拆分

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

由於拆分會將列表分成兩半，這可以在迭代t之前計算通過列表

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

Answer 2

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

Answer 3

你還是老樣子在你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]) 

Answer 4

Guy Coder提出了相當多的方式列表分爲兩個部分，這裏是另一個學習歸併的時候我一直在教導（我認爲，最簡單的一個）：

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