Добрый день всем.

Пытаюсь разобраться в том, как программы на Хаскелле используют память и наткнулся на вот такой непонятный эффект. Есть такая простая программа:

sum1 :: Integer -> Integer -> Integer -> Integer
sum1 a b acc -- | a `seq` b `seq` False = undefined
             | a < b = sum1 (a+1) b (acc+a)
             | otherwise = acc


main = print $ (sum1 0 1000000 0)

Если выполнять её как она написана (с закомментированной строчкой), то она выполняется за O(1) памяти, всего выделяя за время работы O(N). Хотя, казалось бы, она должна использовать O(N) памяти, поскольку функция sum1 нестрогая по acc, и, следовательно, должна создать цепочку недовычисленных сумм (как foldl). Но это ладно, может анализатор строгости работает.

Непонятное происходит, если строчку с seq раскомментировать. По-моему, функция как была строгой по a и b, так и остается. Хвостовая рекурсия тоже остается. Ан нет, происходит переполнение стека. Как так?

Если Integer заменить на Int, то получается все нормально — работает за O(1), выделяя тоже O(1) в обоих случаях. Тут все понятно.

Разъясните, что тут происходит?

Спасибо за внимание.