链表分区函数和反转结果 [英] Linked list partition function and reversed results

问题描述

我编写了这个 F# 函数来将列表分区到某个点而不是进一步——很像 takeWhile 和 partition 之间的交叉.

I wrote this F# function to partition a list up to a certain point and no further -- much like a cross between takeWhile and 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

唯一的问题是被拿走"的项目被颠倒了:

The only problem is that the "taken" items are reversed:

> partitionWhile ((>=) 5) [1..10];;
val it : int list * int list = ([5; 4; 3; 2; 1], [6; 7; 8; 9; 10])

除了调用 rev 之外，有没有办法编写这个函数，让第一个列表的顺序正确?

Other than resorting to calling rev, is there a way this function could be written that would have the first list be in the correct order?

推荐答案

这是一个基于延续的版本.它是尾递归的，并按原始顺序返回列表.

Here's a continuation-based version. It's tail-recursive and returns the list in the original order.

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 的回答(以及累加器版本以供参考)之后的讨论相结合的基准:

Here are some benchmarks to go along with the discussion following Brian's answer (and the accumulator version for reference):

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.简而言之，延续对于这个练习没有任何帮助.

Cps averaged ~7s, Acc ~4s. In short, continuations buy you nothing for this exercise.

这篇关于链表分区函数和反转结果的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！