鏈接列表分區功能和反向結果

我寫了這個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

鏈接列表分區功能和反向結果

回答

相關問題