Самореферентные структуры данных в Lisp/Схема

Ответ 1

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

Общий 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)
? 

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

Подробнее см. Lisp книги для ввода.

Ответ 2

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

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

Ответ 3

Общий Lisp поддерживает модификацию структур данных с помощью setf.

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

Ответ 4

• Вам не нужна "деструктивная модификация" для построения самореферентных структур данных; например, в Common Lisp, '#1=(#1#) является cons-cell, которая содержит себя.

• Схема и Lisp способны совершать разрушительные модификации: вы можете построить круговые минусы выше, например: (let ((x (cons nil nil))) (rplaca x x) x)

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

Ответ 5

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

(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!

Ответ 6

Не только это возможно, но и довольно распространено в Common Lisp Object System: standard-class - это сам экземпляр!

Ответ 7

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

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

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

Ответ 8

Пример 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)))

Ответ 9

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

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

Ответ 10

Хмм, самореляционные структуры данных в Lisp/Scheme, а потоки SICP не упоминаются? Ну, чтобы обобщить, потоки == лениво оцененный список. Это может быть именно та ссылка, которую вы намеревались, но это своего рода самостоятельная ссылка.

Итак, cons-stream в SICP является синтаксисом, который задерживает оценку его аргументов. (cons-stream a b) будет немедленно возвращаться без оценки a или b и будет оценивать только a или b при вызове car-stream или cdr-stream

Из SICP, http://mitpress.mit.edu/sicp/full-text/sicp/book/node71.html: >

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))

В этом определении говорится, что fibs является поток, начинающийся с 0 и 1, такой что остальная часть потока может быть генерируется путем добавления фиблей к себе сдвинуто на одно место:

В этом случае "fibs" присваивается объект, значение которого определяется лениво в терминах "fibs"

Почти забыл упомянуть, ленивые потоки живут в общедоступных библиотеках SRFI-40 или SRFI-41. Один из этих двух должен быть доступен на самых популярных схемах, я думаю,

Ответ 11

Я наткнулся на этот вопрос, ища "ЦИРКУЛЯРНЫЕ ЛИСТЫ LISP СХЕМА".

Вот как я могу сделать это (в STk Scheme):

Сначала создайте список

(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 ..).

Есть ли реальные примеры?