將列表拆分爲兩個

我想實現一個函數，它需要輸入一個大小爲n和一個列表。這個函數將把列表切成兩個列表，其中一個大小爲n，其餘列表爲其餘列表。我是這種語言的新手，很難學習語法。將列表拆分爲兩個

我的主要問題是找到一種方法來表示列表的大小，而不使用任何循環或可變變量。

任何人都可以給我一些指針嗎？

2012-02-01 user1072706

你有什麼試過的？至少你應該給我們一個非工作版本來展示你的努力？ – pad 2012-02-01 22:28:28

提示：你不需要表達列表的長度 - 你所需要的只是一種減少'n'的方法，並檢查它是否已經達到零。 – dasblinkenlight 2012-02-01 22:30:05

這可能有點偏離主題，但是有一個相當整潔的解決方案（由朱麗葉設計）將列表分成兩部分，不需要事先知道/指定長度：http://stackoverflow.com/questions/4866640/split- list-into-two-equal-lists-in -f – 2012-02-12 19:37:20

let split n list = 
    let rec not_a_loop xs = function 
    | (0, ys) | (_, ([] as ys)) -> (List.rev xs), ys 
    | (n, x::ys) -> not_a_loop (x::xs) (n-1, ys) 
    not_a_loop [] (n, list)

來源

2012-02-01 22:37:26 Daniel

我不太瞭解你的代碼，但似乎它使用了一個循環。我正在考慮做一些recurisve調用，我會指定n作爲索引，並在找到位置爲n的項目時作爲基本案例返回。您怎麼看？ – user1072706 2012-02-01 22:54:09

這或多或少是這樣做的，沿途會在'n'之前積累元素。 – Daniel 2012-02-01 23:00:08

@ user1072706：不，它使用遞歸函數_named_循環。這個名字是任意的，不要讓它迷惑你。 – ildjarn 2012-02-01 23:00:15

讓我們從函數的類型簽名開始。因爲它得到n和一個列表作爲參數和返回兩個列表，你有一個函數split：

val split : int -> 'a list -> 'a list * 'a list

這裏是實現這種功能的一種方法：

let split n xs = 
    let rec splitUtil n xs acc = 
    match xs with 
    | [] -> List.rev acc, [] 
    | _ when n = 0 -> List.rev acc, xs 
    | x::xs' -> splitUtil (n-1) xs' (x::acc) 
    splitUtil n xs []

的想法是使用累加器acc用於保存已經遍歷的元素，並減少很長的一段時間。由於元素預先寫入acc，所以最後必須將其反轉以獲得正確的順序。

該函數有兩個基本情況終止：

有沒有留下元素遍歷（xs = []在這一點）。
您已經經歷了列表中的第一個n元素（當時n減少爲0）。

下面是如何split計算結果的簡短的描述：

split 2 [1; 2; 3] // call the auxiliary function splitUtil 
~> splitUtil 2 [1; 2; 3] [] // match the 3rd case of x::xs' 
~> splitUtil 1 [2; 3] [1] // match the 3rd case of x::xs' 
~> splitUtil 0 [3] [2; 1] // match the 2nd case of n = 0 (base case) 
~> List.rev [2; 1], [3] // call List.rev on acc 
~> [1; 2], [3]

來源

2012-02-01 23:04:50 pad

+1用於分解遞歸過程。 – ildjarn 2012-02-01 23:26:30

感謝您的詳細解釋。 – user1072706 2012-02-01 23:57:35

最後一個「splitUtil n xs []」在函數中扮演什麼角色？ – user1072706 2012-02-02 03:13:52

另一種方式，用fold：

let biApply f (a, b) = (f a, f b) 

let splitAt n list = 
    let splitter ((xs, ys), n') c = 
    if n' < n then 
     ((c :: xs, ys), n' + 1) 
    else 
     ((xs, c :: ys), n' + 1) 
    List.fold splitter (([], []), 0) list 
    |> fst 
    |> biApply List.rev

Here是褶皺比你可以按照一個偉大的系列賽瞭解更多關於這個話題。

來源

2012-02-04 18:45:47 missingfaktor

這個函數是不是遍歷*整個*列表，而不是剛剛達到n？ – Henrik 2013-05-07 08:32:17

新解決方案 - splitAt現在內置於List和Array中。參見2014年github上的提交。我注意到了這一點今天在使用F＃中VS.2015

現在，你可以簡單地做到這一點...

let splitList n list = 
    List.splitAt n list

正如你所期望的簽名是...

n: int -> list: 'a list -> 'a list * 'a list

例用法：

let (firstThree, remainder) = [1;2;3;4;5] |> (splitList 3) 
printfn "firstThree %A" firstThree 
printfn "remainder %A" remainder

輸出：

firstThree [1; 2; 3] 
remainder [4; 5]

Github感興趣的人：https://github.com/dsyme/visualfsharp/commit/1fc647986f79d20f58978b3980e2da5a1e9b8a7d

來源

2015-09-01 02:03:02 ripvlan

將列表拆分爲兩個

回答

相關問題