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

Question

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

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

Решение, предложенное было:

triangularNumbers = scanl1 (+) [1..] 

До сих пор, так хорошо.

Но решение я придумал было:

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

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

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

Answer 1

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

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

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

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

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