私は最近、FPの中に入ってきました。だからもっと多くのものがあることは分かっている...余分なスペースを使わずにスタックを逆転させる方法... fp-style
とにかく、命令型プログラミングの古典的な問題は「余分なスペースを使わないで」スタックの逆転である。このソリューションは、通常、スタックの最下位に到達し、最下位の要素を取り出し、スタックを逆順に再構築する外部再帰に戻すために、ダブル再帰でコールスタックを使用します。私はハスケルで同じ問題を解決しようとしてきましたが、その言語で表現する方法を理解できません。ヒント？
EDITはい、スタックを使用すると、余分なスペースを使用してで、質問は、多くの場合、人々はものを考える方法を確認する試験と面接で使用されるトリックです。また、はい、私はものが不変であることを知っています。したがって、与えられたものと逆の複製スタックを作成することは明らかです。
はこの考えを表現する様々な方法があり
リストを逆にする唯一の効果的な方法
reverse = revApp []
revApp acc [] = acc
revApp acc (x:xs) = revApp (x:acc) xs
です（ところで、y'allのは、JKが...面接を失敗している）、それらはすべて基本的に同じコードになります。この考え方は、リストを前から後へ（スタック言語で、上から下へ）解体し、新しいものを前から後ろに構築することです。あなたは引数リストの最後の要素を見てきたまでは逆に、リストの最初の要素がどうなるかわからないので
は、前面から背面に完全に仕事をする方法はありません。あなたが望むなら、の結果リストの構造を前後に構築することができます。これはやや遅くなります。
lazyReverse xs = zipWith' (flip const) xs (reverse xs)
zipWith' _ [] _ = []
zipWith' f (x:xs) ~(y:ys) = f x y : zipWith' f xs ys
アイデアは（前後）が、逆にコピーからその値を取得するには、引数リストの構造をコピーすることによって、結果リストの構造を形成することです。これに関連するヒープ割り当てを避ける方法はないと思います。各テールを中間的に表すサンクは、スタックではなくヒープ上になければならないものへの参照をキャプチャします。
リストを正面に構築できないという特別な制約を課した場合、スタック内で何が起こるのでしょうか？ – Morpheu5
@ Morpheu5 Haskellでリストを作成するには、小さなリストに要素を追加するだけです。 「前に戻る」とは、元のリストの要素の順序を指します。 –
@ Morpheu5もう一度見てください。この答えに掲示されたコードはスタックをとり、空ではない間に、スタックの先頭（ '（x：xs）'ビット）から要素を再帰的にポップし、それを新しいスタックにプッシュします'（x：acc）'ビット）。これは、スタックADTによって公開されているのと同じメソッドを正確に使用します。 – liminalisht
コールスタックを使用することは、実際には「余分なスペースを使用しない」ことではないことに注意してください。 –
「余分なスペース」とは何ですか？ Haskellのリストは不変です。逆の場合は、新しいものを作成する必要があります。あなたがスーパーナイーブなO（n^2）の逆を書くのでない限り、あなたはすでに良い形になっています。標準のO（n）ソリューションでは、すでに割り当てが最小限に抑えられています。 – Carl
O（1）スペースFPスタイルのスタックを反転することはできません。 FPでは事は不変です。再帰にはスペースが必要なため、命令型ソリューションではO（n）スペースも使用されます。 –