4

Hofstadterシーケンスを生成するための素晴らしいhaskellソリューション（ソース）を見つけました：

hofstadter = unfoldr (\(r:s:ss) -> Just (r, r+s:delete (r+s) ss)) [1..]

今、私もそのようなソリューションをF＃で書き込もうとしています。残念ながら（私はF＃にあまり詳しくありません）これまでのところ成功していません。

私の問題は、sequenceF＃でaを使用すると、要素を削除できないように見えることです（haskellソリューションで行われているように）。
のような他のデータ構造arrays、listまたはset要素の削除を可能にするデータ構造は、無限のシーケンスを生成していませんが、特定の要素に対してのみ動作します。

だから私の質問： F＃で要素が削除される無限のシーケンスを生成することは可能ですか？

私がこれまでに試したいくつかのもの：

数列の無限：

let infinite =
    Seq.unfold( fun state -> Some( state, state + 1) ) 1

Hofstadterシーケンス-キーワードがなく、del構文エラーが多いため、機能しません

let hofstadter =
    Seq.unfold( fun (r :: s :: ss) -> Some( r, r+s, del (r+s) ss)) infinite

を使用することを考えSeq.filterましたが、解決策も見つかりませんでした。

4

3 に答える 3

5

deleteシーケンスには関数以上のものが必要だと思います。あなたの例では、シーケンスがサポートしていない無限のコレクションでパターン マッチングが必要です。

Haskell リストの F# 版は、F# PowerPack のLazyListです。LazyList は潜在的に無限であり、パターン マッチングをサポートしているため、delete簡単に実装できます。

ここに忠実な翻訳があります：

open Microsoft.FSharp.Collections.LazyList

let delete x xs =  
    let rec loop x xs = seq {        
        match xs with
        | Nil -> yield! xs
        | Cons(x', xs') when x = x' -> yield! xs'
        | Cons(x', xs') ->
            yield x' 
            yield! loop x xs'
        }
    ofSeq (loop x xs)

let hofstadter =
    1I |> unfold (fun state -> Some(state, state + 1I))
       |> unfold (function | (Cons(r, Cons(s, ss))) -> 
                                 Some(r, cons (r+s) (delete (r+s) ss)) 
                           | _ -> None)
       |> toSeq

ここで興味深いことがいくつかあります。

  • 関数が末尾再帰であることを確認するには、シーケンス式を使用して実装します。delete非末尾再帰バージョンは簡単なはずです。
  • 使用しBigIntegerます。あまり多くの要素が必要ない場合は、 and を使用するintとSeq.initInfiniteより効率的です。
  • ケース リターンNoneを追加して、完全なパターン マッチングを確保します。
  • 最後にLazyListシーケンスに変換します。.NET コレクションとの相互運用性が向上します。

シーケンスでの実装deleteは醜いです。興味がある場合は、参照用に F# のシーケンスから単一の一意でない値を削除するをご覧ください。

于 2013-02-15T14:29:40.173 に答える
4

パッドの解決策は素晴らしいですが、おそらくLazyList実装方法が原因で、スタックオーバーフローが3〜4Kの数値のどこかで発生します。好奇心のために、次の要素を取得するために繰り返し呼び出されるジェネレーター関数 ( unit -> 'a) を中心に構築されたバージョンを作成しました ( の扱いにくさを回避するためIEnumerable)。最初の 10K の数字を取得できました (それ以上は試していません)。

let hofstadter() =

  let delete x f =
    let found = ref false
    let rec loop() =
      let y = f()
      if not !found && x = y
      then found := true; loop()
      else y
    loop

  let cons x f =
    let first = ref true
    fun () -> 
      if !first
      then first := false; x
      else f()

  let next =
    let i = ref 0
    fun () -> incr i; !i

  Seq.unfold (fun next -> 
    let r = next()
    let s = next()
    Some(r, (cons (r+s) (delete (r+s) next)))) next
于 2013-02-15T16:10:23.070 に答える
3

実際、フィルターと haskell ソリューションに従うデザインを使用できます (ただし、@pad が言うように、シーケンスにパターン マッチングがないため、lisp スタイルの破棄を使用しました)。

let infinite = Seq.initInfinite (fun i -> i+1)

let generator = fun ss -> let (r, st)  = (Seq.head ss, Seq.skip 1 ss)                               
                          let (s, stt) = (Seq.head st, Seq.skip 1 st)
                          let srps     = seq [ r + s ]
                          let filtered = Seq.filter (fun t -> (r + s) <> t) stt
                          Some (r, Seq.append srps filtered)

let hofstadter = Seq.unfold generator infinite                               

let t10 = Seq.take 10 hofstadter |> Seq.toList
// val t10 : int list = [1; 3; 7; 12; 18; 26; 35; 45; 56; 69]

ただし、効率については主張しません。

于 2013-02-15T15:28:36.133 に答える