Folks-
I'm a newbie to Lisp. I am looking for suggestions, alternatives to the
brief code below. See what you think.
The following is taken from the problem set in chapter 2 of Paul Graham's
"ANSI Common Lisp":
8(b) Give iterative and recursive versions of a function that takes a symbol
and a list and returns the number of times that symbol appears in the list.
Here are my iterative and recursive solutions:
Iterative: (defun it-searchlist (a x)
(let ((occur 0))
(dolist (obj x)
(if (equal obj a)
(setf occur (+ occur 1))))
occur))
Recursive: (defun rec-searchlist (a x)
(let ((count 0))
(defun rec-sli (a x)
(if (equal (car x) a)
(setf count (+ count 1)))
(if (not (null (cdr x)))
(rec-sli a (cdr x)))
count))
(rec-sli a x))
The recursive code seems like a kludge to me (defining one function within
another to avoid resetting the counter at each recursion). Anyone have a
suggestion on how to make it cleaner?
M. Bartlett
From: John Clonts
Subject: Re: Anyone have a better solution? (code included)
Date:
Message-ID: <9h0ep50mfr@enews1.newsguy.com>
I'm pretty much a novice too but I like this approach:
(defun searchlist (s list &optional (count 0))
(if (null list)
count
(searchlist s (cdr list)(+ count (if (eql s (car list)) 1 0)))))
Cheers,
John
mgbartlett <··········@netzero.net> wrote in message
·················@coward.ks.cc.utah.edu...
> Folks-
>
> I'm a newbie to Lisp. I am looking for suggestions, alternatives to the
> brief code below. See what you think.
>
> The following is taken from the problem set in chapter 2 of Paul Graham's
> "ANSI Common Lisp":
>
> 8(b) Give iterative and recursive versions of a function that takes a
symbol
> and a list and returns the number of times that symbol appears in the
list.
>
> Here are my iterative and recursive solutions:
>
> Iterative: (defun it-searchlist (a x)
> (let ((occur 0))
> (dolist (obj x)
> (if (equal obj a)
> (setf occur (+ occur 1))))
> occur))
>
> Recursive: (defun rec-searchlist (a x)
> (let ((count 0))
> (defun rec-sli (a x)
> (if (equal (car x) a)
> (setf count (+ count 1)))
> (if (not (null (cdr x)))
> (rec-sli a (cdr x)))
> count))
> (rec-sli a x))
>
> The recursive code seems like a kludge to me (defining one function within
> another to avoid resetting the counter at each recursion). Anyone have a
> suggestion on how to make it cleaner?
>
> M. Bartlett
>
>
>
From: Barry Margolin
Subject: Re: Anyone have a better solution? (code included)
Date:
Message-ID: <bxNY6.40$uB1.246@burlma1-snr2>
In article <············@coward.ks.cc.utah.edu>,
mgbartlett <··········@netzero.net> wrote:
>Folks-
>
>I'm a newbie to Lisp. I am looking for suggestions, alternatives to the
>brief code below. See what you think.
>
>The following is taken from the problem set in chapter 2 of Paul Graham's
>"ANSI Common Lisp":
>
>8(b) Give iterative and recursive versions of a function that takes a symbol
>and a list and returns the number of times that symbol appears in the list.
>
>Here are my iterative and recursive solutions:
>
>Iterative: (defun it-searchlist (a x)
> (let ((occur 0))
> (dolist (obj x)
> (if (equal obj a)
> (setf occur (+ occur 1))))
> occur))
>
> Recursive: (defun rec-searchlist (a x)
> (let ((count 0))
> (defun rec-sli (a x)
> (if (equal (car x) a)
> (setf count (+ count 1)))
> (if (not (null (cdr x)))
> (rec-sli a (cdr x)))
> count))
> (rec-sli a x))
It would sure make it easier to help you if you indented your code properly
before posting.
>The recursive code seems like a kludge to me (defining one function within
>another to avoid resetting the counter at each recursion). Anyone have a
>suggestion on how to make it cleaner?
Here's a hint: the following should probably appear somewhere in the code:
(1+ (rec-searchlist a (cdr x)))
If you're trying to make it tail-recursive, then you need the internal
function. However, internal functions should normally be defined using
FLET, not DEFUN, since you don't need to define a top-level function in
this case. But in this case, you should pass the counter as an argument:
(defun tail-rec-searchlist (a x)
(flet ((rec-sli (x running-total)
(if (null x)
running-total
(rec-sli (cdr x)
(if (equal (car x) a)
(1+ running-total)
running-total)))))
(rec-sli x 0)))
--
Barry Margolin, ······@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Tim Moore
Subject: Re: Anyone have a better solution? (code included)
Date:
Message-ID: <9h0946$iaa$0@216.39.145.192>
On Fri, 22 Jun 2001, mgbartlett wrote:
> 8(b) Give iterative and recursive versions of a function that takes a symbol
> and a list and returns the number of times that symbol appears in the list.
>
> Here are my iterative and recursive solutions:
>
> Iterative: (defun it-searchlist (a x)
> (let ((occur 0))
> (dolist (obj x)
> (if (equal obj a)
> (setf occur (+ occur 1))))
> occur))
Pretty straightfward. Your indentation is a bit funky, but I'll chalk
that up to the posting software. You shouldn't use EQUAL without good
reason; I'd use EQL or even EQ if I was certain that I only cared about
symbols (as opposed to numbers and characters too). Maybe you don't know
about this yet, but I'd increment the variable using INCF.
> Recursive: (defun rec-searchlist (a x)
> (let ((count 0))
> (defun rec-sli (a x)
> (if (equal (car x) a)
> (setf count (+ count 1)))
> (if (not (null (cdr x)))
> (rec-sli a (cdr x)))
> count))
> (rec-sli a x))
>
> The recursive code seems like a kludge to me (defining one function within
> another to avoid resetting the counter at each recursion). Anyone have a
> suggestion on how to make it cleaner?
Yup. First off, DEFUN inside a function is bad form unless you have a
really good reason for it. Use LABELS instead.
You're not thinking about the problem recursively. You know you can
traverse the list recursively, but you're hung up on your iterative
solution that uses a count variable. What's a recursive restatement of
the original problem?
If the list is empty, the result is 0 (obvious base case);
If the first element is equal to the symbol, the result is 1 plus the
result for the rest of the list;
Otherwise the result is the result for the rest of the list.
Voila:
(defun rec-searchlist (a x)
(cond ((null x)
0)
((eql a (car x))
(1+ (rec-searchlist a (cdr x))))
(t (rec-searchlist a (cdr x)))))
Tim
"mgbartlett" <··········@netzero.net> wrote in message
·················@coward.ks.cc.utah.edu...
>
> Recursive: (defun rec-searchlist (a x)
> (let ((count 0))
> (defun rec-sli (a x)
> (if (equal (car x) a)
> (setf count (+ count 1)))
> (if (not (null (cdr x)))
> (rec-sli a (cdr x)))
> count))
> (rec-sli a x))
>
> The recursive code seems like a kludge to me (defining one function within
> another to avoid resetting the counter at each recursion). Anyone have a
> suggestion on how to make it cleaner?
check flet, as in function-let. It allows you to define a function locally
which is exactly what you are trying to do here. (which is actually very
appropriate for your problem, not at all a kludge!)
Coby
From: Barry Margolin
Subject: Re: Anyone have a better solution? (code included)
Date:
Message-ID: <G3OY6.45$uB1.380@burlma1-snr2>
In article <·······················@typhoon.tampabay.rr.com>,
Coby Beck <·····@mercury.bc.ca> wrote:
>check flet, as in function-let. It allows you to define a function locally
>which is exactly what you are trying to do here. (which is actually very
>appropriate for your problem, not at all a kludge!)
You made the same stupid mistake I did. Since the internal function is
recursive, it has to be defined using LABELS rather than FLET.
--
Barry Margolin, ······@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Bulent Murtezaoglu
Subject: Re: Anyone have a better solution? (code included)
Date:
Message-ID: <8766dofdo4.fsf@nkapi.internal>
>>>>> "CB" == Coby Beck <·····@mercury.bc.ca> writes:
[rescursive local function example elided]
CB> check flet, as in function-let.
Minor nit: I think he need flet's brother, labels for this as the
function he wants to define is recursive. The hyperspec explanation
might not make this obvious to a new lisper as it does not mention
recursion explicitly, but talks about the scope of the binding for
the flet'ed function name:
http://www.xanalys.com/software_tools/reference/HyperSpec/Body/speope_fletcm_scm_macrolet.html
cheers,
BM
From: Peter Buchlovsky
Subject: Re: Anyone have a better solution? (code included)
Date:
Message-ID: <877ky3b21w.fsf@cs.bham.ac.uk>
"mgbartlett" <··········@netzero.net> writes:
> Folks-
>
> I'm a newbie to Lisp. I am looking for suggestions, alternatives to the
> brief code below. See what you think.
>
> The following is taken from the problem set in chapter 2 of Paul Graham's
> "ANSI Common Lisp":
>
> 8(b) Give iterative and recursive versions of a function that takes a symbol
> and a list and returns the number of times that symbol appears in the list.
>
> Here are my iterative and recursive solutions:
>
> Iterative: (defun it-searchlist (a x)
> (let ((occur 0))
> (dolist (obj x)
> (if (equal obj a)
> (setf occur (+ occur 1))))
> occur))
I have a couple of suggestions on how to improve this code. When
comparing symbols use EQ since symbols have identity. Similarly use
EQL when numbers (as well as symbols) are involved and so on. Paul
Graham probably lists the comparison predicates and their differences
somewhere in his book. The other suggestion is simply stylistic, use
INCF when incrementing a counter as it is simpler than the equivalent
SETF form. It is also preferable to use WHEN instead of IF when there
is no else clause. Here is my definition for the function above:
(defun it-searchlist (symbol list)
(let ((count 0))
(dolist (item list)
(when (eq item symbol)
(incf count)))
count))
> Recursive: (defun rec-searchlist (a x)
> (let ((count 0))
> (defun rec-sli (a x)
> (if (equal (car x) a)
> (setf count (+ count 1)))
> (if (not (null (cdr x)))
> (rec-sli a (cdr x)))
> count))
> (rec-sli a x))
>
> The recursive code seems like a kludge to me (defining one function within
> another to avoid resetting the counter at each recursion). Anyone have a
> suggestion on how to make it cleaner?
You should use FLET or LABELS to define a local function but I think
you are on the wrong track with the above definition. You should be
using the stack when incrementing the counter. Either on your way down
the stack or on your way up (the second is preferable since it takes
advantage of tail recursion elimination in those implementations that
have it.) Here are the two versions:
(defun rec-searchlist (symbol list)
(cond ((null list) 0)
((eq (first list) symbol) (1+ (rec-searchlist symbol (rest list))))
(t (rec-searchlist symbol (rest list)))))
(defun rec-searchlist (symbol list &optional (count 0))
(if (null list)
count
(if (eq (first list) symbol)
(rec-searchlist symbol (rest list) (1+ count))
(rec-searchlist symbol (rest list) count))))
Alternatively, if you don't like using &optional in your toplevel
function, use LABELS.
(defun rec-searchlist (symbol list)
(labels ((rec-sli (symbol list count)
(if (null list)
count
(if (eq (first list) symbol)
(rec-sli symbol (rest list) (1+ count))
(rec-sli symbol (rest list) count)))))
(rec-sli symbol list 0)))
Regards,
Peter
On 24 Jun 2001 16:23:27 -0400, Huaiyuan wrote:
> "mgbartlett" <··········@netzero.net> writes:
>> Iterative: (defun it-searchlist (a x)
>> (let ((occur 0))
>> (dolist (obj x)
>> (if (equal obj a)
>> (setf occur (+ occur 1))))
>> occur))
> (defun it-searchlist (a x)
> (loop :for i :in x :counting (eq a i)))
[Argh! Not another one who uses keywords in LOOP!]
(count a x)
--
In modern physics, the more logical you are, the more wrong you are.
-- Lama Govinda
(setq reply-to
(concatenate 'string "Paul Foley " "<mycroft" '(··@) "actrix.gen.nz>"))
From: Kent M Pitman
Subject: keywords in loop [Re: Anyone have a better solution? (code included)]
Date:
Message-ID: <sfw4rt5mfm7.fsf_-_@world.std.com>
Paul Foley <·······@actrix.gen.nz> writes:
> On 24 Jun 2001 16:23:27 -0400, Huaiyuan wrote:
>
> > (defun it-searchlist (a x)
> > (loop :for i :in x :counting (eq a i)))
>
> [Argh! Not another one who uses keywords in LOOP!]
Actually, I don't think this is so bad. It looks ugly to me, too, but I
think mostly from unfamiliarity. The truth is that if we had defined the
language to do that, it would probably have been better error checking
and fewer stray symbols cluttering things up all over...
From: Thomas F. Burdick
Subject: Re: keywords in loop [Re: Anyone have a better solution? (code included)]
Date:
Message-ID: <xcvithkpfds.fsf@famine.OCF.Berkeley.EDU>
Kent M Pitman <······@world.std.com> writes:
> Paul Foley <·······@actrix.gen.nz> writes:
>
> > On 24 Jun 2001 16:23:27 -0400, Huaiyuan wrote:
> >
> > > (defun it-searchlist (a x)
> > > (loop :for i :in x :counting (eq a i)))
> >
> > [Argh! Not another one who uses keywords in LOOP!]
>
> Actually, I don't think this is so bad. It looks ugly to me, too, but I
> think mostly from unfamiliarity. The truth is that if we had defined the
> language to do that, it would probably have been better error checking
> and fewer stray symbols cluttering things up all over...
I love loop forms using keywords. My emacs colors the keywords
differently, which makes the code more readable.