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