Hi All,
I have to detect whether or not an object is a dotted list. My solution is
(defvar *dotted-list* nil)
(defun dotted-list-p (l)
(let ((*dotted-list* *dotted-list*))
(push (car l) *dotted-list*)
(let ((c (cdr l)))
(when c
(if (consp c)
(dotted-list-p c)
(values t (nreverse *dotted-list*) c))))))
which returns the values of the predicate, the list before the dot and the final cdr.
CL-USER>(dotted-list-p '(1 2 3 4 5 6 7 . 8))
T
(1 2 3 4 5 6 7)
8
I think this function is end recursive and most implementation optimize it to a tail call.
Do you have any comments? Is there a more idomatic way to get these infos? Did I miss anything?
Andreas
There is the function, (last list0 0) that gives you the last element
of a list. so you could write a function, that tests if the last
element is nil (a proper list) or of type 't for a dotted list:
(defun dottedp (list0)
(and (consp list0)
(last list0 0)
t))
or
(defun dottedp (list0)
(when (and (consp list0)
(last list0 0))
t))
c.
"(typep 'nil (statisfies 'identity))" wrote:
> There is the function, (last list0 0) that gives you the last element
> of a list. so you could write a function, that tests if the last
> element is nil (a proper list) or of type 't for a dotted list:
>
> (defun dottedp (list0)
> (and (consp list0)
> (last list0 0)
> t))
>
> or
>
> (defun dottedp (list0)
> (when (and (consp list0)
> (last list0 0))
> t))
Isn't this enough?
(defun dottedp (list)
(cdr (last list)))
Alberto
Alberto Riva wrote:
> "(typep 'nil (statisfies 'identity))" wrote:
>> There is the function, (last list0 0) that gives you the last element
>> of a list. so you could write a function, that tests if the last
>> element is nil (a proper list) or of type 't for a dotted list:
>>
>> (defun dottedp (list0)
>> (and (consp list0)
>> (last list0 0)
>> t))
>>
>> or
>>
>> (defun dottedp (list0)
>> (when (and (consp list0)
>> (last list0 0))
>> t))
>
> Isn't this enough?
>
> (defun dottedp (list)
> (cdr (last list)))
>
> Alberto
Thank you both. To get the same functionality as my proposal, I think one should write:
(defun dottedp (list)
(cdr (last list)))
(defun head (list)
(append (butlast list) (list (car (last list)))))
(defun undot (list)
(let ((dot (dottedp list)))
(when dot
(append (head list) (list dot)))))
Function head gives you the list in front of the dot while undot creates a equivalent list if the given list is dotted.
Andreas
On 2008-11-19, \"(typep 'nil (statisfies 'identity))" <··············@yahoo.it>
wrote:
> There is the function, (last list0 0) that gives you the last element
> of a list. so you could write a function, that tests if the last
> element is nil (a proper list) or of type 't for a dotted list:
>
> (defun dottedp (list0)
> (and (consp list0)
> (last list0 0)
> t))
You missed a requirement; his function also returns the ``purged'' list:
the proper version of the list with the terminating atom replaced by NIL.
(defun dotted-p (l)
(values
(last l 0)
(butlast l 0)))
It does not follow the interface required. It is better instead: the
first value returns
nil if the list is not dotted. Otherwise, it returns cdr of last
cons.
Second value is the "fixed" list. It is not so fine as it reconcs list
when it is not dotted, but
OP's version does that too.
To avoid unnecessary consing, we might do:
(defun dotted-p-2 (l)
(let ((lastcdr (last l 0)))
(values lastcdr
(if lastcdr (butlast l 0) l))))
On Nov 19, 11:29 am, "Andreas Thiele" <······@nospam.com> wrote:
> Do you have any comments? Is there a more idomatic way to get these infos? Did I miss anything?
Why on earth does it use a special variable?
On 20 nov, 20:48, Tim Bradshaw <··········@tfeb.org> wrote:
> On Nov 19, 11:29 am, "Andreas Thiele" <······@nospam.com> wrote:
>
> > Do you have any comments? Is there a more idomatic way to get these infos? Did I miss anything?
>
> Why on earth does it use a special variable?
Why on earth eat chicken when you can eat steak? My only comment is
that if he'd used CLOS, he could have worked a change-class in there.
(More seriously, to the OP, the idiom when using tail-recursion is to
have an optional "accumulator" parameter to the function, for internal
use. Binding a special variable makes your recursion non-tail and thus
it won't be merged -- for current Lisp implementations, at least. Even
better: use iteration.)
On Nov 21, 10:52 am, "Thomas F. Burdick" <········@gmail.com> wrote:
> (More seriously, to the OP, the idiom when using tail-recursion is to
> have an optional "accumulator" parameter to the function, for internal
> use.
Or
(let ((acc ...))
(labels ...))
> Binding a special variable makes your recursion non-tail and thus
> it won't be merged -- for current Lisp implementations, at least. Even
> better: use iteration.)
But Iteration is not PURE. Especially not LOOP: everyone who has ever
used LOOP will go to HELL.
Also it would be faster with static type checking and pattern
matching, all of which are PURE. Finally: do not use Lisp.
--tim
On 21 nov, 13:25, Tim Bradshaw <··········@tfeb.org> wrote:
> On Nov 21, 10:52 am, "Thomas F. Burdick" <········@gmail.com> wrote:
>
> > Binding a special variable makes your recursion non-tail and thus
> > it won't be merged -- for current Lisp implementations, at least. Even
> > better: use iteration.)
>
> But Iteration is not PURE. Especially not LOOP: everyone who has ever
> used LOOP will go to HELL.
Whew, good thing I was going to suggest PROG, then.
> Also it would be faster with static type checking and pattern
> matching, all of which are PURE. Finally: do not use Lisp.
>
> --tim
Thomas F. Burdick wrote:
> On 21 nov, 13:25, Tim Bradshaw <··········@tfeb.org> wrote:
>
>>On Nov 21, 10:52 am, "Thomas F. Burdick" <········@gmail.com> wrote:
>>
>>
>>>Binding a special variable makes your recursion non-tail and thus
>>>it won't be merged -- for current Lisp implementations, at least. Even
>>>better: use iteration.)
>>
>>But Iteration is not PURE. Especially not LOOP: everyone who has ever
>>used LOOP will go to HELL.
>
>
> Whew, good thing I was going to suggest PROG, then.
>
>
>>Also it would be faster with static type checking and pattern
>>matching, all of which are PURE. Finally: do not use Lisp.
Should I start posting Javascript solutions?
kxo
Kenny <·········@gmail.com> writes:
> Thomas F. Burdick wrote:
> > On 21 nov, 13:25, Tim Bradshaw <··········@tfeb.org> wrote:
> >
> >>On Nov 21, 10:52 am, "Thomas F. Burdick" <········@gmail.com> wrote:
> >>
> >>
> >>>Binding a special variable makes your recursion non-tail and thus
> >>>it won't be merged -- for current Lisp implementations, at least. Even
> >>>better: use iteration.)
> >>
> >>But Iteration is not PURE. Especially not LOOP: everyone who has ever
> >>used LOOP will go to HELL.
> > Whew, good thing I was going to suggest PROG, then.
> >
> >>Also it would be faster with static type checking and pattern
> >>matching, all of which are PURE. Finally: do not use Lisp.
>
> Should I start posting Javascript solutions?
Only if they involve AJAX.
And ideally require a completely new browser to execute that nobody has
heard of before.
--
Thomas A. Russ, USC/Information Sciences Institute
Thomas A. Russ wrote:
> Kenny <·········@gmail.com> writes:
>
>
>>Thomas F. Burdick wrote:
>>
>>>On 21 nov, 13:25, Tim Bradshaw <··········@tfeb.org> wrote:
>>>
>>>
>>>>On Nov 21, 10:52 am, "Thomas F. Burdick" <········@gmail.com> wrote:
>>>>
>>>>
>>>>
>>>>>Binding a special variable makes your recursion non-tail and thus
>>>>>it won't be merged -- for current Lisp implementations, at least. Even
>>>>>better: use iteration.)
>>>>
>>>>But Iteration is not PURE. Especially not LOOP: everyone who has ever
>>>>used LOOP will go to HELL.
>>>
>>>Whew, good thing I was going to suggest PROG, then.
>>>
>>>
>>>>Also it would be faster with static type checking and pattern
>>>>matching, all of which are PURE. Finally: do not use Lisp.
>>
>>Should I start posting Javascript solutions?
>
>
> Only if they involve AJAX.
>
> And ideally require a completely new browser to execute that nobody has
> heard of before.
>
OK, done:
function detectDottedList (lizt) {
return null;
}
You cannot make a dotted list in JS.
Note also that I am not being nagged to death for declare-ignores, and
that at long last I have an excuse to do camelCase.
MWAUHAHAHHAHHAA!!!!! Die, Lisp! Die!!! Again!
hth,kenny
By the way, one might avoid consing and make only one pass at the same
time if we use the stack:
(defun the-best-dotted-list-p (l)
(let ((res nil))
(labels ((f (sub)
(cond
((consp sub)
(let ((tail (f (cdr sub))))
(cons (car sub) tail)))
((null sub)
(return-from the-best-dotted-list-p (values nil l)))
(t (setf res sub)
nil))))
(let ((res2 (f l)))
(values res res2)))))
I think it depends on implementation if it is a fastest implementation.
On 2008-11-19, Andreas Thiele <······@nospam.com> wrote:
> Hi All,
>
> I have to detect whether or not an object is a dotted list. My solution is
>
> (defvar *dotted-list* nil)
>
> (defun dotted-list-p (l)
> (let ((*dotted-list* *dotted-list*))
> (push (car l) *dotted-list*)
> (let ((c (cdr l)))
> (when c
> (if (consp c)
> (dotted-list-p c)
> (values t (nreverse *dotted-list*) c))))))
>
> which returns the values of the predicate, the list before the dot and the final cdr.
>
> CL-USER>(dotted-list-p '(1 2 3 4 5 6 7 . 8))
> T
> (1 2 3 4 5 6 7)
> 8
>
> I think this function is end recursive and most implementation optimize it to a tail call.
>
> Do you have any comments? Is there a more idomatic way to get these infos?
Do you want idiomatic or do you want efficient?
See, you can accomplish this in a way that makes only one pass over the input
list, and does not have to reverse the output list.
Building an output list without having to reverse it is slightly ugly, at least
if you use primitive cons-cell-manipulating functions in Lisp.
Luckily, list collection is abstracted in the LOOP macro.
The LOOP macro also allows list iteration over conses, rather than their
contents: you use the ON keyword rather than IN, similar to MAPLIST.
(defun dotted-list-p (original-list)
"Returns two values: a generalized boolean indicating whether or not the
input object is a dotted list (remembering that an atom is not a dotted list);
and a new version of the list like the input list, but the terminating atom
being NIL. This list may share substructure with the input list."
(loop with is-dotted = t
for tail on original-list
collecting (car tail) into new-list
when (null (cdr tail))
do (setf is-dotted nil)
finally
(return (values is-dotted
(if is-dotted new-list original-list)))))
This makes only one pass, but it wastes memory consing up a new list even when
it's not necessary. When the output list is not needed, we could return it
anyway, but we don't.
The reason for that is that it's more efficient to return the original list.
If you return the new list, then the program ends up with two objects: the
original list and the new list. It may well hang on to both of them for a long
time, wasting memory. If it hangs on to the new list, and discards the old,
it's still less efficient, because the garbage generated by discarding the old
list is older than garbage generated by discarding the new list. Some Lisp
systems have an generational garbage collectors which can more quickly reclaim
new garbage. This speeds up code which conses up temporary objects which are
immediately discarded.
We can avoid consing up the new list if we allow ourselves to make an extra
pass over the original list to detect how it is terminated:
(defun dotted-list-p (original-list)
" ... same docstring as above ... "
(let ((terminator (last original-list 0)))
(values
terminator
(if terminator
(butlast original-list 0)
original-list))))
This is also more idiomatic, since the algorithm consists of just trivially
combining the results from calling one or two standard library functions.
Perhaps better than BUTLAST, in this situation, is LDIFF. LDIFF is inherently
simpler, because it just has to scan the input list with a single pointer to
find a a matching pointer.
To use LDIFF, you have to know the identity of the terminating atom. For
instance (ldiff '(1 2 3 4 . 5) 5) is (1 2 3 4). We have the terminating
atom, and so we can rewrite the above IF like this:
(if terminator
(ldiff original-list terminator)
original list))
Both these versions also returns the terminating atom of the dotted list,
rather than the value T. Our one-pass version could be fixed to do that, as
well.
(loop with terminator
for tail on original-list
collecting (car tail) into new-list
when (atom (cdr tail))
do (setf terminator (cdr tail))
finally
(return (values terminator
(if terminator new-list original-list))))
The function could be then renamed like this:
(defun destructure-dotted (list)
"Returns two values: the terminating atom of the given list, and a version
of the list in which the terminating atom is replaced by NIL.
This may just be the given list if it's already NIL terminated."
...)
Guaranteeing this behavior makes the interface more useful.