Как (со) рекурсивное определение работает в Haskell?

Question

Я играю с языком, чтобы начать учиться, и я озадачен неуверенностью в том, как работает рекурсивное определение.

Например, давайте возьмем последовательность треугольных чисел (TN n = sum [1..n])

Решение было предоставлено:

triangularNumbers = scanl1 (+) [1..]

Все идет нормально.

Но решение, которое я нашел, было:

triangularNumbers = zipWith (+) [1..] $ 0 : triangularNumbers

Что тоже правильно.

Теперь мой вопрос: как это переводится на реализацию более низкого уровня? Что происходит именно за сценой, когда встречается такое рекурсивное определение?

Answer 1

Вот простая рекурсивная функция, которая дает вам n-е треугольное число:

triag 0 = 0
triag n = n + triag (n-1)

Ваше решение triag' = zipWith (+) [1..] $ 0 : triag' это нечто более причудливое: это corecursive ( щелчок, щелчок). Вместо того, чтобы вычислять n-е число, уменьшая его до значения меньших входных данных, вы определяете всю бесконечную последовательность треугольных чисел путем рекурсивного указания следующего значения с учетом начального сегмента.

Как Haskell справляется с такой corecursion? Когда он встречает ваше определение, вычисления фактически не выполняются, они откладываются до тех пор, пока не потребуются результаты для дальнейших вычислений. Когда вы получаете доступ к определенному элементу вашего списка triag'Haskell начинает вычислять элементы списка на основе определения, вплоть до элемента, к которому осуществляется доступ. Для более подробной информации я нашел эту статью о ленивой оценке полезной. Таким образом, ленивая оценка - это здорово, если только вам не нужно прогнозировать использование памяти.

Вот аналогичный вопрос SO с пошаговым объяснением оценки fibs = 0 : 1 : zipWith (+) fibs (tail fibs), corecursive определение последовательности Фибоначчи.