Объяснение «завязывания узла»

Читая материал, связанный с Хаскеллом, я иногда сталкиваюсь с выражением «завязывать узлы», думаю, я понимаю, что он делает, но не как .

Итак, есть ли хорошие, простые и простые для понимания объяснения этой концепции?

10.12.2008 23:14:07
Проверьте здесь .
EBGreen 10.12.2008 23:18:13
Или здесь . :)
Alexey 12.12.2015 10:28:44
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'. Итак, теперь у вас есть круглый список в памяти. Программисту не нужно исправлять обратные указатели, потому что ленивый механизм оценки сделает это за вас.

46
26.12.2008 16:35:08
Это было легко! Я думаю, что следующий вопрос: как вставить что-то в двусвязный список в Haskell?
Alexey 12.12.2015 10:47:59
@Alexey - Основной ответ таков: вы делаете копию всего списка с добавленным вставленным элементом. Структуры данных на Haskell не являются изменяемыми, поэтому мы не очень часто используем списки с двойной связью.
Paul Johnson 12.12.2015 11:01:11
Я нашел некоторые обсуждения, беседы и статьи на эту тему в Интернете, и я пытаюсь извлечь уроки из них, но ваш основной ответ кажется мне неубедительным: если вы копируете один узел двусвязного списка в своей реализации, вы копируете весь список, и, следовательно, вы не можете ничего добавить к нему.
Alexey 12.12.2015 12:11:45
Алексей, я имею в виду, что вы должны создать новый список, который будет содержать как старые элементы, так и новый.
Paul Johnson 12.12.2015 13:45:51
@ Алексей, ты наверное не можешь. (если не будет какого-то действительно странного крайнего случая, о котором я не думаю) Ну, по крайней мере, не в чистом коде, делать такие вещи в ST или IO или подобном не было бы очень сложно.
semicolon 17.09.2016 00:42:51

Это не совсем то, о чем вы просили, и это не имеет прямого отношения к Хаскеллу, но статья Брюса МакАдама « О том, как это происходит» подробно раскрывает эту тему. Основная идея Брюса - использовать явный оператор связывания узлов, называемый WRAP, вместо неявного связывания узлов, которое выполняется автоматически в Haskell, OCaml и некоторых других языках. В газете много интересных примеров , и, если вы заинтересованы в завязывании узлов, я думаю, вы почувствуете себя гораздо лучше.

11
18.08.2011 18:49:38