Как порядок передачи аргументов влияет на ленивые вычисления в Haskell?

Я пытался понять ленивую оценку в Haskell, и я понял ее в основном как оценку только тогда, когда вам нужно. Но при попытке эффективно реализовать фибоначчи я столкнулся с этим (странным?) поведением: Эта реализация:

--wrapper function used by both implementations
fib :: Int -> Int
fib x = if x < 0 then 0 else fib2 0 1 x

fib2 :: Int -> Int -> Int -> Int
fib2 x y 0 = x
fib2 x y z = fib2 y (x + y) (z - 1)

будет работать даже при вызове с

fib 20000000
> -70318061090422843

при замене переданных аргументов в рекурсивном вызове:

fib2 :: Int -> Int -> Int -> Int
fib2 x y 0 = x
fib2 x y z = fib2 (x + y) x (z - 1)

приводит к:

fib 20000000
>*** Exception: stack overflow

Почему бы мне не сказать компилятору, чтобы он с нетерпением выполнял первый пример? Почему второй пример не работает, а первый работает?

Для этого я использовал GHCi 8.0.1 в Windows 10.


recursion lazy-evaluation haskell
person Finn M    schedule 22.01.2017    source источник
comment
не уверен в этом случае (вероятно, первая версия разворачивается в основном в цикл, а вторая продолжает выделять кадры стека), см. stackoverflow.com/questions/13042353/ для аналогичного случая...   -  person mb21    schedule 22.01.2017
comment
У меня есть ощущение, что это должно быть связано с каррированием, поскольку пример с переполнением создает переходники в первом аргументе.   -  person chepner    schedule 22.01.2017
comment
Пожалуйста, включите информацию о версии ghci. У меня этого не происходит, вместо этого происходит сбой выделения (7.6.3).   -  person sdx23    schedule 22.01.2017
comment
хорошо, в моем случае оба уже TCO, не так ли? и в этих ответах даже специально сказано сделать аргумент накопления строгим, чего я не делаю для первого примера, и он все еще работает. Это практически корень моего замешательства.   -  person Finn M    schedule 22.01.2017

Ответы (1)


arrow_upward
6
arrow_downward

Во-первых, обратите внимание, что разница между двумя вашими версиями количественная, а не качественная. Первый вызовет переполнение стека при вводе 40000000, а второй успешно завершится при вводе 10000000. Похоже, вторая версия использует в два раза больше стека, чем первая.

По сути, причина в том, что если мы введем нотацию {n} для переходников, которые живут в аргументах x и y, ваша первая версия

fib2 {n} {n+1} 0 = {n}
fib2 {n} {n+1} z = let {n+2} = (+) {n} {n+1}    -- build a thunk
                    in fib2 {n+1} {n+2} (z - 1)

в то время как вторая версия делает

fib2 {n+1} {n} 0 = {n+1}
fib2 {n+1} {n} z = let {n+2} = (+) {n+1} {n}    -- build a thunk
                    in fib2 {n+2} {n+1} (z - 1)

Теперь рассмотрим, что произойдет, когда рекурсия fib2 завершится и наступит время вычислить {n} (или {n+1}; давайте просто проигнорируем эту разницу). Каждый преобразователь {0}, ..., {n} будет оцениваться только один раз в определенном порядке. Бывает, что (+) сначала оценивает свой левый аргумент, а затем правый аргумент. Для определенности возьмем просто n = 6. Оценка выглядит так

{6} = (+) {4} {5}
... {4} = (+) {2} {3}
... ... {2} = (+) {0} {1}
... ... ... {0} = 0
... ... ... {1} = 1
... ... {2} = 1
... ... {3} = (+) {1} {2}
... ... ... {1} = 1
... ... ... {2} = 1   -- we already calculated it
... ... {3} = 2
... {4} = 3
... {5} = ......

Стек никогда не станет глубже, чем n/2 уровней, так как мы сначала рекурсивно переходим от {n} к {n-2}, а когда нам нужно вычислить {n-1}, мы уже вычислили {n-2}.

Напротив, во второй версии мы сначала рекурсивно от {n} к {n-1}, поэтому стек будет иметь n уровней.

person Reid Barton    schedule 22.01.2017
comment
Да, имеет смысл на 100%, так что одного большого числа было недостаточно для проверки :P - person Finn M; 22.01.2017