我编写了这个 F# 函数来将列表划分到某个点,不再进一步——很像 takeWhile
和 partition
之间的交叉。
let partitionWhile c l =
let rec aux accl accr =
match accr with
| [] -> (accl, [])
| h::t ->
if c h then
aux (h::accl) t
else
(accl, accr)
aux [] l
唯一的问题是“拿走”的项目被颠倒了:
> partitionWhile ((>=) 5) [1..10];;
val it : int list * int list = ([5; 4; 3; 2; 1], [6; 7; 8; 9; 10])
除了求助于调用 rev
之外,有没有一种方法可以编写此函数,使第一个列表的顺序正确?
最佳答案
这是一个基于延续的版本。它是尾递归的,并以原始顺序返回列表。
let partitionWhileCps c l =
let rec aux f = function
| h::t when c h -> aux (fun (acc, l) -> f ((h::acc), l)) t
| l -> f ([], l)
aux id l
在 Brian 的回答(以及供引用的累加器版本)之后,这里有一些基准与讨论一起进行:
let partitionWhileAcc c l =
let rec aux acc = function
| h::t when c h -> aux (h::acc) t
| l -> (List.rev acc, l)
aux [] l
let test =
let l = List.init 10000000 id
(fun f ->
let r = f ((>) 9999999) l
printfn "%A" r)
test partitionWhileCps // Real: 00:00:06.912, CPU: 00:00:07.347, GC gen0: 78, gen1: 65, gen2: 1
test partitionWhileAcc // Real: 00:00:03.755, CPU: 00:00:03.790, GC gen0: 52, gen1: 50, gen2: 1
Cps
平均 ~7s,Acc
~4s。简而言之,延续对本练习没有任何帮助。
关于list - 链表分区函数和反转结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7199122/