Haskell - Cスタックのオーバーフロー

Question

私はちょうどハスケルに導入されているので、私はその言語でコードする方法ではあまり実践されていないので、重複している場合は申し訳ありませんが、言語で書かれています。

与えられた値を超えない正の偶数の合計をとるアルゴリズムを作成しようとしています。私はコードを記述しようとしましたが、Cスタックオーバーフローエラーが発生しました。ここで

は私のコードです：

sumint :: Int -> Int 
sumint x 
    | x==0 = 0 
    | x==1 = 1 
    | (x `mod` 2 == 0) && (x >= 2) = x + (sumint x-2) 
    | (x `mod` 2 /= 0) && (x >= 1) = x + (sumint x-1) 

は、私はこのエラーを取得するために、間違ったつもりはどこ？

Answer 1

初期誤差：あなたのコードのステップ無限再帰

：

sumint :: Int -> Int 

ねえ、型シグネチャ。あなたは揺れる。

sumint x 
    | x==0 = 0 

ベースケース、クール。

| x==1 = 1 

まったく必要ない場合。 OK、確かに...を除いて。 1はそうではありませんなぜ私たちは合計でそれを含めるのですか？ゼロ（または完全に削除）にする必要があります。

| (x `mod` 2 == 0) && (x >= 2) = x + (sumint x-2) 

問題の肉はこちらです。 1.Xは偶数です。 2. Xは正の値です。結果はx + (sumint x) - 2いいえ！

• エラー1：通知関数アプリケーションが演算子よりも高い値をバインドするため、x + sumint (x-2)である必要があります。

これは、スタックオーバーフローの原因です。 sumint 2 == 2 + (sumint 2) - 2 + (sumint 2) -2 + (sumint 2) -2 + ...、yay無限再帰。

| (x `mod` 2 /= 0) && (x >= 1) = x + (sumint x-1) 

別のケース...オッズ...ポジティブ...しかし、なぜxで追加していますか？あなたは、オッズではなく、エヴェンスを加えたいと思う。だから、同時に上記の問題を修正する我々が得る：

• エラー2：あなたはxが奇数であるかを決定した場合、xに追加しないでください。ちょうどsumint (x-1)を使用してください。

あなたは不安です。 xが正でない場合はどうなりますか？あなたは（別の）ケースが必要です。

| otherwise = 0 

次の問題：なし蓄積

問題は、今あなたが大規模なサンク（未評価の計算を）構築の代わりに、あなたが進むにつれてその結果を蓄積することにより、一定の間隔で動作しているです。私たちが言う、のためにあなたの計算を展開する場合は、6に注意してください、私たちが得る：

sumint x = go x 0 
where 
    go n accumulator 
     | n <= 0 = accumulator 
     | odd n  = go (n-1) accumulator 
     | otherwise = go (n-2) (accumulator + n) 

：

sumint 6 = 6 + sumint (6-2) 
     = 6 + 4 + sumint (4-2) 
     = 6 + 4 + 2 + sumint (2-2) 
     = 6 + 4 + 2 + 0 

あなたは本当にそれのようなアキュムレータに渡すために良いだろう、すべてのそれらの追加は分離しておく必要はありません

サイドノート：他のstackoverflow市民はアキュムレータを厳密にすることに言及しているかもしれませんが、それは良いフォームです。私は、ここでの議論で現在の尋問者の気を散らしたくない。最適化を使用して通知、-O2、十分です。

上記のすべてのソリューションはかなり冗長で

慣用的なソリューション。関数とアキュムレータを使用してリストを反復する一般的な操作は、foldのタイプです。 Foldは、関数型プログラミングでよく使われる高度に最適化された構造トラバーサルの1つです。この場合、「厳密な左折りたたみ」が典型的な候補（Data.Listから）です。つまり、foldl' 'であり、慣例による素数（'）は、厳密にはlが残っていることを意味します。

sumint n = foldl' (+) 0 [val | val <- [0..n], even val] 

ここでは、合計を得るためにリストを折りたたんでいます。関心のあるリストを作成するには、リストの理解度を使用しました。まず、0..nの値を列挙し、述語evenに合致しない値はスキップします。

私たちは、これをさらにクリーンアップし、2によって手順は、このように私たちにあなたが望むだけ追いつい与えることsum機能とリスト内包表記を使って、それを改善することができます修正のための

sumint n = sum [0,2..n] 

Answer 2

オペレータの優先順位の問題です。ハスケルでは、関数のアプリケーションが可能な限り高い優先順位を持っています。したがって、sumint x - 2と書くと、sumint (x-2)と解釈されても、Haskellはそれを(sumint x) - 2と解釈しています。したがって、sumint xを直接sumint xで定義しようとしています。スタックオーバーフローが発生するまで、再帰的な関数呼び出しを積み重ねるだけです。関数適用の前に減算を評価する場合は、明示的なかっこを追加する必要があります。