9

F# でリストの先頭に追加するのはやや面倒です。完了したら元に戻す必要があるからです。最初からリストを作成する方法はありますか?

4

4 に答える 4

3

次のように追加xしxsます。

xs @ [x]

これは O(n) であることに注意してください。

于 2013-09-20T20:30:03.100 に答える
3

元のコードを参照すると、探しているのはList.foldBackではなく使用することだと思いますList.fold。基本的に、リストの先頭からではなく、リストの末尾から関数foldBackを繰り返し適用します。folderほど効率的ではありませんfoldが、リストを逆に使用foldBackして回避することをお勧めします。

を使用foldBackすると、累積関数folderは次のようにリストに適用さx0::x1::...::xlastれます。ここで、への最初の引数folderは ですinit。

folder x0 (folder x1 ( ... (folder xlast init) ... ) )

cffold

folder (... (folder (folder init x0) x1) ...) xlast

別の解決策を提案する元の質問に対する他の回答がいくつかありますが、コードに固執し、最初の実装で結果を代用foldBackしますfold

let chunkOrig items chunkSize =
    let folder =
        fun x (result, chunk) ->
            if List.length chunk < chunkSize then
                (result, x::chunk)
            else
                (chunk::result, [x])
    let (a,b) = List.foldBack folder items ([], []) 
    b::a

すべてのリストの反転がなくなったので、これはすでにはるかに簡単です。そしてそれはうまくいくようです。

> chunkOrig [1..10] 2;;
val it : int list list = [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]]

ただし、リストが等しいチャンクに分割されていない場合foldBack、最後の要素から始まるため、うまくいきません。

> chunkOrig [1..11] 2;;
val it : int list list = [[1]; [2; 3]; [4; 5]; [6; 7]; [8; 9]; [10; 11]]

あなたがする必要があるfolderのは、チャンク自体ではなく、現在のチャンクに残っている長さによってローカル関数をパラメータ化することです。

let chunk items chunkSize =
    let folder =
        fun x (result, lenLeft) ->
        if lenLeft > 0 then
            match result with
               | [] -> ([[x]], lenLeft-1)
               | r0::rtail -> ((x::r0)::rtail, lenLeft-1)
        else
            ([x]::result, chunkSize-1)
    let (result, lenLeft) = List.foldBack folder items ([], (List.length items) % chunkSize) 
    result

> chunk [1..10] 2;;
val it : int list list = [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]]

> chunk [1..11] 2;;
val it : int list list = [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]; [11]]
于 2013-09-17T15:21:13.167 に答える
3

リストの前に付けたり逆にしたりしても問題はありません。@要素が 1 つのリストにappend ( ) を使用できますが、コードの匂いがします。許容できる (末尾再帰) アプローチは次のとおりです。

let appendSingle xs x =
    [ yield! xs
      yield x ]

上記のすべてのソリューションの実行時間は O(n) です。あなたのユースケースでは、プライベートResizeArrayを保持して、リバースの使用を避けることができます。可変性が隠されているので問題ありません。この機能を比較

let filter f l = 
  let rec loop acc l =
    match l with 
    | [] -> List.rev acc                        
    | x::xs when f x -> loop (x::acc) xs  
    | x::xs -> loop acc xs
  loop [] l

より効率的な相手と

let filter f l = 
  let rec loop (acc : ResizeArray<_>) l =
    match l with 
    | [] -> Seq.toList acc                        
    | x::xs when f x -> 
        acc.Add(x)  
        loop acc xs  
    | x::xs -> loop acc xs
  loop (ResizeArray()) l
于 2013-09-17T14:55:26.517 に答える