Menu
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?
702
A self referential data structure is essentially a structure definition which includes at least one member that is a pointer to the structure of its own kind. • Such self referential structures are very useful in applications that involve linked data structures, such as lists and trees.
Self Referential structures are those structures that have one or more pointers which point to the same type of structure, as their member. In other words, structures pointing to the same type of structures are self-referential in nature.
Many applications of LISP involve storing a variety of values associated with a symbolic name. Association lists and property lists provide two ways of doing this, unique to LISP. Arrays, vectors and strings are also used for data storage and manipulation.
The self-referential structure is widely used in dynamic data structures such as trees, linked lists, and so on. The next node of a node will be pointed in linked lists, which consists of the same struct type. It is a unique type of structure containing a member of its type.
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.
76
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
)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
