Самоссылочные структуры данных в Лиспе / Схеме

Question

Есть ли способ построить само-ссылочную структуру данных (скажем, граф с циклами) в lisp или схеме? Я никогда не думал об этом раньше, но, играя вокруг, я не могу найти простой способ сделать его из-за отсутствия способа сделать разрушительную модификацию. Является ли это просто существенным недостатком функциональных языков, и если да, то как насчет ленивых функциональных языков, таких как haskell?

Answer 1

В Common Lisp вы можете изменять содержимое списка, содержимое массива, слоты экземпляров CLOS и т. Д.

Common Lisp также позволяет читать и записывать циклические структуры данных. Используйте

? (setf *print-circle* t)
T

; a list of two symbols: (foo bar)

? (defvar *ex1* (list 'foo 'bar))
*EX1*

; now let the first list element point to the list,
; Common Lisp prints the circular list

? (setf (first *ex1*) *ex1*)
#1=(#1# BAR)

; one can also read such a list

? '#1=(#1# BAR)
#1=(#1# BAR)

; What is the first element? The list itself

? (first '#1=(#1# BAR))
#1=(#1# BAR)
? 

Так называемые pure Функциональные языки программирования не допускают побочных эффектов. Большинство диалектов Лиспа не чисты. Они допускают побочные эффекты и позволяют изменять структуры данных.

Подробнее об этом см. Во вводных книгах по Lisp.

Answer 2

Common Lisp поддерживает модификацию структур данных с setf.

Вы можете построить круговую структуру данных в Haskell, связав узел .

Answer 3

В Схеме вы можете легко это сделать с помощью set!, set-car! и set-cdr! (и всего остального, оканчивающегося на удар ('!'), что указывает на изменение):

(let ((x '(1 2 3)))
  (set-car! x x)
  ; x is now the list (x 2 3), with the first element referring to itself
  )

Answer 4

1. Вам не нужно «деструктивное изменение» для построения самоссылочных структур данных; например, в Common Lisp '#1=(#1#) является конс-ячейкой, которая содержит себя.

2. Scheme и Lisp способны вносить деструктивные изменения: вы можете построить круглые минусы выше, например, так: (let ((x (cons nil nil))) (rplaca x x) x)

Можете ли вы сообщить нам, какой материал вы используете при изучении Lisp / Scheme? Я составляю список целей для наших черных вертолетов; это распространение дезинформации о Лиспе и Схеме должно быть остановлено.

Answer 5

Я одобрил очевидные методы Схемы; этот ответ касается только Haskell.

В Haskell вы можете сделать это чисто функционально, используя let, что считается хорошим стилем. Хорошим примером является преобразование регулярного выражения в NFA. Вы также можете сделать это обязательно, используя IORef s, который считается плохим стилем, поскольку он заставляет весь ваш код в монаду ввода-вывода.

В общем, ленивая оценка Хаскелла поддается прекрасным функциональным реализациям как циклических, так и бесконечных структур данных. В любой сложной let привязке все связанные вещи могут использоваться во всех определениях. Например, преобразование конкретного конечного автомата в Haskell очень просто, независимо от того, сколько циклов у него может быть.

Answer 6

Мало того, что это возможно, это довольно центрально для Common Lisp Object System: стандарт-класс сам по себе является экземпляром!

Answer 7

Да, и они могут быть полезны. Один из моих профессоров в колледже создал тип Схемы, который он назвал «Номера Медузы». Это были числа с плавающей запятой произвольной точности, которые могли включать повторяющиеся десятичные числа. У него была функция:

(create-medusa numerator denominator) ; or some such

, который создал Число Медузы, которое представляло рациональное. В результате:

(define one-third (create-medusa 1 3))
one-third => ; scheme hangs - when you look at a medusa number you turn to stone
(add-medusa one-third (add-medusa one-third one-third)) => 1

Как уже было сказано, это делается с разумным применением автомобиля set-car! и set-cdr!

Answer 8

Связывание узла (круговые структуры данных в Haskell) в StackOverflow

См. Также страницу Wiki на Haskell: Завязывание узла

Answer 9

CLOS пример:

(defclass node ()
  ((child :accessor node-child :initarg :child)))

(defun make-node-cycle ()
  (let* ((node1 (make-instance 'node))
         (node2 (make-instance 'node :child node1)))
     (setf (node-child node1) node2)))

Answer 10

Я наткнулся на этот вопрос, когда искал "СХЕМА LISP КРУГЛЫХ СПИСКОВ".

Вот как я могу сделать один (в схеме STk):

Сначала составьте список

(define a '(1 2 3))

На данный момент STk считает a списком.

(list? a)
> #t

Затем перейдите к последнему элементу (в данном случае 3) и замените cdr, который в настоящее время содержит nil, указателем на себя.

(set-cdr! (cdr ( cdr a)) a)

Теперь STk считает, что это не список.

(list? a)
> #f

(Как это получается?)

Теперь, если вы напечатаете a, вы найдете бесконечно длинный список (1 2 3 1 2 3 1 2 ... и вам нужно будет убить программу. В Stk вы можете control-z или control-\, чтобы выйти.

Но для чего нужны круглые списки?

Я могу вспомнить неясные примеры, связанные с арифметикой по модулю, такие как круговой список дней недели (M T W T F S S M T W ...) или круговой список целых чисел, представленных 3 битами (0 1 2 3 4 5 6 7 0 1 2 3 4 5 ..).

Есть ли примеры из реальной жизни?