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

В языке 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)
? 

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

См. вводные книги Lisp для больше на этом.

В Схеме можно сделать это легко с 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
  )

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

Можно создать круговую структуру данных в Haskell, женившись.

1. Вам не нужна 'разрушительная модификация' для построения самосправочных структур данных; например, в языке Common LISP, '#1=(#1#) ячейка недостатков, которая содержит себя.

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

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

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

(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

как сказано прежде, это сделано с разумным приложением автомобиля набора! и CDR набора!

Мало того, что это возможно, это является довольно центральным к Системе Объекта языка Common LISP: стандартный класс является экземпляром себя!

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

В Haskell можно сделать это просто функционально использование let, который считают хорошим стилем. Одним хорошим примером является regexp-to-NFA преобразование. Можно также сделать это обязательно использование IORefs, который считают плохим стилем, поскольку он вызывает весь Ваш код в монаду IO.

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

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

Hmm, self referential data structures in Lisp/Scheme, and SICP streams are not mentioned? Well, to summarize, streams == lazily evaluated list. It might be exactly the kind of self reference you've intended, but it's a kind of self reference.

So, cons-stream in SICP is a syntax that delays evaluating its arguments. (cons-stream a b) will return immediately without evaluating a or b, and only evaluates a or b when you invoke car-stream or cdr-stream

From 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))))

This definition says that fibs is a stream beginning with 0 and 1, such that the rest of the stream can be генерируется путем добавления фибры к себе сдвинуто на одно место:

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

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

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

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

Я наткнулся на этот вопрос, когда искал "CIRCULAR LISTS LISP SCHEME".

Вот как я могу его создать (в схеме 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 - \ , чтобы выйти.

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

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

Есть ли какие-нибудь реальные примеры?