F＃のシーケンスを慣用的な方法で別のシーケンスに基づいて分割する方法

Question

F＃では2つのシーケンスがそれぞれ厳密に昇順に並べられています。listMaxesとnumbersです。

not Seq.isEmpty numbersの場合、not Seq.isEmpty listMaxesとSeq.last listMaxes >= Seq.last numbersが保証されます。

IはlistMaxes限界の場合の要素、リストに分割numbersの要素を含む、F＃でList.lengthSeq.length listMaxesに等しい整数のリストのリストを返す関数を実装するために、各グループにたいです。例えば

：この関数は

[ [10; 11; 13; 16; 20; 25]; [31; 38; 46; 55]; [65]; List.empty; [76; 88] ] 

を返す必要があります

listMaxes = seq [ 25; 56; 65; 75; 88 ] 
numbers = seq [ 10; 11; 13; 16; 20; 25; 31; 38; 46; 55; 65; 76; 88 ] 

引数で呼び出さ私は一度だけnumbersを反復、この機能を実装することができます

let groupByListMaxes listMaxes numbers = 
    if Seq.isEmpty numbers then 
     List.replicate (Seq.length listMaxes) List.empty 
    else 
     List.ofSeq (seq { 
      use nbe = numbers.GetEnumerator() 
      ignore (nbe.MoveNext()) 
      for lmax in listMaxes do 
       yield List.ofSeq (seq { 
        if nbe.Current <= lmax then 
         yield nbe.Current 
        while nbe.MoveNext() && nbe.Current <= lmax do 
         yield nbe.Current 
       }) 
     }) 

しかし、これをコードは汚れていて、醜く、命令的で、非常にun-F＃-yと感じます。

これを実現する機能/ F＃自主的な方法はありますか？

Answer 1

それは、パターンマッチングと末尾再帰で次のように行うことができます。

let groupByListMaxes listMaxes numbers = 
    let rec inner acc numbers = 
     function 
     | [] -> acc |> List.rev 
     | max::tail -> 
      let taken = numbers |> Seq.takeWhile ((>=) max) |> List.ofSeq 
      let n = taken |> List.length 
      inner (taken::acc) (numbers |> Seq.skip n) tail 

    inner [] numbers (listMaxes |> List.ofSeq) 

更新は：私もfoldに触発と思い付いてしまいました入力シーケンスの変換を厳密に控える以下のソリューションを使用します。

let groupByListMaxes maxes numbers = 
    let rec inner (acc, (cur, numbers)) max = 
     match numbers |> Seq.tryHead with 
     // Add n to the current list of n's less 
     // than the local max 
     | Some n when n <= max -> 
      let remaining = numbers |> Seq.tail 
      inner (acc, (n::cur, remaining)) max 
     // Complete the current list by adding it 
     // to the accumulated result and prepare 
     // the next list for fold. 
     | _ -> 
      (List.rev cur)::acc, ([], numbers) 

    maxes |> Seq.fold inner ([], ([], numbers)) |> fst |> List.rev 

Answer 2

ここでは、リストの解釈に基づいたバージョンがあります。このバージョンは、かなり機能的です。あなたはそれを処理したいときはいつでも、Seq.toListを使ってそれらの間で変換することができます。また、ライブラリ関数のみを使用する場合は、Seq.scanとSeq.partition ((>=) max)を併用することもできますが、計算やメモリに2次の複雑さを導入するのは非常に簡単です。

これは、両方で線形である：

let splitAt value lst = 
    let rec loop l1 = function 
     | []     -> List.rev l1, [] 
     | h :: t when h > value -> List.rev l1, (h :: t) 
     | h :: t    -> loop (h :: l1) t 
    loop [] lst 

let groupByListMaxes listMaxes numbers = 
    let rec loop acc lst = function 
     | []  -> List.rev acc 
     | h :: t -> 
      let out, lst' = splitAt h lst 
      loop (out :: acc) lst' t 
    loop [] numbers listMaxes 

Answer 3

私はより良い実装を自分で見つけました。改善のヒントはまだ歓迎されています。

2つの配列を扱うことは本当に苦労します。そして、私は実際にnumbersを繰り返して、そのシーケンスをリストに入れないで1回だけしたいと思います。しかし、私はlistMaxes（一般にシーケンスのほうが短い）を回すことはコストがかからないことに気付きました。そうすれば、1つのシーケンスしか残らず、numbersを超えてSeq.foldを使うことができます。

Seq.foldで反復処理している間に、保持して変更したい状態は、numbers以上にする必要がありますか？まず、それは間違いなくlistMaxesの残りを含めるべきですが、私たちがすでに超えている以前の最大値はもはや関心がありません。第二に、累積されたリストは、これまでのところ、他の回答と同様に、逆の順序で保存することができます。より多くのポイント：状態は、これまでの番号の逆のリストの逆のリストを第2の要素として有するカップルである。あなたは、複数の数字で最大の要素よりも大きい「maxes」を持っているときnbe.Currentが最終的に（）がfalseを返すnbe.MoveNext後に呼び出されますので

let groupByListMaxes listMaxes numbers = 
    let rec folder state number = 
     match state with 
      | m :: maxes, _ when number > m -> 
       folder (maxes, List.empty :: snd state) number 
      | m :: maxes, [] -> 
       fst state, List.singleton (List.singleton number) 
      | m :: maxes, h :: t -> 
       fst state, (number :: h) :: t 
      | [], _ -> 
       failwith "Guaranteed not to happen" 
    let listMaxesList = List.ofSeq listMaxes 
    let initialState = listMaxesList, List.empty 
    let reversed = snd (Seq.fold folder initialState numbers) 
    let temp = List.rev (List.map List.rev reversed) 
    let extraLength = List.length listMaxesList - List.length temp 
    let extra = List.replicate extraLength List.empty 
    List.concat [temp; extra]