6

n までのすべての奇数を合計するプログラムを実行しています。

oddSum' n result | n==0 = result
                 | otherwise = oddSum' (n-1) ((mod n 2)*(n)+result)

oddSum n = oddSum' n 0

入力に対して 2 つのエラーが発生します (以下に示します)。末尾再帰を使用しているのに、スタック オーバーフローが発生するのはなぜですか? （注：UbuntuでHugsを使用しています）

oddSum 20000 ERROR - コントロール スタック オーバーフロー

oddSum 100000 ERROR - ガベージ コレクションで十分なスペースを再利用できません

4

2 に答える 2

8 
 oddSum 3
 oddSum 2 ((2 mod 2)*2 + 3)
 oddSum 1 ((1 mod 2)*1 + ((2 mod 2)*2 + 3))

変数に巨大なサンクを構築していresultます。これを評価すると、すべての計算を一度に実行する必要があり、スタックがオーバーフローします。たとえば、加算を実行するには、最初にオペランドを評価し、オペランド内の加算のオペランドを評価する必要があるためです。

おっと、サンクが大きくなりすぎると、ヒープ オーバーフローが発生します。

使ってみて

result `seq` ((mod n 2) * n + result)

再帰で。

于 2013-02-07T11:37:08.327 に答える
8

まず、Hugs を使用しないでください。サポートされていません。GHC を最適化すると、このようなものがタイトで効率的なループにコンパイルされる可能性があります (それでも、コードはうまくいきません)。

非厳密なアキュムレータは、常に巨大なサンクを構築するリスクをもたらします。1 つの解決策は、厳密にすることです。

{-# LANGUAGE BangPatterns   #-}

oddSum' n !acc | n==0       = acc
               | otherwise  = oddSum' (n-1) $ (n`mod`2)*n + acc

もちろん、これは慣用的なものではありません。末尾再帰関数を明示的に記述するのは面倒であり、Haskell ではやや嫌われています。この種のほとんどのことは、次のようなライブラリ関数でうまく実行できます。

oddSum n = sum [1, 3 .. n]

...残念ながら、一定のスペースでも確実に機能しません。それは折り畳みの厳密なバージョンで動作します（これsumは単なる特殊化です）、

import Data.List
oddSum n = foldl' (+) 0 [1, 3 .. n]
于 2013-02-07T11:41:12.953 に答える