問題タブ [lazy-sequences]

今日、私は高階関数の書き方がわからないという考えを持っていました。私はいくつかのまばらで怠惰な無限のシーケンスを持っています、そして私は与えられた数がこれらの怠惰なシーケンスのいずれかにあるかどうかをチェックできる抽象化を作成したいと思います。パフォーマンスを向上させるために、スパースシーケンスの値をハッシュマップ（またはセット）にプッシュし、必要に応じてハッシュマップの値の数を動的に増やしたいと思いました。怠惰なシーケンスが少ないため、自動メモ化はここでは答えではありません。

おそらくコードは最も理解しやすいので、これが私がこれまでに持っているものです。述語がクローズドオーバーハッシュマップを使用するように次のコードを変更するにはどうすればよいですか？ただし、必要に応じてハッシュマップのサイズを増やし、新しいハッシュマップを使用するように自身を再定義しますか？

命令型に戻らずにこの問題を解決するにはどうすればよいですか？

ジェネレーターが値を終了せず、必要なすべての結果が読み取られたときに、生成を停止する方法はありますか? つまり、ジェネレーターは StopIteration を実行せずに値を提供しています。

たとえば、これは止まらない: (改訂版)

このコードを見つけましたが、この場合の適用方法はまだわかりません: http://code.activestate.com/recipes/576585-lazy-recursive-generator-function/

編集：これを書いている過程で自分の質問に対する部分的な答えを発見しましたが、簡単に改善できると思うので、とにかく投稿します。多分そこにもっと良い解決策がありますか？

letに頼らずにフォームで再帰関数を定義する簡単な方法を探していますletfn。letこれはおそらく不合理な要求ですが、私がこの手法を探している理由は、多くのネストされたandletfnステートメントを必要とする方法で相互に依存するデータと再帰関数が混在しているためです。

次のような遅延シーケンスを生成する再帰関数を書きたいと思いました (例としてフィボナッチ数列を使用)。

fibsしかし、バインド中に独自のシンボルを使用できないのは clojure のようです。それを回避する明白な方法はletfn

しかし、前に述べたように、これは多くの厄介なネストと交互のletandにつながりletfnます。

letfnだけを使用せずにこれを行うためにlet、U-combinator と思われるものを使用するものを作成することから始めました (今日その概念について聞いたばかりです)。

しかし、どのように冗長性を取り除くの(fi fi)ですか?

この時点で、コンビネータ Q に 1 時間も苦労して少しずつビットを追加した後、自分の質問に対する答えを発見しました。

Q再帰シーケンスを定義するために使用しているこのコンビネータは何と呼ばれていますか? 引数のない Y コンビネータのように見えますx。それは同じですか？

YまたはQの機能を提供するclojure.coreまたはclojure.contribの別の機能はありますか? 私がしたことが慣用的だったとは想像できません...

私は、遅延して減らしてテストしたい、長くて怠惰なシーケンスを持っています。2 つの連続する要素=(または他の述語) が互いに一致しなくなったらすぐに、作成にコストがかかるリストの消費を停止したいと考えています。はい、これは のように聞こえますがtake-while、さらに読んでください。

私は次のようにシンプルでエレガントなものを書きたいと思っていました (のようにevery?動作するふりをしますreduce):

しかし、それは怠惰に機能しないため、無限の seq にハングアップします。これがほぼ希望どおりに機能することを発見しました。

しかし、シーケンスのチャンクによって余分な不要な要素が作成され、テストされることに気付きました。少なくとも、これは次のコードで起こっていることだと思います。

take-while、 を使用して、取得した要素の数を確認する回避策を見つけましたcountが、それはかなり面倒です。

Rich Hickey に、 と を適切に組み合わせreduceてevery?短絡するよう丁寧に提案する必要がありますか? それとも、既に存在する明らかな方法を見逃しているのでしょうか?

編集:apply 2 人の親切な人が、遅延シーケンスでのチャンクを回避するためのソリューションを投稿しましたが、4 つのチャンク グループで消費しているように見える を実行するときにチャンクを回避するにはどうすればよいですか?

編集 #2: Stuart Sierra が指摘し、私が独自に発見したように、これは実際にはチャンクではありません。ふつうに演技をするだけなので、これをクローズと呼び、彼に答えを出します。興味のある人のために、問題のreduce'ing部分を行うために、別の回答に小さな関数を含めました。

BufferedReader を使用してオブジェクトのストリーミング読み取りを実行しています。

このオブジェクトで 2 つのことを行う必要があります。

1. SuperCSV csv リーダーに渡す
2. 生の行を取得し、(Clojure) 遅延シーケンスに保持する

現在、2 つの異なる BufferedReaders を使用する必要があります。1 つは SuperCSV CSV リーダー クラスへの引数として、もう 1 つは生の行の遅延シーケンスを初期化するためです。S3 オブジェクトを効果的に 2 回ダウンロードしていますが、これは高価 ($) で低速です。

私の同僚の 1 人が、私が探しているのは Unix の「tee」コマンドに類似したものだと指摘しました。どういうわけか「分割」でき、データのチャンクをダウンロードし、コピーをレイジー シーケンスと csv リーダー機能の両方に渡すことができる BufferedReader が役立ちます。

