Объяснение "привязка узла"

Ответ 1

Связывание узла - это решение проблемы круговых структур данных. В императивных языках вы создаете круговую структуру, сначала создавая некругулярную структуру, а затем возвращаетесь назад и фиксируете указатели, чтобы добавить округлость.

Предположим, вам нужен двухэлементный круговой список с элементами "0" и "1" . Казалось бы, невозможно построить, потому что если вы создаете "1" node, а затем создаете "0" node, чтобы указать на него, вы не можете вернуться и исправить "1" node, чтобы указать назад на "0" node. Таким образом, у вас есть ситуация с курицей и яйцом, где оба узла должны существовать до того, как они могут быть созданы.

Вот как вы это делаете в Haskell. Рассмотрим следующее значение:

alternates = x where
   x = 0 : y
   y = 1 : x

На неязычном языке это будет бесконечный цикл из-за разворачиваемой рекурсии. Но в Haskell ленивая оценка делает правильную вещь: она генерирует двухэлементный круговой список.

Чтобы узнать, как это работает на практике, подумайте о том, что происходит во время выполнения. Обычная "тонкая" реализация ленивой оценки представляет собой неоценимое выражение как структуру данных, содержащую указатель на функцию плюс аргументы, которые должны быть переданы функции. Когда это оценивается, thunk заменяется фактическим значением, так что будущие ссылки не должны снова вызывать функцию.

Когда вы берете первый элемент списка "x", оценивается до значения (0, & y), где бит "& y" является указателем на значение "y". Так как 'y' не оценивается, это в настоящее время thunk. Когда вы берете второй элемент списка, компьютер следует по ссылке от x до этого thunk и оценивает его. Он оценивает (1, & x), или, другими словами, указатель возвращается к исходному значению "x". Итак, теперь у вас есть круговой список, сидящий в памяти. Программисту не нужно исправлять обратные указатели, потому что ленивый механизм оценки делает это за вас.

Ответ 2

Это не совсем то, о чем вы просили, и это напрямую не связано с Haskell, но бумага Брюса МакАдама Что об Wraps It Up идет в этом тема в значительной степени и глубине. Основная идея Bruce заключается в том, чтобы использовать явный узел привязки, называемый WRAP, вместо привязки неявной, которая выполняется автоматически в Haskell, OCaml и некоторых других языках. В документе есть много <сильных > развлекательных примеров, и если вы заинтересованы в узловязании, я думаю, вы уйдете с гораздо лучшим чувством к процессу.