問題タブ [tail-recursion]

より機能的なスタイルで書き直そうとしている変更可能なスカラ コードがいくつかあります。これはかなり複雑なコードなので、少しずつリファクタリングしようとしています。私の最初の考えはこれでした：

コード全体にまだ副作用が混在しているため、これはまったく機能していないように見えました。私の2番目の考えはこれでした：

少なくとも、機能的な値生成コードを変更可能な値処理コードから分離したため、これは私にとってより良い解決策のように思えました。ただし、実際には保存する必要のない大きなリストを生成しているため、これはメモリ効率が大幅に低下します。

これにより、3つの選択肢が残ります。

1. 末尾再帰関数を作成し、弾丸をかじって値処理コードをリファクタリングする
2. 遅延リストを使用します。これはメモリに敏感なアプリではありません (ただし、パフォーマンスには敏感です)。
3. 新しいアプローチを思いつく。

私が本当に欲しいのは、処理後に値を破棄できる遅延評価シーケンスだと思います。助言がありますか？

VS2010を使用してF＃を学び始めたばかりです。以下は、フィボナッチ数列を生成する最初の試みです。私がやろうとしているのは、400未満のすべての数字のリストを作成することです。

私の最初の問題は、最後のステートメントで、最後の行に「式のこのポイントまたはそれ以前の不完全な構造化構造」というエラーメッセージが表示されることです。ここで何が間違っているのかわかりません。

これは（c ++ / C＃プログラマーから）かなり効率的な方法でリストを作成するための明白な方法のようですが、私がf＃についてほとんど知らないことから、これはプログラムを実行する正しい方法ではないようです。 。私はこの気持ちで正しいですか？

このような単純な追加関数（F＃）：

関数は末尾再帰ではないため、sが大きくなるとクラッシュします。F＃の標準の追加関数は大きなリストではクラッシュしないため、別の方法で実装する必要があることに気付きました。だから私は疑問に思いました：appendの末尾再帰的定義はどのように見えますか？私はこのようなものを思いついた：

これは機能しますが、かなり奇妙に見えます。よりエレガントな定義はありますか？

なぜだろうか

スタックオーバーフローエラーは発生しません。プレリュードの++は単純で、末尾再帰ではないようです。

編集：当初、この問題は前奏曲で++が定義されている方法、特に書き換えルールに関係していると思いました。したがって、質問は以下のように続きました。議論は私にこれが事実ではないことを示しました。遅延評価効果によってコードがスタックオーバーフローなしで実行されるようになったと思いますが、その方法はよくわかりません。

これだけで、スタックオーバーフローが発生するはずですよね？だから私はそれがおそらく++の定義に従うghc魔法と関係があると思います：

{-＃ルール "++" [〜1] forallxsys。xs ++ ys = augment（\ cn-> foldr cn xs）ys＃-}

*それはスタックオーバーフローを回避するのに役立ちますか？誰かがこのコードで何が起こっているのかについてのヒントを提供できますか？**

最近はF#を勉強中。私はさまざまな方法で問題を解決しようとします。このような：

V2 と V3 の結果は同じはずだと思いました。しかし、私は以下の結果を得ます：

V2 と V3 の結果が異なるのはなぜですか?

F＃を学習するためのコードを記述します。次に例を示します。

私はそれがうまくいくことをとても嬉しく思います！

私は完全に再帰の初心者です

再帰は素晴らしいことです。

findPrimesは効率的ではないと思います。

可能であれば、誰かがfindPrimesを末尾再帰にリファクタリングするのを手伝ってくれますか？

ところで、最初のn個の素数を見つけるためのより効率的な方法はありますか？

IL命令を見たいのです.tailが、私が書いてきた末尾呼び出しを使用した単純な再帰関数は、明らかにループに最適化されています。Reflectorでループがどのように見えるか完全にはわからないので、私は実際にこれを推測しています。しかし、私は間違いなく.tailオペコードを見ていません。プロジェクトのプロパティで[末尾呼び出しの生成]をオンにしました。また、Reflectorでデバッグビルドとリリースビルドの両方を試しました。

私が使用したコードは、ChrisSmithによるProgrammingF＃、190ページからのものです。

誰かが実際に生成するいくつかの簡単なF＃コードを提案できます.tailか？

Clojure での Sieve of Erathosthene の実装を次に示します (ストリームに関する SICP のレッスンに基づく)。

さて、最初の 100 個の素数を取れば問題ありません。

しかし、最初の 1000 個の素数を取ろうとすると、スタック オーバーフローのためにプログラムが中断します。関数ふるいを何らかの方法で変更して末尾再帰になり、それでもアルゴリズムの「ストリームネス」を維持することが可能かどうか疑問に思っていますか?

助けて？

タイプの値はどのようにできますか：

機能的な方法で生成されたそれ自体を参照する値がありますか？

Treeを適切に定義するには、次のPythonコードで結果の値がxに等しくなる必要があります。

編集：明らかにもっと説明が必要です。私はF＃と関数型プログラミングを学ぼうとしているので、以前にプログラミングしたカバーツリーを他の言語で実装することにしました。ここで重要なのは、各レベルのポイントが下のレベルのポイントのサブセットであるということです。構造は概念的にレベル無限大になります。

命令型言語では、ノードにはそれ自体を含む子のリストがあります。これはF＃で必須に実行できることを私は知っています。いいえ、カバーツリーアルゴリズムが与えられた場合、無限ループは作成されません。

最初にいくつかの背景。私は現在、モナディックパーサーコンビネーターについていくつかのことを学んでいます。この論文（p。16-17）から「chainl1」関数を転送しようとしたときに、次の解決策を思いつきました。

大きな入力で関数をテストしたところ、StackOverflowExceptionが発生しました。今、私は疑問に思っていますが、末尾再帰を使用するような方法で、何らかの計算式を使用する再帰関数を書き直すことは可能ですか？

計算式を展開すると、一般的にどのようにできるのかわかりません。