Self-referential data structures in Lisp/Scheme

Question

Is there a way to construct a self-referential data structure (say a graph with cycles) in lisp or scheme? I'd never thought about it before, but playing around I can find no straightforward way to make one due to the lack of a way to make destructive modification. Is this just an essential flaw of functional languages, and if so, what about lazy functional languages like haskell?

Answer 1

In Scheme, you can do it easily with set!, set-car!, and set-cdr! (and anything else ending in a bang ('!'), which indicates modification):

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

Common Lisp supports modification of data structures with setf.

You can build a circular data structure in Haskell by tying the knot.

Answer 3

In Common Lisp you can modify list contents, array contents, slots of CLOS instances, etc.

Common Lisp also allows to read and write circular data structures. Use

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

So-called pure Functional Programming Languages don't allow side-effects. Most Lisp dialects are not pure. They allow side-effects and they allow to modify data-structures.

See Lisp introduction books for more on that.

Answer 4

1. You don't need `destructive modification' to construct self-referential data structures; e.g., in Common Lisp, '#1=(#1#) is a cons-cell that contains itself.

2. Scheme and Lisp do not lack of way to make destructive modification: you can construct the circular cons above alternatively like this: (let ((x (cons nil nil))) (rplaca x x) x)

Can you let us know what material you're using while learning Lisp/Scheme? I'm compiling a target list for our black helicopters; this spreading of misinformation about Lisp and Scheme has to be stopped.

Answer 5

CLOS example:

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

Yes, and they can be useful. One of my college professors created a Scheme type he called Medusa Numbers. They were arbitrary precision floating point numbers that could include repeating decimals. He had a function:

(create-medusa numerator denominator) ; or some such

which created the Medusa Number that represented the rational. As a result:

(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

as said before, this is done with judicious application of set-car! and set-cdr!

Answer 7

Not only is it possible, it's pretty central to the Common Lisp Object System: standard-class is an instance of itself!

Answer 8

I upvoted the obvious Scheme techniques; this answer addresses only Haskell.

In Haskell you can do this purely functionally using let, which is considered good style. One nice example is regexp-to-NFA conversion. You can also do it imperatively using IORefs, which is considered poor style as it forces all your code into the IO monad.

In general Haskell's lazy evaluation lends itself to lovely functional implementations of both cyclic and infinite data structures. In any complex let binding, all things bound may be used in all definitions. For example translating a particular finite-state machine into Haskell is a snap, no matter how many cycles it may have.

Answer 9

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 generated by adding fibs to itself shifted by one place:

In this case, 'fibs' is assigned an object whose value is defined lazily in terms of 'fibs'

Almost forgot to mention, lazy streams live on in the commonly available libraries SRFI-40 or SRFI-41. One of these two should be available in most popular Schemes, I think

Answer 10

Tying the Knot (circular data structures in Haskell)

Answer 11

I stumbled upon this question while searching for "CIRCULAR LISTS LISP SCHEME".

This is how I can make one (in STk Scheme):

First, make a list

(define a '(1 2 3))

At this point, STk thinks a is a list.

(list? a)
> #t

Next, go to the last element (the 3 in this case) and replace the cdr which currently contains nil with a pointer to itself.

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

Now, STk thinks a is not a list.

(list? a)
> #f

(How does it work this out?)

Now if you print a you will find an infinitely long list of (1 2 3 1 2 3 1 2 ... and you will need to kill the program. In Stk you can control-z or control-\ to quit.

But what are circular-lists good for?

I can think of obscure examples to do with modulo arithmetic such as a circular list of the days of the week (M T W T F S S M T W ...), or a circular list of integers represented by 3 bits (0 1 2 3 4 5 6 7 0 1 2 3 4 5 ..).

Are there any real-world examples?

Answer 12

In reply to Phil Colbourne (sorry, but I can't work out how to reply to his post directly): These kind of things turn up occasionally. I ran across this issue while trying to implement a Fibonacci heap for use in a timed cache, for example.