Космическая утечка только в некоторых случаях в интерпретаторе GHC при выполнении: concat <some list>!! N

Я определяю собственную версию concat, myConcat:

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)

Если я выполняю myConcat <some huge list> !! n в интерпретаторе GHC, он крадет мою память со скоростью 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.

Ответы

Ответ 1

Здесь речь идет о строгости. Оценка в Haskell не является строгой, поэтому вычисления обычно выполняются только в том случае, если их результаты действительно необходимы. Вместо этого создается так называемый "тон", который представляет собой еще не выполненное вычисление.

В некоторых случаях компилятор может, однако, обнаружить, что результат вычисления будет необходим в любом случае и, следовательно, заменяет создание thunks фактическим вычислением.

Haskell Wiki, вероятно, объясняет это лучше.

Чтобы исправить вашу функцию myConcat, вы должны убедиться, что она не создает миллионы thunks, вручную принудительно строгая оценка. Один (не очень красивый) способ сделать это может быть:

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