Hi all
I am at the bottom of the Lisp learning curve, I wonder if anyone can
help. Please note that this *is not* a homework problem. I have also
Googled and searched the c.l.l FAQ for the answer, but didn't find it.
I have written a simple list filter, as follows:
; Filter on a list element (we'll replace the "(equal an-element 1)"
; with a call to a filtering function later)
(defun filter-element (an-element)
(if (equal an-element 1) an-element
nil))
; Filter a list
(defun my-filter (a-list)
(if (endp a-list) nil
(cons (filter-element (car a-list)) (my-filter (cdr a-list)))))
What I want is for "(my-filter '(1 2 3 4))" to return (1). Instead, it
returns (1 nil nil nil). I could use "(remove nil (my-filter '(1 2 3
4)))" to get the desired effect, but I think that I actually want to
build this behaviour into my functions (i.e. it seems wasteful to be
storing empty elements, and I'm surprised that Lisp doesn't remove
them, but then as "nil" also represents false, I guess this is the
reason).
Can anyone tell me how I can achieve the desired behaviour? What have
I misunderstood?
Thanks in advance,
Chris
From: Howard Ding <······@hading.dnsalias.com>
Subject: Re: Newbie: Unwanted NILs in lists
Date:
Message-ID: <m3ad1a4v29.fsf@frisell.localdomain>
·····@microserf.org.uk (C Rose) writes:
>
> ; Filter on a list element (we'll replace the "(equal an-element 1)"
> ; with a call to a filtering function later)
> (defun filter-element (an-element)
> (if (equal an-element 1) an-element
> nil))
>
> ; Filter a list
> (defun my-filter (a-list)
> (if (endp a-list) nil
> (cons (filter-element (car a-list)) (my-filter (cdr a-list)))))
>
> What I want is for "(my-filter '(1 2 3 4))" to return (1). Instead, it
> returns (1 nil nil nil). I could use "(remove nil (my-filter '(1 2 3
> 4)))" to get the desired effect, but I think that I actually want to
> build this behaviour into my functions (i.e. it seems wasteful to be
> storing empty elements, and I'm surprised that Lisp doesn't remove
> them, but then as "nil" also represents false, I guess this is the
> reason).
>
> Can anyone tell me how I can achieve the desired behaviour? What have
> I misunderstood?
>
Only cons when the element passes the filter test. Otherwise just
proceed to the next element. Also note that you're consing on the
result of filter-element, not necessarily the element itself, which
may or may not be what you want when you move to more complicated
functions. Finally, note that Lisp already has a filter function
built-in -- it just happens to be called 'remove-if-not' instead of
'filter'. :-)
--
Howard Ding
<······@hading.dnsalias.com>
C Rose wrote:
> Hi all
>
> I am at the bottom of the Lisp learning curve, I wonder if anyone can
> help. Please note that this *is not* a homework problem. I have also
> Googled and searched the c.l.l FAQ for the answer, but didn't find it.
>
> I have written a simple list filter, as follows:
>
> ; Filter on a list element (we'll replace the "(equal an-element 1)"
> ; with a call to a filtering function later)
> (defun filter-element (an-element)
> (if (equal an-element 1) an-element
> nil))
>
> ; Filter a list
> (defun my-filter (a-list)
> (if (endp a-list) nil
> (cons (filter-element (car a-list)) (my-filter (cdr a-list)))))
>
> What I want is for "(my-filter '(1 2 3 4))" to return (1). Instead, it
> returns (1 nil nil nil). I could use "(remove nil (my-filter '(1 2 3
> 4)))" to get the desired effect, but I think that I actually want to
> build this behaviour into my functions
Don't use unnecesary recursion -- this isn't Scheme. :)
(defun my-filter (a-list)
(loop for e in a-list
when (filter e)
collect it))
> (i.e. it seems wasteful to be
> storing empty elements, and I'm surprised that Lisp doesn't remove
> them, but then as "nil" also represents false, I guess this is the
> reason).
NIL is a perfectly valid list element. Why do you imagine it
shouldn't be allowed to be one (even ignoring its use as 'false')?
Paul
"Paul F. Dietz" <·····@dls.net> writes:
[C Rose:]
> > ; Filter on a list element (we'll replace the "(equal an-element 1)"
> > ; with a call to a filtering function later)
> > (defun filter-element (an-element)
> > (if (equal an-element 1) an-element
> > nil))
> > ; Filter a list
> > (defun my-filter (a-list)
> > (if (endp a-list) nil
> > (cons (filter-element (car a-list)) (my-filter (cdr a-list)))))
[Paul:]
> Don't use unnecesary recursion -- this isn't Scheme. :)
>
> (defun my-filter (a-list)
> (loop for e in a-list
> when (filter e)
> collect it))
Or, for that matter,
(remove-if-not #'filter-element a-list)
But clearly the OP is interested in learning rather than
in filtering lists as such, which seems entirely reasonable.
And while "Don't use unnecessary recursion" is excellent
advice for writing real programs, there's no reason why
someone shouldn't write unnecessarily recursive code to
get the hang of structural induction over Lisp lists.
--
Gareth McCaughan
.sig under construc
C Rose wrote:
> Hi all
>
> I am at the bottom of the Lisp learning curve, I wonder if anyone can
> help. Please note that this *is not* a homework problem. I have also
> Googled and searched the c.l.l FAQ for the answer, but didn't find it.
>
Well...since you've done everything you're supposed to, I guess we'd
better help you with your problem...
> I have written a simple list filter, as follows:
>
> ; Filter on a list element (we'll replace the "(equal an-element 1)"
> ; with a call to a filtering function later)
> (defun filter-element (an-element)
> (if (equal an-element 1) an-element
> nil))
>
> ; Filter a list
> (defun my-filter (a-list)
> (if (endp a-list) nil
> (cons (filter-element (car a-list)) (my-filter (cdr a-list)))))
>
> What I want is for "(my-filter '(1 2 3 4))" to return (1). Instead, it
> returns (1 nil nil nil). I could use "(remove nil (my-filter '(1 2 3
> 4)))" to get the desired effect, but I think that I actually want to
> build this behaviour into my functions (i.e. it seems wasteful to be
> storing empty elements, and I'm surprised that Lisp doesn't remove
> them, but then as "nil" also represents false, I guess this is the
> reason).
>
To make a long story short, you could simplify things and just do this:
* (defun filter-1 (list)
(cond ((null list) '())
((equal (car list) 1) (cons (car list) (filter-1 (cdr list))))
(t (filter-1 (cdr list)))))
FILTER-1
* (filter-1 '(1 2 3 4))
(1)
In order to supply a different filter function:
* (defun my-filter (list)
(cond ((null list) '())
((filter-element (car list))
(cons (car list) (my-filter (cdr list))))
(t (my-filter (cdr list)))))
MY-FILTER
* (defun filter-element (elt)
(if (equal elt 1)
elt
nil))
FILTER-ELEMENT
* (my-filter '(1 2 3 4))
(1)
Finally, if you need to capture the output of the FILTER-ELEMENT
function you can do this:
(defun my-filter (list)
(cond ((null list) '())
(t (let ((f (filter-element (car list))))
(if f
(cons f (my-filter (cdr list)))
(my-filter (cdr list)))) )))
Maybe you are unfamiliar with COND:
http://www.lispworks.com/reference/HyperSpec/Body/m_cond.htm
You might also want to use = rather than EQUAL if you are dealing
strictly with numbers.
Good Luck,
David Sletten
C Rose wrote:
> Hi all
>
> I am at the bottom of the Lisp learning curve, I wonder if anyone can
> help. Please note that this *is not* a homework problem. I have also
> Googled and searched the c.l.l FAQ for the answer, but didn't find it.
>
> I have written a simple list filter, as follows:
>
> ; Filter on a list element (we'll replace the "(equal an-element 1)"
> ; with a call to a filtering function later)
> (defun filter-element (an-element)
> (if (equal an-element 1) an-element
> nil))
>
> ; Filter a list
> (defun my-filter (a-list)
> (if (endp a-list) nil
> (cons (filter-element (car a-list)) (my-filter (cdr a-list)))))
>
> What I want is for "(my-filter '(1 2 3 4))" to return (1). Instead, it
> returns (1 nil nil nil). I could use "(remove nil (my-filter '(1 2 3
> 4)))" to get the desired effect, but I think that I actually want to
> build this behaviour into my functions (i.e. it seems wasteful to be
> storing empty elements, and I'm surprised that Lisp doesn't remove
> them, but then as "nil" also represents false, I guess this is the
> reason).
>
> Can anyone tell me how I can achieve the desired behaviour? What have
> I misunderstood?
Second Q first: Not much have you misunderstood. I think the Real
Problem is not fully grasping (until now) that nil is a perfectly valid
Lisp object, so:
(list nil nil nil)
...does indeed create a hefty structure with three cons cells. This
characteristic of nil (of Lisp, actually) is vital. We cannot just have
the language throwing structure away-- maybe nil is a placeholder in a
list, like zero in a number. 2004 becomes 24 without zero, and then i do
not have to pay to see mel gibson's movie, i can see the sermon on the
mount live, Pythonista big noses aside. but i digress.
As for achieving the desired behavior, well, you /do/ want to throw away
nil filter results, so you have to write the code. This, btw, is
something that comes up quite a bit in Lisp programming, and others have
offered lotsa good ways. loop is the way to go since it offers a way to
throw things away (when-collect), but as a newbie interested in getting
a feel for Lisp you might want to go with one of the solutions that
looks like:
when list not nil
let temp (filter-element (car list))
if temp
(cons temp ...recursion)
...recursion
A common trick is to use the fact that:
(append nil nil nil) => nil
This is not "throwing away" structure if you know what append is
advertised to do, and you can use that to avoid the double reference
above with:
(append (when temp (list temp))
...recursion)
kenny
--
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
·····@microserf.org.uk (C Rose) writes:
> Hi all
>
> I am at the bottom of the Lisp learning curve, I wonder if anyone can
> help. Please note that this *is not* a homework problem. I have also
> Googled and searched the c.l.l FAQ for the answer, but didn't find it.
>
> I have written a simple list filter, as follows:
>
> ; Filter on a list element (we'll replace the "(equal an-element 1)"
> ; with a call to a filtering function later)
> (defun filter-element (an-element)
> (if (equal an-element 1) an-element
> nil))
>
> ; Filter a list
> (defun my-filter (a-list)
> (if (endp a-list) nil
> (cons (filter-element (car a-list)) (my-filter (cdr a-list)))))
>
> What I want is for "(my-filter '(1 2 3 4))" to return (1). Instead, it
> returns (1 nil nil nil). I could use "(remove nil (my-filter '(1 2 3
> 4)))" to get the desired effect, but I think that I actually want to
> build this behaviour into my functions (i.e. it seems wasteful to be
> storing empty elements, and I'm surprised that Lisp doesn't remove
> them, but then as "nil" also represents false, I guess this is the
> reason).
Why would you expect it to remove them? I can think of two possible
reasons.
1 You might be thinking "NIL is the empty list; adding an
empty list to a list should leave it unchanged."
In this case, what you need to know is that CONS doesn't
mean "combine the elements of these two lists" (that's
APPEND), it means "make a new list with *this* as first
element and *that* as tail". The empty list can perfectly
well be an element of another list.
2 You might be thinking that somehow the computer should
know that you don't want those elements in the list, even
though you haven't told it so.
In this case, what you need to know is that when you're
programming a computer, it will do precisely what you
tell it to do, not what you *want* it to do. A lot of
the work in becoming a good programmer is learning to
be absolutely explicit (in your head, and in what you
write) about the difference between the two.
In your MY-FILTER function above, you *always* cons the
result of calling FILTER-ELEMENT onto the front of the
list you're building. How could it *not* get put there,
then?
> Can anyone tell me how I can achieve the desired behaviour? What have
> I misunderstood?
How about this? (I've deliberately not actually written the
code, but turning it into a Lisp function shouldn't be hard.)
Filtering the empty list yields the empty list.
Filtering any other list yields either
- the first element, plus the result of filtering
the tail, or
- just the result of filtering the tail,
depending on whether that first element satisfies
the condition.
--
Gareth McCaughan
.sig under construc
On 17 Apr 2004 05:40:28 -0700, ·····@microserf.org.uk (C Rose) wrote:
> I am at the bottom of the Lisp learning curve, I wonder if anyone
> can help. Please note that this *is not* a homework problem. I have
> also Googled and searched the c.l.l FAQ for the answer, but didn't
> find it.
>
> I have written a simple list filter, as follows:
>
> ; Filter on a list element (we'll replace the "(equal an-element 1)"
> ; with a call to a filtering function later)
> (defun filter-element (an-element)
> (if (equal an-element 1) an-element
> nil))
>
> ; Filter a list
> (defun my-filter (a-list)
> (if (endp a-list) nil
> (cons (filter-element (car a-list)) (my-filter (cdr a-list)))))
>
> What I want is for "(my-filter '(1 2 3 4))" to return (1). Instead,
> it returns (1 nil nil nil). I could use "(remove nil (my-filter '(1
> 2 3 4)))" to get the desired effect, but I think that I actually
> want to build this behaviour into my functions (i.e. it seems
> wasteful to be storing empty elements, and I'm surprised that Lisp
> doesn't remove them, but then as "nil" also represents false, I
> guess this is the reason).
>
> Can anyone tell me how I can achieve the desired behaviour? What have
> I misunderstood?
You were pretty close. You could, e.g., use REMOVE-IF-NOT:
* (defun my-filter (filter-fn a-list)
(remove-if-not filter-fn a-list))
MY-FILTER
* (my-filter #'oddp '(1 2 3 4 5 6))
(1 3 5)
Of course, there are many ways to skin a cat. The next one might cons
a little bit more but it shows another idiom:
* (defun my-filter (filter-fn a-list)
(mapcan (lambda (x)
(and (funcall filter-fn x)
(list x)))
a-list))
MY-FILTER
* (my-filter #'oddp '(1 2 3 4 5 6))
(1 3 5)
HTH,
Edi.
C Rose <·····@microserf.org.uk> wrote:
> (defun filter-element (an-element)
> (if (equal an-element 1) an-element
> nil))
> ; Filter a list
> (defun my-filter (a-list)
> (if (endp a-list) nil
> (cons (filter-element (car a-list)) (my-filter (cdr a-list)))))
(defun filter (list)
(cond ((endp list)
nil)
((= (car list) 1)
(cons (car list) (filter (cdr list))))
(t
(filter (cdr list)))))
If you don't want the NILs there, don't put them there. ;)
The reason NILs aren't dropped has nothing to do with NIL being
used for false as well, but everything to do with what lists
actually are.
The list
(1 2 3)
is (cons 1 (cons 2 (cons 3 nil))),
or [1 | *-]->[2 | *-]->[3 | nil].
and the list
(1 nil nil)
is (cons 1 (cons nil (cons nil nil))),
or [1 | *-]-> [nil | *-]-> [nil | *-]-> [nil | nil].
Where [x | y] represents (cons x y), and is alternatively written
with the pointer to y as [x | *-]-> y. ASCII art really sucks for
this, but all decent books on lisp explain this.
Cheers,
-- Nikodemus
·········@random-state.net wrote:
> (1 nil nil)
>
> is (cons 1 (cons nil (cons nil nil))),
>
> or [1 | *-]-> [nil | *-]-> [nil | *-]-> [nil | nil].
Ugggh. Sorry, that should be
[1 | *-]-> [nil | *-]-> [nil | nil]
of course, as Pekka Niirainen was kind enough to point out.
I'll just shut up. ,)
Cheers,
-- Nikodemus
From: Pekka Niiranen
Subject: Re: Newbie: Unwanted NILs in lists: I Just can not get it.
Date:
Message-ID: <40825755.9020202@wlanmail.com>
Was this a bug in explanation or:
If list (1 2 3) is
(cons 1 (cons 2 (cons 3 nil))) and is in ascii
[1 | *-]->[2 | *-]->[3 | nil]
Why then
(1 nil nil) is
(cons 1 (cons nil (cons nil nil))) is NOT in ascii
[1 | *-]-> [nil | *-]-> [nil | nil]
-pekka-
·········@random-state.net wrote:
> C Rose <·····@microserf.org.uk> wrote:
>
>
>>(defun filter-element (an-element)
>> (if (equal an-element 1) an-element
>> nil))
>
>
>>; Filter a list
>>(defun my-filter (a-list)
>> (if (endp a-list) nil
>> (cons (filter-element (car a-list)) (my-filter (cdr a-list)))))
>
>
> (defun filter (list)
> (cond ((endp list)
> nil)
> ((= (car list) 1)
> (cons (car list) (filter (cdr list))))
> (t
> (filter (cdr list)))))
>
> If you don't want the NILs there, don't put them there. ;)
>
> The reason NILs aren't dropped has nothing to do with NIL being
> used for false as well, but everything to do with what lists
> actually are.
>
> The list
>
> (1 2 3)
>
> is (cons 1 (cons 2 (cons 3 nil))),
>
> or [1 | *-]->[2 | *-]->[3 | nil].
>
> and the list
>
> (1 nil nil)
>
> is (cons 1 (cons nil (cons nil nil))),
>
> or [1 | *-]-> [nil | *-]-> [nil | *-]-> [nil | nil].
>
> Where [x | y] represents (cons x y), and is alternatively written
> with the pointer to y as [x | *-]-> y. ASCII art really sucks for
> this, but all decent books on lisp explain this.
>
> Cheers,
>
> -- Nikodemus
In article <················@wlanmail.com>,
Pekka Niiranen <··············@wlanmail.com> wrote:
> Was this a bug in explanation or:
>
> If list (1 2 3) is
> (cons 1 (cons 2 (cons 3 nil))) and is in ascii
> [1 | *-]->[2 | *-]->[3 | nil]
>
> Why then
> (1 nil nil) is
> (cons 1 (cons nil (cons nil nil))) is NOT in ascii
> [1 | *-]-> [nil | *-]-> [nil | nil]
No, that's correct.
Perhaps the previous poster originally meant to have another element in
the list and changed his mond halfway?
Or, it could be a point of confusion about nil. Nil is often
represented as a well known cons cell where both the car and cdr point
to itself, to avoid a test and special-case code in car and cdr.
-- Bruce
Your code is very close to working.
Replace
(defun filter-element (an-element)
(if (equal an-element 1) an-element
nil))
by
(defun filter-element (an-element)
(if (equal an-element 1)(list an-element)
nil))
that is wrap the element you want to keep in a list.
Then replace
(defun my-filter (a-list)
(if (endp a-list) nil
(cons (filter-element (car a-list)) (my-filter (cdr a-list)))))
by
(defun my-filter (a-list)
(if (endp a-list) nil
(append (filter-element (car a-list))
(my-filter (cdr a-list)))))
that is append instead of cons. Then
(my-filter '(1 2 3 4)) => (1)
The approach you are taking is seen to best effect when
the filter-element function sometimes contributes more than
one element to the final list. Consider
(defun vary-odd(n)
(if (oddp n)
(make-list n :initial-element n)))
1 -> (1)
2 -> ()
3 -> (3 3 3)
4 -> ()
etc
Using the built in mapcan in place of my-filter
(mapcan (function vary-odd) '(1 2 3 4 5))
=> (1 3 3 3 5 5 5 5 5)
Other posters have already given you a weeks worth of
stuff to try out. Have fun.
Alan Crowe
Edinburgh
Scotland