Вариант треугольника Паскаля в Haskell - проблема с ленивой оценкой

Question

Чтобы решить некоторые проблемы, мне нужно вычислить вариант треугольника Паскаля, который определен так:

f(1,1) = 1, 
f(n,k) = f(n-1,k-1) + f(n-1,k) + 1 for 1 <= k < n, 
f(n,0) = 0,
f(n,n) = 2*f(n-1,n-1) + 1.

Для N данного я хочу эффективно получить N-Th Prine (f (n, 1). F (n, n)). Еще одно ограничение: f (n, k) должен быть -1, если это будет> = 2 ^ 32.

Моя реализация:

next :: [Int64] -> [Int64]
next list@(x:_) = x+1 : takeWhile (/= -1) (nextRec list)

nextRec (a:rest@(b:_)) = boundAdd a b : nextRec rest
nextRec [a] = [boundAdd a a]

boundAdd x y
    | x < 0 || y < 0 = -1
    | x + y + 1 >= limit = -1
    | otherwise = (x+y+1)

-- start shoud be [1]
fLine d start = until ((== d) . head) next start

Проблема: для очень большого количества я получаю переполнение стека. Есть ли способ заставить Haskell оценить весь список? Понятно, что каждая строка не может содержать больше элементов, чем верхняя граница, потому что они в конечном итоге становятся -1 и не хранятся, и каждая строка зависит только от предыдущего. Благодаря ленивой оценке только голова каждой строки вычисляется до тех пор, пока последняя строка не нуждается в втором элементе, и все сундуки по пути хранятся ... У меня очень эффективная реализация в C ++, но мне действительно интересно, если есть Способ сделать это в Haskell тоже.

Answer 1

Работает на меня: Какая реализация Haskell вы используете? Наивная программа для расчета этого треугольника отлично работает для меня в GHC 6.10.4. Я могу распечатать 1000 ряд просто отлично:

nextRow :: [Integer] -> [Integer]
nextRow row = 0 : [a + b + 1 | (a, b) <- zip row (tail row ++ [last row])]

tri = iterate nextRow [0]

main = putStrLn $ show $ tri !! 1000               -- print 1000th row

Я даже могу распечатать первые 10 номеров в строке 100000 без перенапряжения стека. Я не уверен, что идет не так для тебя. Глобальное имя tri Может держать весь треугольник результатов живым, но даже если это так, это кажется относительно безвредным.

Как заставить порядок оценки: Вы можете заставить TUKNS быть оцененным в определенном порядке с использованием функции Prelude seq (что является волшебной функцией, которая не может быть реализована с точки зрения других основных функций HASKELL). Если вы скажете Haskell для печати a `seq` b, Сначала он оценивает Thunk для a, затем оценивает и отпечатывает b.

Обратите внимание, что seq неглубоко: это Только Достаточно ли оценки для силы a больше не быть Thunk. Если a Тип кортежа, результат все еще может быть кортежом Teunks. Если это список, результат может быть мигание ячейки, имея Thunks для головы, так и для хвоста.

Похоже, вам не нужно делать это для такой простой проблемы; Несколько тысяч Tемнов не должны быть слишком много для любой разумной реализации. Но это будет так:

-- Evaluate a whole list of thunks before calculating `result`.
-- This returns `result`.
seqList :: [b] -> a -> a
seqList lst result = foldr seq result lst

-- Exactly the same as `nextRow`, but compute every element of `row`
-- before calculating any element of the next row.
nextRow' :: [Integer] -> [Integer]
nextRow' row = row `seqList` nextRow row

tri = iterate nextRow' [0]

Сгибание внутри seqList в основном расширяется в lst!!0 `seq` lst!!1 `seq` lst!!2 `seq` ... `seq` result.

Это намного медленнее для меня при печати только первые 10 элементов ряд 100 000. Я думаю, что это потому, что это требует вычисления 99 999 полных рядов треугольника.