リンクされたリストパーティション関数とその逆の結果

Question

リストを特定のポイントまでパーティション分割するために、これを書いたのはtakeWhileとpartitionの間のクロスのようなものです。 revを呼び出すに頼るよりも

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

その他、最初のリストがあることだろう。この関数は書くことができます方法があります：

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 

唯一の問題は、「とら」の項目が逆転しているということです正しい順序で？

Answer 1

続きは次のバージョンです。これはtail-recursiveで、元の順序でリストを返します。

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：

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 

はここでブライアンの答え（および参照用アキュムレータ版）以下の議論と一緒に行くためにいくつかのベンチマークです。要するに、継続はあなたにこの運動のための何も買わない。

Answer 2

あなたはこのような関数を書き換えることはできません。

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 

はい、ブライアンは指摘しているとして、それはもはや末尾再帰であるが、述べたように、それは質問に答えます。ちなみに、Haskellではspanは抱擁で全く同じように実装されています

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

をHaskellで、このバージョンを好むための良い理由は怠惰です：リストが逆転する前に、最初のバージョンでは、すべての良い要素が訪れています。 2番目のバージョンでは、最初の正常な要素をすぐに返すことができます。

Answer 3

私はあなたが継続を使用できると期待していますが、最後にList.revを呼び出すことが最善の方法です。

Answer 4

私は通常、シーケンスが怠けているので、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) 

Answer 5

私はダニエルの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 

私はこのソリューションが気に入っています。なぜなら、最初のリストの最後までドリルダウンし、2番目のリストを後方に構築することによって、List.revを使用する必要がないkludgeyが少なくなったからです。私は.revを避けるための他の主な方法は、cons操作でtail再帰を使うことだと思います。いくつかの言語は適切な末尾再帰と同じ方法で "tail recursion mod cons"を最適化します（しかし、Don SymeはこれがF＃には来ないと言いました）。

これはF＃でテール再帰的には安全ではありませんが、私の答えは答えとなり、リストは避けられます。REV（これはそれ以外のアプローチ、私たちは唯一の最初のリストを返した場合のように、考える2組の要素にアクセスする必要が醜いと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