のF＃ - 結果の型は、ここで無限のエラー

Question

だろうが、実装に基づいて、すべての順列を生成するための簡単なコードでは、ここで見つける：All permutations of a list

let concatElement element sequence = 
    seq { 
     yield element 
     yield! sequence 
    } 

let rec permute (choices : 'a seq)= 
    seq { 
     if Seq.isEmpty choices then 
      yield Seq.empty 
     else 
      for choice in choices do 
       let remaining = choices |> Seq.where (fun el -> el <> choice) 
       yield concatElement choice (permute remaining) 
    } 

私はコンパイル時にエラーが発生します「結果の型は次のようになり'a'と 'seq <' a> 'を統一すると無限になります"yield concatElement choice (permute remaining)"

ここで何が間違っていますか？

Answer 1

'a seqのシーケンスの1つの要素として、yield'a seqにしようとしています。そのためには、'aは'a seqと同じタイプでなければなりません。したがって、タイプは「無限」です。無限に入れ子にする必要があります。

私は、あなたが何らかの形でシーケンス要素をループする必要があることを認識していることが分かりました。あなたが持っているように、for .. inの構文を使って反復することができます。あるいはF＃は実際にこれを行うyield!演算子を提供します。この精神で、あなたの答えは

let rec permute (choices : 'a seq) (permBuilder: 'a seq) : seq<seq<'a>>= seq { 
    if Seq.isEmpty choices then 
     yield permBuilder 
    else 
     for choice in choices do 
      let remaining = choices |> Seq.where (fun el -> el <> choice) 
      let newBuilder = concatElement choice permBuilder 
      yield! permute remaining newBuilder } 

あるいは、その代わりに、私たちは私たちのために（！系列の）自動的に配列の配列を収集するためにSeq.collect機能を使用することができ、私たちは素敵な機能が残っているように記述することができ明示的なイテレータとスタイルコード：考慮すべき

let prepend element sequence = seq { yield element; yield! sequence } 

let rec permute input = 
    if Seq.length input <= 1 then Seq.singleton input 
    else 
     let without element = Seq.where ((<>) element) input 
     let permutations element = permute (without element) |> Seq.map (prepend element) 
     Seq.collect permutations input 

何かが、しかし：あなたが明瞭でない2つの要素を持っている場合はどうなりますか？たとえば、[1; 1; 2]の順列を取得しようとするとどうなりますか？現在の方法ではこれをうまく処理できません。たとえあなたがwithoutのクロージャを改善したとしても、重複した回答が得られます。

Answer 2

私はLee'veがコメントしたように、私はそれを

let concatElement element sequence = 
    seq { 
     yield element 
     yield! sequence 
    } 

let rec permute (choices : 'a seq) (permBuilder: 'a seq) : seq<seq<'a>>= 
    seq { 
     if Seq.isEmpty choices then 
      yield permBuilder 
     else 
      for choice in choices do 
       let remaining = choices |> Seq.where (fun el -> el <> choice) 
       let newBuilder = concatElement choice permBuilder 
       for perm in permute remaining newBuilder do 
        yield perm 

だと思う、私は>> '配列<配列<で>' 配列<をCONCATしようとしました。私のコードは順列よりもループがありませんでした。