I'm trying to create a function that would test whether the given list is circular with a re-starting point being the beginning of the list.
Expected results:
(setq liste '(a b c))
(rplacd (cddr liste) liste)
(circular liste) => t
(circular '(a b c a b c)) => nil
As I simply want to test if any subsequent item is 'eq' to the first one, I don't want to build the whole tortoise and hare algorithm.
Here is my code :
(defun circular (liste)
(let (beginningliste (car liste)))
(labels ( (circ2 (liste)
(cond
((atom liste) nil)
((eq (car liste) beginningliste) t)
(t (circ2 (cdr liste)))
) ) ) ) )
- It doesn't give the expected result but I don't understand where my error is
- I'm not sure I'm using 'labels' correctly
- Is there a way to do that without using 'labels'?
Edit. I guess I have answered my third question as I think I have found a simpler way. Would this work?
(defun circular (liste)
(cond
((atom liste) nil)
((eq (car liste) (cadr liste)) t)
(t (circular (rplacd liste (cddr liste))))
)
)
First, the behavior is undefined when you mutate constant data: when you quote something (here the list), the Lisp environment has the right to treat it as a constant. See also this question for why
defparameter
ordefvar
is preferred oversetq
. And so...... would be better written as:
Second, your code is badly formatted and has bad naming conventions (please use dashes to separate words); here it is with a conventional layout, with the help of emacs:
With that formatting, two things should be apparent:
The
let
contains no body forms: you define local variables and never use them; you could as well delete thelet
line.Furthermore, the
let
is missing one pair of parenthesis: what you wrote defines a variable namefirst
and another one namedcar
, bound tolist
. I presume you want to definefirst
as(car list)
.You define a local
circ2
function but never use it. I would expect thecircularp
function (the-p
is for "predicate", likenumberp
,stringp
) to call(circ2 (cdr list))
. I prefer renamingcirc2
asvisit
(orrecurse
), because it means something.With the above corrections, that would be:
However, if your list is not circular but contains the same element multiple times (like
'(a a b))
, you will report it as circular, because you inspect the data it holds instead of the structure only. Don't look into theCAR
here:Also, the inner function is tail recursive but there is no guarantee that a Common Lisp implementation automatically eliminates tail calls (you should check with your implementation; most can do it on request). That means you risk allocating as many call stack frames as you have elements in the list, which is bad. Better use a loop directly:
Last, but not least: your approach is a very common one but fails when the list is not one big circular chain of cells, but merely contains a loop somewhere. Consider for example:
(see that answer where I explain what
#1=
and#1#
mean)The lists with numbers in front exhibit circularity but you can't just use the first cons cell as a marker, because you will be looping forever inside the sublist that is circular. This is the kind or problems the Tortoise and Hare algorithm solves (there might be other techniques, the most common being storing visited elements in a hash table).
After your last edit, here is what I would do if I wanted to check for circularity, in a recursive fashion, without
labels
:We keep track of all the visited cons cells in
seen
, which is optional and initialized to NIL (you could pass another value, but that can be seen as a feature).Then, we say that a list is circular with respect to seen if it is a cons cell which either: (i) already exists in seen, or (ii) is such that its CDR is circular with respect to
(cons list seen)
.The only additional trick here is to ensure the result is a boolean, and not the return value of
member
(which is the sublist where the element being searched for is the first element): if your environment has*PRINT-CIRCLE*
set to NIL and the list is actually circular, you don't want it to try printing the result.Instead of
(if (member list seen) t nil)
, you could also use:(when (member list seen))
(position list seen)
(not (not (member list seen)))