GHCインタプリタでスペースリークが発生するのは、concat !! nは

Question

私はmyConcat、concatの私の独自のバージョンを定義します。

module Eh where 

myConcat []   = [] 
myConcat ([]:os)  = myConcat os 
myConcat ((x:xs):os) = x : myConcat (xs:os) 

(!!!) :: [a] -> Int -> a 
xs  !!! n | n < 0 = error "negative index" 
[]  !!! _   = error "index too large" 
(x:_) !!! 0   = x 
(_:xs) !!! n   = xs !!! (n-1) 

私はGHCインタプリタでmyConcat <some huge list> !! nをすれば、それは300メガバイト/秒で私の記憶を盗む、と私はそれがOOMを召喚することができます前に、それを殺さなければなりませんキラー。ここでは、私はEhを "解釈済み"として読み込みます。読み込む前にコンパイルしません。

 
code run in the GHC interpreter  space leak? 
myConcat (repeat [1,2,3,4]) !! (10^8) Yes 
concat (repeat [1,2,3,4]) !! (10^8) No 
myConcat (repeat [1,2,3,4]) !!! (10^8) No 
concat (repeat [1,2,3,4]) !!! (10^8) No 

は、今私はEh（ghc --make -O2 Eh.hs）をコンパイルした場合、その後、インタプリタでそれをロードし、それらのどれもスペースリーク、これらのテストを再実行します。インタプリタで実行するのではなく、各テストケースをコンパイルするのと同じです。

何が起こっているのですか？

---

私はGHC 6.12.3を実行しています。

Answer 1

ここでの問題は厳密さです。ハスケルでの評価は厳密ではないので、計算は通常、その結果が本当に必要な場合にのみ実行されます。代わりに、実行されていない計算を表すいわゆるサンクが作成されます。

しかしながら、コンパイラは、とにかく計算の結果が必要となることを検出することができるため、実際の計算によってサンクの作成を置き換えます。

Haskell Wikiはおそらくこれをよりよく説明します。

myConcat機能を修正するには、手動で厳密な評価を強制して何百万というサンクを作成しないようにする必要があります。

myConcat []   = [] 
myConcat ([]:os)  = myConcat os 
myConcat ((x:xs):os) = ((:) $! x) myConcat (xs:os)