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

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

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

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

triangularNumbers = scanl1 (+) [1..]

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

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

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

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

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


recursion haskell declaration corecursion
person Diego Martinoia    schedule 27.07.2015    source источник
comment
Вероятно, об этом уже спрашивали и отвечали раньше, но поиск рекурсивного определения вызывает только вопросы, связанные с рекурсией в алгоритмическом смысле.   -  person Diego Martinoia    schedule 27.07.2015
comment
это может помочь.   -  person Alec    schedule 27.07.2015
comment
Начните с понимания [1..].   -  person Eugene Sh.    schedule 27.07.2015
comment
@ЕвгенийШ. Я думаю, что понимаю ленивые бесконечные структуры, но я все еще не вижу, как саморекурсивное определение могло бы помочь, поскольку нет точки 0?   -  person Diego Martinoia    schedule 27.07.2015
comment
@DiegoMartinoia Можете ли вы определить для себя что-то похожее на [1..] (ну, это будет выглядеть не очень красиво, но вы можете назвать это естественным)? Он также использует (или может использовать) саморекурсию и немного проще, чем треугольные числа. Или даже бесконечный список. Конечно, без использования каких-либо предопределенных бесконечных списков.   -  person Eugene Sh.    schedule 27.07.2015
comment
@ЕвгенийШ. Исходя из Java, я вижу, как довольно легко реализовать такой бесконечный итератор. Но с итератором у вас есть внутреннее состояние (т.е. последнее число, к которому вы +1). Мне любопытно, а) как это внутреннее состояние на самом деле отображается на низком уровне после того, как haskell сжимает его, и б) как более сложный пример, такой как определение треугольника numb, которое я дал, становится хрустящим.   -  person Diego Martinoia    schedule 27.07.2015

Ответы (1)


arrow_upward
5
arrow_downward

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

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

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

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

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

person lodrik    schedule 27.07.2015
comment
Но где базовый случай в определении, которое я привел в качестве примера? Берет ли он 1 из [1..] и 0 из 0:tn ? - person Diego Martinoia; 27.07.2015
comment
Предположим, вы получаете доступ к первому элементу triag':, который можно вычислить напрямую, это 1+0, сумма первых элементов [1..] и 0:triag'. Теперь второе: это 2 + 1, где 2 — второй элемент из [1..], а 1 — второй элемент из 0:triag', т. е. первый элемент из triag', 1. Таким образом, любой элемент triag' определяется вашим решением и может быть вычислен как нужный. - person lodrik; 27.07.2015