Haskell：stackoverflowを使わずに多数の関数を繰り返す

Question

ハスケルの初心者として、私は関数（例えば、ロジスティックマップ）を何回も繰り返そうとしています。命令型言語ではこれは単純なループになりますが、Haskellではスタックオーバーフローが発生します。コードが動作の反復の数が少ないため

main = print $ iter 1000000 

f x = 4.0*x*(1.0-x) 

iter :: Int -> Double 
iter 0 = 0.3 
iter n = f $ iter (n-1) 

を、しかし、百万回の反復のために私はスタック領域のオーバーフローを得る：例えば、このコードを取り、これが起こるんなぜ私が理解できない

Stack space overflow: current size 8388608 bytes. 
Use `+RTS -Ksize -RTS' to increase it. 

。尾の再帰はここでうまくいくはずです。 問題は遅延評価です。 $!またはseqをさまざまな位置に挿入することで、厳密な評価を強制するいくつかの方法を試しましたが、成功しませんでした。

関数を膨大な回数繰り返すハスケルの方法は何でしょうか？

私は、関連記事からの提案を試してみました：hereまたはhereが、私は常に多数の反復、例えば、main = print $ iterate f 0.3 !! 1000000のためにStackOverflowになってしまいました。

Answer 1

問題は、あなたの定義

iter :: Int -> Double 
iter 0 = 0.3 
iter n = f $ iter (n-1) 

が間違った方向に評価しようとする

ということです。いくつかの手順のためにそれを展開、我々はiter 0へiter 1000000から

iter n = f (iter (n-1)) 
     = f (f (iter (n-2))) 
     = f (f (f (iter (n-3)))) 
     ... 

とコールスタック全体を取得何が評価される前に構築する必要があります。それは厳密な言葉で同じでしょう。あなたは評価の一部が反復する前に起こるようにそれを整理しなければなりません。場合には、コンパイラは、すでにそれらを追加しない - - それはスタックを消費することなくスムーズになります通常の方法は、次に

iter n = go n 0.3 
    where 
    go 0 x = x 
    go k x = go (k-1) (f x) 

正格性注釈を追加するように、蓄積パラメータを持つことです。

iterateのバリアントには、iterと同じ問題があります。コールスタックは、自分の場合と同じように、内部ではなく内部に組み込まれています。しかしiterate以来、コールスタックインサイドアウト、iterateの厳しいバージョン（またはそれ以前の反復が前に強制されている消費パターンが）問題を解決し、

iterate' :: (a -> a) -> a -> [a] 
iterate' f x = x `seq` (x : iterate' f (f x)) 

は問題なくiterate' f 0.3 !! 1000000を算出し、構築します。