O, those are not the tipical things to do in Scheme!
(why? read after the answer of your question)
Scheme is an elegant descentant of LISP, the first functional programming language.
LISt Processing, was the first programming language defining it's
semantics axiomatically.
The main data structure is the list.
There are three kinds of lists in lisp (and scheme).
Proper lists, dotted lists, and circular lists.
Proper lists are inductively defined as follows:
i) nil is a (proper) list
ii) (x . xs) is a list if xs is a (proper) list
iii) only the objects formed by rules i-ii are (proper) lists.
(x . xs) is other notation for (cons x xs) the constructor.
(a b c d) is a brief form of (a . (b . (c . (d . nil))))
In statically-typed languages a proper list may be defined as follows:
i) nil is a list of type 'a
ii) (x . xs) is a list if xs is a list of type 'a and x is of type 'a
iii) only the objects formed by rules i-ii are lists of type 'a.
(a b c) is a legal list of symbols
((1) (2) (3)) is a legal list of lists of numbers
(a (a) 2) is an illegal list in a statically typed language (like SML or Haskell)
Dotted lists are a more general data structrure, because lisp is
dynamically typed language,
it is possible to define lists of objects of any type not homogeneous,
like the second definition of a list of type a.
A dotted list is defined as follows
i) x is an atom then it is a (dotted) list
ii) (x . xs) is a list if xs is a (dotted) list
iii) only the objects formed by rules i-ii are (dotted) lists.
As you can see, the only difference between proper lists and dotted
list (in lisp or scheme)
is that they can end with an atom different of nil. a number or symbol.
Actually dotted lists are binary trees for exampe '((a . b) . (c .
d)) in short notation ((a . b) c . d)
is a representation of a binary tree with leafs a,..,d
Circular lists are constructed with set-cdr! in order to allow what
you call "loop back",
in that case the "last" element of a "list" is a pointer to some pair
in the "list".
( a . ( b . | ))
^ |
+-------+
How could you find when some element is repeating,
first you must remember that lisp's EQ compairs pointers while EQUAL
when faced with two
lists compairs each element recursively.
In Scheme you have eq? and eqv?.
A way to find the link to the repeating section of the circular list
is to build a list of lists to the
tails recursively, use it as a parameter and testing every time for
membership of the cdr,
if it is included you got the place where the pointer is.
It is not efficient, but works. I do not write the code, because
your question seems part of a homework.
In order to improve performance, it is not wise to do such waste of
time, it is better to build an abstract data type
where the pointer held by an encapsulated variable.
See the wizards book (Abelson, Susmann, Structure and Interpretation
of Computer Programs, MIT Press)
to find more about data absraction and encapsulation.
The use of destructive "functions" like set-car!, set-cdr! must
restricted to very exceptional cases, use carfuly.
The style of Scheme is more functional than imperative, don't use
imperative (destructive) "functions" if it is note strictly needed.
Function application and composition is more typical.
Scheme is an eager language, but you can get some lazyness with the
use of streams, in order, for example to
implement an infinite list of ones, or all the natural numbers (and
you do not need to make use of circular lists).
You can also check the following reports to know more about scheme (and lisp):
Revised report on the algorithmic language Scheme.
R. Kelsey, W. Clinger, J. Rees (editors).
Higher-Order and Symbolic Computation, Vol. 11, No. 1, September, 1998.
and ACM SIGPLAN Notices, Vol. 33, No. 9, October, 1998.
Common Lisp: the Language
Guy L. Steele Jr. (editor).
Digital Press, Maynard, Mass., second edition 1990. |
