将列表拆分为两个

我想实现一个函数，它需要输入一个大小为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

将列表拆分为两个

回答

相关问题