我如何使用尾部实现我自己的List.partition
我正在尝试为F＃练习编写自己的List.partition函数。 这是我第一次（天真）的尝试：
let rec mypartition_naive func list =
match list with
| [] -> ([],[])
| head::tail ->
let (h1,h2) = mypartition_naive func tail
if func head
then (head::h1,h2)
else (h1,head::h2)
这有效，但它不是尾递归。 我在第二次尝试中使用累加器来进行尾递归：
let mypartition_accumulator func list =
let rec helper acc listinner =
match listinner with
| head::tail ->
let a,b = acc
let newacc = if func head then (head::a,b) else (a,head::b)
helper newacc tail
| _ -> acc
helper ([],[]) list
严格来说，这是有效的：它对列表进行分区。 问题是这颠倒了列表的顺序。 我得到这个：
let mylist = [1;2;3;4;5;6;7;8]
let partitioned = mypartition_accumulator (fun x -> x % 2 = 0) mynums
//partitioned is now ([8; 6; 4; 2], [7; 5; 3; 1])
//I want partitioned to be ([2; 4; 6; 8], [1; 3; 5; 7])
我认为我可以使用continuation传递来编写一个不反转列表元素的尾递归分区函数，但我并不真正了解延续传递（并且我已经阅读了很多关于它的内容）。 如何使用尾递归编写分区并保持列表元素的顺序？
这是一个CPS版本，但List.rev是要走的路（参见这个相关答案）。
let partition f list =
let rec aux k = function
| h::t -> aux (fun (a, b) ->
k (if f h then h::a, b else a, h::b)) t
| [] -> k ([], [])
aux id list
虽然已经回答，但这个问题值得尝试解释。 基于累加器的尾递归版本基本上是fold ，从左到右，因此需要反转。
let fold folder state list : 'State =
let rec aux state = function
| [] -> state
| h:'T::t -> aux (folder state h) t
aux state list
// val fold : folder:('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State
let partitionFold p =
fold (fun (a, b) h -> if p h then h::a, b else a, h::b) ([], [])
>> fun (a, b) -> List.rev a, List.rev b
partitionFold (fun x -> x % 2 = 0) [0..10]
// val it : int list * int list = ([0; 2; 4; 6; 8; 10], [1; 3; 5; 7; 9])
fold的签名和功能现在与标准库中的List.fold完全相同。
相比之下，continuation-passing风格的版本相当于foldBack （参见List.foldBack ）。 它从右向左（最后一个元素第一个）递归地迭代，从而立即获得所需的顺序。
let foldBack folder list state : 'State =
let rec aux k = function
| [] -> k state
| h:'T::t -> aux (folder h >> k) t
aux id list
// val foldBack :
// folder:('T -> 'State -> 'State) -> list:'T list -> state:'State -> 'State
let partitionFoldBack p list =
foldBack (fun h (a, b) -> if p h then h::a, b else a, h::b) list ([], [])
partitionFoldBack (fun x -> x % 2 = 0) [0..10]
// val it : int list * int list = ([0; 2; 4; 6; 8; 10], [1; 3; 5; 7; 9])