Is this considered tail-recursive?
(defun uniq (lst)
(if (null lst)
t
(and (not (contains (car lst) (cdr lst)))
(uniq (cdr lst)))))
To me, it would seem it is, since and is not a function but a form.
Specifically, by the time we get to the recursion, we can simply
replace our stack with it and return it directly.
Is there any advantage to writing it:
(defun uniq (lst)
(cond ((null lst) t)
((contains (car lst) (cdr lst)) nil)
(t (uniq (cdr lst)))))
In article <························@l53g2000cwa.googlegroups.com>,
"S. Robert James" <············@gmail.com> wrote:
> Is this considered tail-recursive?
>
> (defun uniq (lst)
> (if (null lst)
> t
> (and (not (contains (car lst) (cdr lst)))
> (uniq (cdr lst)))))
>
> To me, it would seem it is, since and is not a function but a form.
> Specifically, by the time we get to the recursion, we can simply
> replace our stack with it and return it directly.
Correct.
>
> Is there any advantage to writing it:
>
> (defun uniq (lst)
> (cond ((null lst) t)
> ((contains (car lst) (cdr lst)) nil)
> (t (uniq (cdr lst)))))
It's clearer to human readers, IMHO.
If you want something more like your first version, you could use UNLESS
instead of AND NOT:
(defun uniq (list)
(or (null list)
(unless (contains (car list) (cdr list))
(uniq (cdr list))))
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
For what it's worth, I am a newbie and the cond version is the only
one that makes sense to me. I have a question though... what is
"contains"? I mean I understand what is supposed to be doing but it
isn't a lisp function... is it a macro or something I don't know
about? Is it a function that was defined in a previous thread I
didn't read?
"landspeedrecord" <···············@gmail.com> writes:
> For what it's worth, I am a newbie and the cond version is the only
> one that makes sense to me. I have a question though... what is
> "contains"? I mean I understand what is supposed to be doing but it
> isn't a lisp function... is it a macro or something I don't know
> about? Is it a function that was defined in a previous thread I
> didn't read?
You can s/contain/member/ I guess...
--
__Pascal Bourguignon__ http://www.informatimago.com/
WARNING: This product warps space and time in its vicinity.
(message (Hello 'S.)
(you :wrote :on '(8 Feb 2007 19:23:56 -0800))
(
SRJ> Is this considered tail-recursive?
yes, but it might be suboptimal for larger lists.
this one should be faster:
(defun uniq (list)
(loop for (a b) on (sort (copy-list list) #'<)
never (equal a b)))
since it doesn't contain a call to #'contains that makes it O(N^2), but it
works only on numbers, and conses..
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"?? ???? ??????? ?????")