链接列表分区功能和反向结果

我写了这个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其他，有没有办法这个功能可以写，将有第一个列表是按正确的顺序？

来源

2011-08-26 Rei Miyasaka

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

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

这里有一些基准与讨论一起去以下布赖恩的回答（和蓄能器版本以供参考）：

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平均〜7秒，Acc〜4秒。总之，继续这个练习不会为你购买任何东西。

来源

2011-08-26 04:22:48 Daniel

感谢您的所有努力！ –

你可以重写的功能是这样的：

let partitionWhile c l = 
    let rec aux xs = 
    match xs with 
     | [] -> ([], []) 
     | h :: t -> 
      if c h then 
      let (good, bad) = aux t in 
       (h :: good, bad) 
      else 
      ([], h :: t) 
    aux l

是的，正如布赖恩指出它不再是尾递归，但它回答了说明。顺便说一句，span在Haskell中实现完全相同的方式拥抱：

span p []  = ([],[]) 
span p [email protected](x:xs') 
    | p x  = (x:ys, zs) 
    | otherwise = ([],xs) 
    where (ys,zs) = span p xs'

一个很好的理由更喜欢这个版本中Haskell是懒惰：在第一个版本是相反的列表之前所有美好的元素被访问。在第二个版本中，第一个元素可以立即返回。

来源

2011-08-26 01:41:32 antonakos

仅供参考，这是不是尾递归，所以它会在一个非常大的列表中被'StackOverflowException'炸毁。 – Brian

似乎是一种相当危险的方式来实现可能用于巨大列表的算法。 Haskell是否提供更大的堆栈或其他？ –

@Rei原因是懒惰。我最好也提一下。 – antonakos

我希望你可以使用延续，但最后调用List.rev是最好的方法。

来源

2011-08-26 01:42:41 Brian

除了因为它更容易，是否有理由赞成累加器+ List.rev'而不是CPS？ – Daniel

写起来更容易，阅读更容易，并且可能更具性能。 – Brian

在我可以说任何事情之前，我将不得不更多地阅读延续...嗯.... –

我通常喜欢列表上的序列，因为他们是懒惰的，你得到了List.toSeq和Seq.toList函数在它们之间进行转换。以下是使用序列的partitionWhile函数的实现。

let partitionWhile (c:'a -> bool) (l:'a list) = 
    let fromEnum (e:'a IEnumerator) = 
     seq { while e.MoveNext() do yield e.Current} 
    use e = (l |> List.toSeq).GetEnumerator() 
    (e |> fromEnum |> Seq.takeWhile c |> Seq.toList) 
    ,(e |> fromEnum |> Seq.toList)

来源

2011-08-26 04:20:06 Ankur

我不认为我是唯一一个从Daniel的CPS解决方案中学到很多东西的（挣扎着）。在试图弄清楚，它帮助我有可能改变一些（对初学者）暧昧列表的引用，就像这样：（需要注意的是“[]”中的L4比赛是最初的ACC值）

let partitionWhileCps cond l1 = 

     let rec aux f l2 = 
      match l2 with 
      | h::t when cond h -> aux (fun (acc, l3) -> f (h::acc, l3)) t 
      | l4 -> f ([], l4) 

     aux id l1

我喜欢这个解决方案，因为它感觉不需要使用List.rev，通过钻到第一个列表的末尾并向后建立第二个列表。我认为避免.rev的另一个主要方法是使用尾部递归和cons操作。一些语言以与正确的尾递归相同的方式优化“尾递归mod缺点”（但是Don Syme已经表示这不会到达F＃）。

因此，这不是F＃中的尾递归安全，但它使我的答案成为答案并避免了List。REV（这是丑陋的有访问这两个元组元素，并会更贴合平行于CPS的方式，否则，我认为，就像如果我们只返回的第一个列表）：

let partitionWhileTrmc cond l1 = 

     let rec aux acc l2 = 
      match l2 with 
      | h::t when cond h -> (h::fst(aux acc t), snd(aux acc t)) 
      | l3 -> (acc, l3) 

     aux [] l1

来源

2015-09-02 20:32:17 RomnieEE

链接列表分区功能和反向结果

回答

相关问题