私は整数をとり、整数のリストを返す関数を持っています。関数の結果から無限リストを生成する
この関数を最初の整数に効率的にマップする方法と、以前にマップされていない結果リストの各項目に対して、同じ関数を適用し、本質的に無限リストを生成します。
など。
f :: Int -> [Int]
f 0 = [1,2]++(f 1)++(f 2)
さらに、結果リストを10E10まで索引付けできる必要があります。これはどのように最適化されますか？メモ？
幅優先検索が必要です。基本的なイディオムはこのように書きます：私たちは、引数xs、出力でそれを現在の「状態」を維持し、どのように
bfs :: (a -> [a]) -> [a] -> [a]
bfs f xs = xs ++ bfs f (concatMap f xs)
通知は、再帰的に入力状態の各要素に適用されるfある新しい状態と呼んでいます。
以前に見たことのない要素を除外するには、見たことのある要素を追跡する余分な状態を渡す必要があります。 Data.Setを入力し、それに応じてアルゴリズムを調整します。私は刺激的な教育者であるので、私はあなたにそのビットを残しておきます。
ありがとう、これは私が思いついたものに非常に似ています。しかし、最適化は可能ですか？結果リストのために現在10E6で値を取得しているのは私のマシンで約20秒かかります。 – iamogbz
繰り返し値がある場合は、それをプルーニングすることで、まだそれを行っていない場合には、非常に役立ちます。幅優先探索もうまく並列化すべきですが、チューニング権を取得するのは難しいかもしれません（そして、私はそれほど専門家ではありません - 他のSO質問のための飼育者かもしれません）。さもなければ、私はあなたが利用できる検索機能（例えば、常に2つの値を計算する場合、いくつかの対数や何かを使って10e6要素の正確な式を計算することができます）でいくつかの数学的構造を探します。 – luqui
ああ、ランダムな考え方です。厳密なインデックス付け '' ix 0（x：xs）= x; n番目の要素を得るためにix n（x：xs）= x 'seq' ix（n-1）xs''を使用します。関数が非常に簡単な場合は、いくつかのサンクの蓄積に苦しんでいる可能性があります。もちろん、常に '-O'でコードをコンパイルしてください。 – luqui
これは考えられない例の場合ですが、この定義は無効です。 'f'は0に対してのみ*定義されています。 'f1'と' f2'は全く定義されていません。 'Data.List.unfoldr'について読んでみてください。 – chepner
@chepnerもっと多くの例を追加することができますが、質問を理解するために必要だったもの以上を定義したくありませんでした – iamogbz