また、遅延シーケンスを BufferedReader でラップして、それをスーパー csv に渡すことができるかどうかも現在調査中です。非常に大きな遅延シーケンスを複数のコンシューマーに渡すときに Java ヒープ スペースの問題が発生したので、この解決策を採用することを少し心配しています。

別の解決策は、ファイルをローカルにダウンロードしてから、このファイルで 2 つのストリームを開くことです。これにより、ストリーミングの背後にある本来の動機がなくなります。つまり、データが到着し始めるとすぐにファイルの処理を開始できます。

最終的な解決策であり、他に何も機能しない場合にのみ検討する解決策は、解析された CSV と元の解析されていない行の両方を返す独自の CSV リーダーを実装することです。解析された CSV データの Java ハッシュと元の解析されていない行の両方を返すことができる非常に堅牢な CSV リーダーを使用している場合は、お知らせください。

ありがとう！

チェッカーのようなゲームを実装していますが、特定の構成ですべての正当な動きを列挙するシーケンスが必要です。

C# から直接翻訳された次の関数があります。

動作しますが、扱いにくく、「F# の方法」とは言えません。ましてや、ここで行っていることはパフォーマンスが最適化されていないのではないかと疑っています。

私が望むのは、「すべてのセルを反復する」、「このセルからのすべての有効な動きを反復する」の組み合わせを使用するものに「これを平坦化」することです。

そして、ここに私が組み合わせたい機能があります：

と

それを機能させるためのさまざまな試みの詳細は割愛します。どれも成功しなかったからです。しかし、長い話を短くするために、単純な MoveStruct を返す平坦化されたバージョンではなく、yield ごとに seq を返すイテレータを思い付くことができました。

AllCells と LegalMovesAround(x,y) を組み合わせる方法を知っている人はいますか?

よろしく、 アレックス

一部の言語（Haskell、Clojure、Schemeなど）の評価は遅延です。遅延評価の「セールスポイント」の1つは、無限のデータ構造です。何がそんなに素晴らしいのですか？無限のデータ構造を処理できることが明らかに有利である場合のいくつかの例は何ですか？

質問

1ストリームと遅延評価（40ポイント）

比較ソートには、n個の要素をソートする場合に少なくともO（n log n）の比較が必要であることがわかっています。一部の関数fについて、ソートされたリストの最初のf（n）要素のみが必要であるとしましょう。f（n）が漸近的にlog nよりも小さいことがわかっている場合、リスト全体をソートするのは無駄になります。ソートされたリストを表すストリームを返すレイジーソートを実装できます。ソートされたリストの先頭を取得するためにストリームにアクセスするたびに、リスト内で最小の要素が見つかります。これには線形時間がかかります。リストからf（n）要素を削除すると、O（nf（n））が使用されます。この質問では、次のデータ型の定義を使用します。いくつかのヘルパー関数も定義されています。

これらのストリームは必ずしも無限ではありませんが、無限である可能性があることに注意してください。

Q1.1（20ポイント）関数lazysort：int list-> intstream'を実装します。

整数のリストを受け取り、ソートされたリストを表すintストリームを返します。これは一定時間内に実行する必要があります。ストリーム'が強制されるたびに、EmptyまたはCons（v、s'）のいずれかが与えられます。短所の場合、vはソートされたリストの最小要素であり、s'は残りのソートされたリストを表すストリーム'です。力には線形時間がかかるはずです。例えば：

関連する定義

コードとして与えられるものは次のとおりです。

解決策への私の試み

私はintリストを取得してそれをintstreamに変換する次のことを試みました'：

ただし、forceを呼び出すと、最小要素は返されません。最小値を検索する必要がありますが、方法がわかりません...次のように挿入ソートを実行することを考えました。

しかし、私は最小値を検索し、リストをソートせずにストリームとして配置する必要があります...

どんな助けでもいただければ幸いです。

次の使用例を考えてみましょう:
2 つの db テーブルを並行して反復処理し、いずれかのテーブルの違いとギャップ/欠落レコードを見つけたいと考えています。1) テーブルの pk は Int ID フィールドです。2) テーブルは ID 順に読み込まれます。3) いずれかのテーブルからレコードが欠落している可能性があります (対応するシーケンス ギャップを伴う)。

遅延読み取りを使用して、各データベースに対して1回のパスでこれを行いたいと思います。(このプログラムの最初のバージョンでは、シーケンス オブジェクトとデータ リーダーを使用しています。残念ながら、各データベースに対して複数のパスを作成します)。

ペアごとのシーケンス処理を使用することを考え、反復内で Seq.skip を使用して、テーブル処理を同期させようとしました。ただし、I Seq.skip のオーバーヘッドが大きいため (フードの下で新しいシーケンスを作成する)、明らかにこれは非常に遅いため、大きなテーブル (たとえば 200k rec) では問題になる可能性があります。

これは一般的な設計パターン (さまざまなソースからの同時データ ストリームを比較する) であり、同様のプロジェクトへのフィードバック/コメント/リンクに関心があります。

コメントしたい人はいますか？

私はHaskellを学んでいて、次のコードに出くわしました。

それがどのように機能するかという点で、私は解析に少し問題があります。それはとてもきちんとしていて、これ以上何も必要ないことは理解していますが、Haskellが次のように書いたときにどのようにfibsを「埋める」ことができるかを理解したいと思います。

何か助けはありますか？

ありがとう！