Связывание узла - это решение проблемы круговых структур данных. В императивных языках вы создаете круговую структуру, сначала создавая некруглую структуру, а затем возвращаетесь и исправляете указатели, чтобы добавить округлость.
Скажем, вы хотели двухэлементный круговой список с элементами "0" и "1". Казалось бы, невозможно создать, потому что если вы создадите узел «1», а затем создадите узел «0», чтобы указать на него, вы не сможете затем вернуться и исправить узел «1», чтобы он указывал на узел «0». , Таким образом, у вас есть ситуация "курица и яйцо", когда оба узла должны существовать, прежде чем они смогут быть созданы.
Вот как вы это делаете на Хаскеле. Рассмотрим следующее значение:
alternates = x where
x = 0 : y
y = 1 : x
В не ленивом языке это будет бесконечный цикл из-за неоконченной рекурсии. Но в Haskell ленивый анализ делает правильную вещь: он генерирует двухэлементный круговой список.
Чтобы увидеть, как это работает на практике, подумайте о том, что происходит во время выполнения. Обычная «ленивая» реализация отложенной оценки представляет собой неоцененное выражение в виде структуры данных, содержащей указатель функции плюс аргументы, которые должны быть переданы функции. Когда это оценивается, thunk заменяется фактическим значением, чтобы будущие ссылки не вызывали функцию снова.
Когда вы берете первый элемент списка, «x» оценивается до значения (0, & y), где бит «& y» является указателем на значение «y». Поскольку «у» не было оценено, это в настоящее время гром. Когда вы берете второй элемент списка, компьютер переходит по ссылке от x к этому thunk и оценивает ее. Он оценивает (1, & x) или, другими словами, указатель на исходное значение 'x'. Итак, теперь у вас есть круглый список в памяти. Программисту не нужно исправлять обратные указатели, потому что ленивый механизм оценки сделает это за вас.