将列表拆分为两个
我想实现一个函数,它需要输入一个大小为n和一个列表。这个函数将把列表切成两个列表,其中一个大小为n,其余列表为其余列表。我是这种语言的新手,很难学习语法。将列表拆分为两个
我的主要问题是找到一种方法来表示列表的大小,而不使用任何循环或可变变量。
任何人都可以给我一些指针吗?
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)
我不太了解你的代码,但似乎它使用了一个循环。我正在考虑做一些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]
+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是褶皱比你可以按照一个伟大的系列赛了解更多关于这个话题。
这个函数是不是遍历*整个*列表,而不是刚刚达到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
你有什么试过的?至少你应该给我们一个非工作版本来展示你的努力? – pad 2012-02-01 22:28:28
提示:你不需要表达列表的长度 - 你所需要的只是一种减少'n'的方法,并检查它是否已经达到零。 – dasblinkenlight 2012-02-01 22:30:05
这可能有点偏离主题,但是有一个相当整洁的解决方案(由朱丽叶设计)将列表分成两部分,不需要事先知道/指定长度:http://*.com/questions/4866640/split- list-into-two-equal-lists-in -f – 2012-02-12 19:37:20