I can create a circular data structure in Scheme like this:
(define my-pair (cons 1 1))
(set-car! my-pair my-pair)
Is it possible to create a circular data structure in Scheme without using mutation? (I am preparing a lecture on the limits of reference counting.)
You can make a lazy list with closures:
; The infinite list (1 1 1 ...
(define ones
(letrec ((x (cons 1 (lambda () x))))
x))
> ones
'(1 . #<procedure>)
> ((cdr ones))
'(1 . #<procedure>)
Identity check verifying circularity:
> (eq? ones ((cdr ones)))
#t
By following a link to a related question (Why don't purely functional languages use reference counting?), I saw a reference to letrec. That made me realize that I can indeed create a circular "data structure" in Scheme:
(letrec ((add (lambda (x y) (if (>= x y) (+ x y) (add2 y x))))
(add2 (lambda (x y) (if (>= x y) (+ x y) (add y x)))))
(add 1 5))
Adding to @molbdnilo answer most scheme imeplemetation define delay and force,
that allow to create so called streams (defined in
SICP).
; The infinite list (1 1 1 ...
(define ones (cons 1 (delay ones)))
> ones
(1 . #<promise>)
> (force (cdr ones))
(1 . #<promise>)
(eq? ones (force (cdr ones)))
#t
delay and force can be implemented as macros that are just lambda expression. You can even write procedures like filter or map that handle streams.
EDIT:
Also defined by R7RS you can create real circular list with datum labels.
(define x '#0=(a b c . #0#))
x
;; ==> #0=(a b c . #0#)
(eq? x (cdddr x))
#t
If Scheme fully support the R7RS spec it should allow to define and display circular list in the same way. Note that in Kawa Scheme it will print in a loop to display the circular list you need to use (write x).
