Hello again comp.lang.lisp
I am doing some simple exercises located in
<http://www.cs.northwestern.edu/academics/courses/325/exercises/lisp-
exs.html>
Here's what I have so far, please critisize my code.
; Lisp #1: HAS-NUMBER-P (Wilensky 8.7)
(defun has-number-p (sexp)
(if (listp sexp)
(some #'has-number-p sexp)
(numberp sexp)))
; Lisp #3: MAKE-BALANCE (Wilensky, 12)
(defun make-balance (balance)
(let ((closure-balance balance))
(lambda (&optional x)
(if x
(incf closure-balance x)
closure-balance))))
; Lisp #4: DELETE-CAR (Wilensky, 15)
(defun delete-car (x)
(let ((y (rest x)))
(setf (rest x) nil)
(setf x y)))
(I skipped exercise #2 because I don't know much about macros, yet)
#5 has me stumbled:
> Define (collect-numbers s-exp) to return a list of all the numbers in the s-expression s-exp. s-exp may be an atom, a list, or a list of s-expressions.
Here's what I have in mind:
Turn
'(1 (2 3) (4 (5 A)) 6)
into (1 2 3 4 5 A 6)
And then use (remove-if #'numberp sexp)
Unfortunately, I don't know how to do step 1.
Any help? Perhaps there's a better way than what I have in mind?
Another idea would be to transverse the list, and collect the items
satisfying the test (numberp) unless they are lists; In that case,
append to the current list the return value of the function called
with that list, but I've failed to implement that as well.
P.S. not homework, I'm trying to learn common lisp
On 2008-06-07 09:00:14 -0400, ········@gmail.com said:
> Unfortunately, I don't know how to do step 1.
There is a very common lisp utility called flatten.
Paul Graham gives a version in On Lisp thus:
(defun flatten (x)
(labels ((rec (x acc)
(cond ((null x) acc)
((atom x) (cons x acc))
(t (rec (car x) (rec (cdr x) acc))))))
(rec x nil)))
On Jun 7, 5:27 pm, Raffael Cavallaro <················@pas-d'espam-
s'il-vous-plait-mac.com> wrote:
> On 2008-06-07 09:00:14 -0400, ········@gmail.com said:
>
> > Unfortunately, I don't know how to do step 1.
>
> There is a very common lisp utility called flatten.
>
> Paul Graham gives a version in On Lisp thus:
>
> (defun flatten (x)
> (labels ((rec (x acc)
> (cond ((null x) acc)
> ((atom x) (cons x acc))
> (t (rec (car x) (rec (cdr x) acc))))))
> (rec x nil)))
Thanks :-).
I see 'On Lisp' is available for free from Paul Grahams website, I
shall have a look.
Raffael Cavallaro <················@pas-d'espam-s'il-vous-plait-mac.com> wrote:
+---------------
| ········@gmail.com said:
| > Unfortunately, I don't know how to do step 1.
|
| There is a very common lisp utility called flatten.
| Paul Graham gives a version in On Lisp thus:
| (defun flatten (x)
| (labels ((rec (x acc)
| (cond ((null x) acc)
| ((atom x) (cons x acc))
| (t (rec (car x) (rec (cdr x) acc))))))
| (rec x nil)))
+---------------
Note that this function should be more properly called FLATTEN-TREE,
as contrasted with FLATTEN-LIST, e.g.:
(defun flatten-list (list)
(loop for item in list
when (consp item)
nconc (flatten-list item)
else
collect item))
The difference appears when the data really is a "list of lists"
and some of the lists contain NIL as an member:
> (flatten-tree '(1 2 nil (3 4 nil (5 6 nil 7) nil) nil))
(1 2 3 4 5 6 7)
> (flatten-lists '(1 2 nil (3 4 nil (5 6 nil 7) nil) nil))
(1 2 NIL 3 4 NIL 5 6 NIL 7 NIL NIL)
>
Sometimes you want one, and sometimes you want the other.
It all depends on your particular application.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
thus spoke ········@gmail.com:
> (I skipped exercise #2 because I don't know much about macros, yet)
Go learn Peter Seibel's book with a good introduction to macros. It's
available for free at <http://gigamonkeys.com/book/>
>#5 has me stumbled:
>> Define (collect-numbers s-exp) to return a list of all the numbers in
>> the s-expression s-exp. s-exp may be an atom, a list, or a list of
>> s-expressions.
> Here's what I have in mind:
> Turn
> '(1 (2 3) (4 (5 A)) 6)
> into (1 2 3 4 5 A 6)
> And then use (remove-if #'numberp sexp)
> Unfortunately, I don't know how to do step 1.
what you need is a flatten function. To do the actual collecting, LOOP
is inappropriate, PUSH/NREVERSE is applicable, but somewhat ugly and
wasteful. A WITH-COLLECT macro will do, but you need to define it first:
(defmacro with-collect ((fn) &body body)
(let ((last-name (gensym "LAST-NAME"))
(list-name (gensym "LIST-NAME")))
`(let* ((,list-name (list nil))
(,last-name ,list-name))
(flet ((,fn (obj)
(setq ,last-name (setf (cdr ,last-name) (cons obj nil)))
(cdr ,list-name)))
(declare (inline ,fn))
,@body)
(cdr ,list-name))))
And the actual FLATTEN:
(defun flatten (list)
(with-collect (collect)
(labels ((flatten-aux (list)
(dolist (x list)
(if (listp x)
(flatten-aux x)
(collect x)))))
(flatten-aux list))))
Note that with LISTP, NILs inside the tree structure are simply skipped.
If CONSP was used instead, they would be treated as atoms.
Now,
CL-USER> (flatten '(1 (2 3) (4 (5 A)) 6))
(1 2 3 4 5 A 6)
CL-USER> (remove-if-not #'numberp *)
(1 2 3 4 5 6)
--
The great peril of our existence lies in the fact that our diet consists
entirely of souls. -- Inuit saying
········@gmail.com writes:
> #5 has me stumbled:
>> Define (collect-numbers s-exp) to return a list of all the numbers
>> in the s-expression s-exp. s-exp may be an atom, a list, or a list
>> of s-expressions.
It is very easy to implement COLLECT-NUMBERS:
(defun collect-numbers (thing)
(collect-if #'numberp thing))
Oh, so we need to implement COLLECT-IF. No problem:
(defun collect-if (predicate thing)
(cond ((funcall predicate thing)
;; We're interested in thing, so return it (in a list).
(list thing))
((consp thing)
;; Thing is a cons, so we need to append both the
interesting
;; stuff in the car and the interesting stuff in the cdr.
(append (collect-if predicate (car thing))
(collect-if predicate (cdr thing))))
(t
;; Thing is an uninteresting atom, so return the empty
list.
'())))
This works, but isn't very efficient. There are many ways to
implement COLLECT-IF more efficiently, so let's pick one:
(defun collect-if (predicate thing)
(let ((interesting-stuff '()))
(map-atoms (lambda (atom)
(when (funcall predicate atom)
(push atom interesting-stuff)))
thing)
;; We don't need to reverse it for this particular problem, but
;; it may be useful in the more general case.
(nreverse interesting-stuff)))
This is better, but we need to implement MAP-ATOMS in order for it to
work:
(defun map-atoms (function thing)
(typecase thing
;; It's an atom, so we call the function with it.
(atom (funcall function thing))
;; It's a cons, so we map the atoms in its car and its cdr.
(cons (map-atoms function (car thing))
(map-atoms function (cdr thing)))))
There we go:
CL-USER> (collect-numbers '(1 (2 3) (4 (5 a)) 6))
(1 2 3 4 5 6)
Ariel
On Jun 8, 1:57 am, Ariel Badichi <····@tidexsystems.com> wrote:
> ········@gmail.com writes:
> > #5 has me stumbled:
> >> Define (collect-numbers s-exp) to return a list of all the numbers
> >> in the s-expression s-exp. s-exp may be an atom, a list, or a list
> >> of s-expressions.
>
> It is very easy to implement COLLECT-NUMBERS:
>
<snip>
> There we go:
>
> CL-USER> (collect-numbers '(1 (2 3) (4 (5 a)) 6))
> (1 2 3 4 5 6)
Excellent, thanks a lot Ariel.
I like how you showed me "how to think" in order to implement that
function.
Perhaps collect-if can be modified to work with sequences and not just
lists?
I'll try to write that.
thus spoke ········@gmail.com:
> Perhaps collect-if can be modified to work with sequences and not just
> lists?
Sure!
;;; Functionally equivalent to REMOVE-IF-NOT without all the fancy
;;; keywords
(defun collect-if (pred seq)
(with-collect (collect)
(map nil (lambda (x)
(when (funcall pred x)
(collect x)))
seq)))
CL-USER> (collect-if #'numberp '(foo 42 bar 69 "Yow!" 1/3))
(42 69 1/3)
--
The great peril of our existence lies in the fact that our diet consists
entirely of souls. -- Inuit saying
········@gmail.com writes:
> Hello again comp.lang.lisp
>
> I am doing some simple exercises located in
> <http://www.cs.northwestern.edu/academics/courses/325/exercises/lisp-
> exs.html>
> Here's what I have so far, please critisize my code.
>
> ; Lisp #1: HAS-NUMBER-P (Wilensky 8.7)
> (defun has-number-p (sexp)
> (if (listp sexp)
> (some #'has-number-p sexp)
> (numberp sexp)))
>
> ; Lisp #3: MAKE-BALANCE (Wilensky, 12)
> (defun make-balance (balance)
> (let ((closure-balance balance))
> (lambda (&optional x)
> (if x
> (incf closure-balance x)
> closure-balance))))
These both look good.
> ; Lisp #4: DELETE-CAR (Wilensky, 15)
> (defun delete-car (x)
> (let ((y (rest x)))
> (setf (rest x) nil)
> (setf x y)))
I don't think this does what you think it does. Have you tried it out
using something like the test case shown in the web site? BTW, the web
site has a bug in this exercise because it asks you to modify constant
list structure, which is a BAD IDEA. But you should still discover that
what is done is not what you expect.
Try the following and see if it matches what it is supposed to do.
(setq l (list 'a 'b 'c))
(delete-car l)
l
You will discover that it does not match the results you should be
getting.
> #5 has me stumbled:
> > Define (collect-numbers s-exp) to return a list of all the numbers in the s-expression s-exp. s-exp may be an atom, a list, or a list of s-expressions.
> Here's what I have in mind:
> Turn
> '(1 (2 3) (4 (5 A)) 6)
> into (1 2 3 4 5 A 6)
> And then use (remove-if #'numberp sexp)
I think you want REMOVE-IF-NOT instead, right?
OK. That is one method that will accomplish the answer. It has the
benefit of being nicely compositional, so that you can use the parts to
build up lots of chained functions.
It does have the drawback that you end up traversing the list structure
two times. Once to flatten the list, and then again to filter the
list.
Another useful technique to learn is one that relies on the use of
accumulator variables to build up the answer during the recursive
descent of the list. Typically this involves the use of a main function
and a helper that takes the accumulator.
There are ways (using LABELS) to make the helper function be an internal
function, although for learning and testing it is often better to have
two separate functions that you can work on and debug independently.
Try the following:
(defun collect-numbers (s-exp)
(collect-numbers-helper s-exp nil))
(defun collect-numbers-helper (s-exp results)
...
)
And in the second function collect the results by recursive descent
through the s-expression, with the goal of getting the answers with only
one pass through the data structure. (Hint: You will end up with the
results in reverse order.)
--
Thomas A. Russ, USC/Information Sciences Institute
On Jun 9, 10:00 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
> ········@gmail.com writes:
> > ; Lisp #4: DELETE-CAR (Wilensky, 15)
> > (defun delete-car (x)
> > (let ((y (rest x)))
> > (setf (rest x) nil)
> > (setf x y)))
>
> I don't think this does what you think it does. Have you tried it out
> using something like the test case shown in the web site? BTW, the web
> site has a bug in this exercise because it asks you to modify constant
> list structure, which is a BAD IDEA. But you should still discover that
> what is done is not what you expect.
>
> Try the following and see if it matches what it is supposed to do.
>
> (setq l (list 'a 'b 'c))
> (delete-car l)
> l
>
> You will discover that it does not match the results you should be
> getting.
I'm starting to believe DELETE-CAR is not possible to implement.
For example:
(defun delete-car (l) (setf l (rest l))) ; not destructive
(defparameter x '(1 2 3 4 5))
(defparameter y (cddr x)) ; y = (3 4 5)
(delete-car y) ; y = (4 5)
At this point, x is '(1 2 3 4 5).
If DELETE-CAR was destructive as the exercise requires, x would be
'(1 2 4 5).
Is it possible to destructively delete the car if you don't know its
cdr?
I see even standard procedures are unable to do this:
> (defparameter x '(a b c))
==> X
> (delete 'a x)
==> (b c)
> x
==> '(a b c)
I understand cons cells, and I understand why this happends.
So, is a destructive DELETE-CAR actually possible to implement?
Anyone got any interesting lisp exercises? (books are fine too)
On 10 Jun., 15:04, ········@gmail.com wrote:
> I understand cons cells, and I understand why this happends.
> So, is a destructive DELETE-CAR actually possible to implement?
Yes, but:
(1) SETFing variables is not going to buy you much. You need to SETF
something else.
(2) The specification of DELETE-CAR rightly notes: "it's impossible
to destructively delete the only item in a list and turn it into
NIL". The one-element case is therefore expressly allowed not to work
(because it can't).
Matthias
Thomas A. Russ wrote:
> ········@gmail.com writes:
>
>> Hello again comp.lang.lisp
>>
>> I am doing some simple exercises located in
>> <http://www.cs.northwestern.edu/academics/courses/325/exercises/lisp-
>> exs.html>
>
>> ; Lisp #4: DELETE-CAR (Wilensky, 15)
>> (defun delete-car (x)
>> (let ((y (rest x)))
>> (setf (rest x) nil)
>> (setf x y)))
>
> I don't think this does what you think it does. Have you tried it out
> using something like the test case shown in the web site? BTW, the web
> site has a bug in this exercise because it asks you to modify constant
> list structure, which is a BAD IDEA.
Fixed. Thanks
Thomas A. Russ wrote:
> ········@gmail.com writes:
>
>> #5 has me stumbled:
>>> Define (collect-numbers s-exp) to return a list of all the numbers in the s-expression s-exp. s-exp may be an atom, a list, or a list of s-expressions.
>
> Try the following:
>
> (defun collect-numbers (s-exp)
> (collect-numbers-helper s-exp nil))
>
> (defun collect-numbers-helper (s-exp results)
> ...
> )
>
While all reasonably simple efficient answers are fine in my class, I'm
surprised no one has mentioned mapcan yet.