Asp Forum - Recursion - comp.lang.lisp

gengyangcai

11/7/2015 6:02:00 AM

This is a recursive function :

(defun our-member (obj 1st)
(if (null 1st)
nil
(if (eql (car 1st) obj)
1st
(our-member obj (cdr 1st)))))

Here it is in action :

> (our-member 'b '(a b c))
(B C)
> (our-member 'z '(a b c))
NIL

This is a tough piece of code --- how do I understand it ?

13 Answers

Pascal J. Bourguignon

11/7/2015 6:39:00 AM

CAI GENGYANG <gengyangcai@gmail.com> writes:

> This is a recursive function :
>
> (defun our-member (obj 1st)
> (if (null 1st)
> nil
> (if (eql (car 1st) obj)
> 1st
> (our-member obj (cdr 1st)))))
>
> Here it is in action :
>
>> (our-member 'b '(a b c))
> (B C)
>> (our-member 'z '(a b c))
> NIL
>
>
> This is a tough piece of code --- how do I understand it ?

By reading it.

You may also try it, notably tracing it:

(declaim (notinline our-member))
(defun our-member (obj 1st)
(if (null 1st)
nil
(if (eql (car 1st) obj)
1st
(our-member obj (cdr 1st)))))
(trace our-member)

cl-user> (our-member 3 '(1 2 3 4 5))
0> Calling (our-member 3 (1 2 3 4 5))
1> Calling (our-member 3 (2 3 4 5))
2> Calling (our-member 3 (3 4 5))
<2 our-member returned (3 4 5)
<1 our-member returned (3 4 5)
<0 our-member returned (3 4 5)
(3 4 5)
cl-user>

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.â? -- Carl Bass CEO Autodesk

gengyangcai

11/7/2015 11:26:00 AM

From what I understand about the different terms :

(defun our-member (obj 1st) ------ (1)
(if (null 1st) ------ (2)
nil ------ (3)
(if (eql (car 1st) obj) ------ (4)
1st ------ (5)
(our-member obj (cdr 1st))))) ------ (6)

Line 1 : Defines a function called our-member that takes 2 inputs (obj and 1st)
Line 2 : null returns t if the object is the empty list, otherwise returns nil
Line 3 : nil --- First it means empty list. Second it means false and is the value returned when a true-or-false test tests false.
Line 4 : eq1 is a predicate that tests whether its two arguments are identical
Line 5 : Just an input called 1st
Line 6 : cdr is everything after the 1st element

This is the first time I've been so lost ... I am totally clueless what the entire piece of code means. Must be the pizza I just ate lol ...

On Saturday, November 7, 2015 at 2:38:42 PM UTC+8, informatimago wrote:
> CAI GENGYANG <gengyangcai@gmail.com> writes:
>
> > This is a recursive function :
> >
> > (defun our-member (obj 1st)
> > (if (null 1st)
> > nil
> > (if (eql (car 1st) obj)
> > 1st
> > (our-member obj (cdr 1st)))))
> >
> > Here it is in action :
> >
> >> (our-member 'b '(a b c))
> > (B C)
> >> (our-member 'z '(a b c))
> > NIL
> >
> >
> > This is a tough piece of code --- how do I understand it ?
>
> By reading it.
>
> You may also try it, notably tracing it:
>
> (declaim (notinline our-member))
> (defun our-member (obj 1st)
> (if (null 1st)
> nil
> (if (eql (car 1st) obj)
> 1st
> (our-member obj (cdr 1st)))))
> (trace our-member)
>
> cl-user> (our-member 3 '(1 2 3 4 5))
> 0> Calling (our-member 3 (1 2 3 4 5))
> 1> Calling (our-member 3 (2 3 4 5))
> 2> Calling (our-member 3 (3 4 5))
> <2 our-member returned (3 4 5)
> <1 our-member returned (3 4 5)
> <0 our-member returned (3 4 5)
> (3 4 5)
> cl-user>
>
> --
> __Pascal Bourguignon__ http://www.informat...
> "The factory of the future will have only two employees, a man and a
> dog. The man will be there to feed the dog. The dog will be there to
> keep the man from touching the equipment." -- Carl Bass CEO Autodesk

Teemu Likonen

11/7/2015 12:44:00 PM

CAI GENGYANG [2015-11-06 22:01:50-08] wrote:

> (defun our-member (obj 1st)
> (if (null 1st)
> nil
> (if (eql (car 1st) obj)
> 1st
> (our-member obj (cdr 1st)))))

> This is a tough piece of code --- how do I understand it ?

We could write the same thing with COND and use variable name "list"
instead of "1st":

(defun our-member (obj list)
(cond ((null list) nil)
((eql (car list) obj) list)
(t (our-member obj (cdr list)))))

Now let's add some FORMATs that print immediate values:

(defun our-member (obj list)
(declare (optimize (debug 3)))
(format t "'list' is ~S, " list)
(cond ((null list)
(format t "return nil~%")
nil)
((eql (car list) obj)
(format t "'obj' ~S is (car ~S), return 'list' ~:*~S~%"
obj list)
list)
(t
(format t "'obj' ~S is not (car ~S), call 'our-member'~%"
obj list)
(our-member obj (cdr list)))))

Let's also TRACE function calls:

(trace our-member)

Finally try it:

CL-USER> (our-member 3 '(1 2 3 4 5))

0: (OUR-MEMBER 3 (1 2 3 4 5))
'list' is (1 2 3 4 5), 'obj' 3 is not (car (1 2 3 4 5)), call 'our-member'
1: (OUR-MEMBER 3 (2 3 4 5))
'list' is (2 3 4 5), 'obj' 3 is not (car (2 3 4 5)), call 'our-member'
2: (OUR-MEMBER 3 (3 4 5))
'list' is (3 4 5), 'obj' 3 is (car (3 4 5)), return 'list' (3 4 5)
2: OUR-MEMBER returned (3 4 5)
1: OUR-MEMBER returned (3 4 5)
0: OUR-MEMBER returned (3 4 5)
(3 4 5)

CL-USER> (our-member 0 '(1 2 3 4 5))

0: (OUR-MEMBER 0 (1 2 3 4 5))
'list' is (1 2 3 4 5), 'obj' 0 is not (car (1 2 3 4 5)), call 'our-member'
1: (OUR-MEMBER 0 (2 3 4 5))
'list' is (2 3 4 5), 'obj' 0 is not (car (2 3 4 5)), call 'our-member'
2: (OUR-MEMBER 0 (3 4 5))
'list' is (3 4 5), 'obj' 0 is not (car (3 4 5)), call 'our-member'
3: (OUR-MEMBER 0 (4 5))
'list' is (4 5), 'obj' 0 is not (car (4 5)), call 'our-member'
4: (OUR-MEMBER 0 (5))
'list' is (5), 'obj' 0 is not (car (5)), call 'our-member'
5: (OUR-MEMBER 0 NIL)
'list' is NIL, return nil
5: OUR-MEMBER returned NIL
4: OUR-MEMBER returned NIL
3: OUR-MEMBER returned NIL
2: OUR-MEMBER returned NIL
1: OUR-MEMBER returned NIL
0: OUR-MEMBER returned NIL
NIL

gengyangcai

11/7/2015 1:07:00 PM

Wow,

Lisp is really hard to learn alone from scratch ... and I don't know a single Lisp programmer in Singapore whom I can learn from ...

On Saturday, November 7, 2015 at 8:43:40 PM UTC+8, Teemu Likonen wrote:
> CAI GENGYANG [2015-11-06 22:01:50-08] wrote:
>
> > (defun our-member (obj 1st)
> > (if (null 1st)
> > nil
> > (if (eql (car 1st) obj)
> > 1st
> > (our-member obj (cdr 1st)))))
>
> > This is a tough piece of code --- how do I understand it ?
>
> We could write the same thing with COND and use variable name "list"
> instead of "1st":
>
> (defun our-member (obj list)
> (cond ((null list) nil)
> ((eql (car list) obj) list)
> (t (our-member obj (cdr list)))))
>
> Now let's add some FORMATs that print immediate values:
>
> (defun our-member (obj list)
> (declare (optimize (debug 3)))
> (format t "'list' is ~S, " list)
> (cond ((null list)
> (format t "return nil~%")
> nil)
> ((eql (car list) obj)
> (format t "'obj' ~S is (car ~S), return 'list' ~:*~S~%"
> obj list)
> list)
> (t
> (format t "'obj' ~S is not (car ~S), call 'our-member'~%"
> obj list)
> (our-member obj (cdr list)))))
>
> Let's also TRACE function calls:
>
> (trace our-member)
>
> Finally try it:
>
> CL-USER> (our-member 3 '(1 2 3 4 5))
>
> 0: (OUR-MEMBER 3 (1 2 3 4 5))
> 'list' is (1 2 3 4 5), 'obj' 3 is not (car (1 2 3 4 5)), call 'our-member'
> 1: (OUR-MEMBER 3 (2 3 4 5))
> 'list' is (2 3 4 5), 'obj' 3 is not (car (2 3 4 5)), call 'our-member'
> 2: (OUR-MEMBER 3 (3 4 5))
> 'list' is (3 4 5), 'obj' 3 is (car (3 4 5)), return 'list' (3 4 5)
> 2: OUR-MEMBER returned (3 4 5)
> 1: OUR-MEMBER returned (3 4 5)
> 0: OUR-MEMBER returned (3 4 5)
> (3 4 5)
>
> CL-USER> (our-member 0 '(1 2 3 4 5))
>
> 0: (OUR-MEMBER 0 (1 2 3 4 5))
> 'list' is (1 2 3 4 5), 'obj' 0 is not (car (1 2 3 4 5)), call 'our-member'
> 1: (OUR-MEMBER 0 (2 3 4 5))
> 'list' is (2 3 4 5), 'obj' 0 is not (car (2 3 4 5)), call 'our-member'
> 2: (OUR-MEMBER 0 (3 4 5))
> 'list' is (3 4 5), 'obj' 0 is not (car (3 4 5)), call 'our-member'
> 3: (OUR-MEMBER 0 (4 5))
> 'list' is (4 5), 'obj' 0 is not (car (4 5)), call 'our-member'
> 4: (OUR-MEMBER 0 (5))
> 'list' is (5), 'obj' 0 is not (car (5)), call 'our-member'
> 5: (OUR-MEMBER 0 NIL)
> 'list' is NIL, return nil
> 5: OUR-MEMBER returned NIL
> 4: OUR-MEMBER returned NIL
> 3: OUR-MEMBER returned NIL
> 2: OUR-MEMBER returned NIL
> 1: OUR-MEMBER returned NIL
> 0: OUR-MEMBER returned NIL
> NIL

gengyangcai

11/7/2015 1:14:00 PM

Maybe I should switch to learning Python instead. I have a friend who programs in Python ...much easier to get help ... this is really slow going ..

On Saturday, November 7, 2015 at 9:07:32 PM UTC+8, CAI GENGYANG wrote:
> Wow,
>
> Lisp is really hard to learn alone from scratch ... and I don't know a single Lisp programmer in Singapore whom I can learn from ...
>
>
> On Saturday, November 7, 2015 at 8:43:40 PM UTC+8, Teemu Likonen wrote:
> > CAI GENGYANG [2015-11-06 22:01:50-08] wrote:
> >
> > > (defun our-member (obj 1st)
> > > (if (null 1st)
> > > nil
> > > (if (eql (car 1st) obj)
> > > 1st
> > > (our-member obj (cdr 1st)))))
> >
> > > This is a tough piece of code --- how do I understand it ?
> >
> > We could write the same thing with COND and use variable name "list"
> > instead of "1st":
> >
> > (defun our-member (obj list)
> > (cond ((null list) nil)
> > ((eql (car list) obj) list)
> > (t (our-member obj (cdr list)))))
> >
> > Now let's add some FORMATs that print immediate values:
> >
> > (defun our-member (obj list)
> > (declare (optimize (debug 3)))
> > (format t "'list' is ~S, " list)
> > (cond ((null list)
> > (format t "return nil~%")
> > nil)
> > ((eql (car list) obj)
> > (format t "'obj' ~S is (car ~S), return 'list' ~:*~S~%"
> > obj list)
> > list)
> > (t
> > (format t "'obj' ~S is not (car ~S), call 'our-member'~%"
> > obj list)
> > (our-member obj (cdr list)))))
> >
> > Let's also TRACE function calls:
> >
> > (trace our-member)
> >
> > Finally try it:
> >
> > CL-USER> (our-member 3 '(1 2 3 4 5))
> >
> > 0: (OUR-MEMBER 3 (1 2 3 4 5))
> > 'list' is (1 2 3 4 5), 'obj' 3 is not (car (1 2 3 4 5)), call 'our-member'
> > 1: (OUR-MEMBER 3 (2 3 4 5))
> > 'list' is (2 3 4 5), 'obj' 3 is not (car (2 3 4 5)), call 'our-member'
> > 2: (OUR-MEMBER 3 (3 4 5))
> > 'list' is (3 4 5), 'obj' 3 is (car (3 4 5)), return 'list' (3 4 5)
> > 2: OUR-MEMBER returned (3 4 5)
> > 1: OUR-MEMBER returned (3 4 5)
> > 0: OUR-MEMBER returned (3 4 5)
> > (3 4 5)
> >
> > CL-USER> (our-member 0 '(1 2 3 4 5))
> >
> > 0: (OUR-MEMBER 0 (1 2 3 4 5))
> > 'list' is (1 2 3 4 5), 'obj' 0 is not (car (1 2 3 4 5)), call 'our-member'
> > 1: (OUR-MEMBER 0 (2 3 4 5))
> > 'list' is (2 3 4 5), 'obj' 0 is not (car (2 3 4 5)), call 'our-member'
> > 2: (OUR-MEMBER 0 (3 4 5))
> > 'list' is (3 4 5), 'obj' 0 is not (car (3 4 5)), call 'our-member'
> > 3: (OUR-MEMBER 0 (4 5))
> > 'list' is (4 5), 'obj' 0 is not (car (4 5)), call 'our-member'
> > 4: (OUR-MEMBER 0 (5))
> > 'list' is (5), 'obj' 0 is not (car (5)), call 'our-member'
> > 5: (OUR-MEMBER 0 NIL)
> > 'list' is NIL, return nil
> > 5: OUR-MEMBER returned NIL
> > 4: OUR-MEMBER returned NIL
> > 3: OUR-MEMBER returned NIL
> > 2: OUR-MEMBER returned NIL
> > 1: OUR-MEMBER returned NIL
> > 0: OUR-MEMBER returned NIL
> > NIL

Pascal J. Bourguignon

11/7/2015 1:30:00 PM

CAI GENGYANG <gengyangcai@gmail.com> writes:

> From what I understand about the different terms :
>
> (defun our-member (obj 1st) ------ (1)
> (if (null 1st) ------ (2)
> nil ------ (3)
> (if (eql (car 1st) obj) ------ (4)
> 1st ------ (5)
> (our-member obj (cdr 1st))))) ------ (6)
>
>
> Line 1 : Defines a function called our-member that takes 2 inputs (obj and 1st)
> Line 2 : null returns t if the object is the empty list, otherwise returns nil
> Line 3 : nil --- First it means empty list. Second it means false and is the value returned when a true-or-false test tests false.
> Line 4 : eq1 is a predicate that tests whether its two arguments are identical
> Line 5 : Just an input called 1st
> Line 6 : cdr is everything after the 1st element
>
>
> This is the first time I've been so lost ... I am totally clueless
> what the entire piece of code means. Must be the pizza I just ate lol
> ...

Yes, but it would be useless to switch to python, it won't be easier to
understand it in python:

def our_member(obj,lst) :
if []==lst :
return []
else :
if lst[0]==obj :
return lst
else :
return our_member(obj,lst[1:])

our_member(3,[1,2,3,4,5])
--> [3,4,5]

Is it any clearer?

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.â? -- Carl Bass CEO Autodesk

gengyangcai

11/7/2015 1:46:00 PM

Damn ... I'll be meeting a friend tomorrow. He said he can help me master Python , I'll be leaving Lisp aside for the moment. This is an incredibly powerful language (maybe the MOST powerful one according to Paul Graham), so hard to master. At least with Python, I can physically sit down side by side with my friend and really understand the material. And it would be much easier to find co-founders who program in Python since my goal is YCombinator. I'll leave Lisp aside for the moment , but I'll be back since I do want to master it. Probably get back to this after I have successfully built my startup at Ycombinator and have plenty of time to ponder the many intricacies of Lisp ..

On Saturday, November 7, 2015 at 9:30:24 PM UTC+8, informatimago wrote:
> CAI GENGYANG <gengyangcai@gmail.com> writes:
>
>
>
> > From what I understand about the different terms :
> >
> > (defun our-member (obj 1st) ------ (1)
> > (if (null 1st) ------ (2)
> > nil ------ (3)
> > (if (eql (car 1st) obj) ------ (4)
> > 1st ------ (5)
> > (our-member obj (cdr 1st))))) ------ (6)
> >
> >
> > Line 1 : Defines a function called our-member that takes 2 inputs (obj and 1st)
> > Line 2 : null returns t if the object is the empty list, otherwise returns nil
> > Line 3 : nil --- First it means empty list. Second it means false and is the value returned when a true-or-false test tests false.
> > Line 4 : eq1 is a predicate that tests whether its two arguments are identical
> > Line 5 : Just an input called 1st
> > Line 6 : cdr is everything after the 1st element
> >
> >
> > This is the first time I've been so lost ... I am totally clueless
> > what the entire piece of code means. Must be the pizza I just ate lol
> > ...
>
> Yes, but it would be useless to switch to python, it won't be easier to
> understand it in python:
>
> def our_member(obj,lst) :
> if []==lst :
> return []
> else :
> if lst[0]==obj :
> return lst
> else :
> return our_member(obj,lst[1:])
>
> our_member(3,[1,2,3,4,5])
> --> [3,4,5]
>
> Is it any clearer?
>
>
>
> --
> __Pascal Bourguignon__ http://www.informat...
> "The factory of the future will have only two employees, a man and a
> dog. The man will be there to feed the dog. The dog will be there to
> keep the man from touching the equipment." -- Carl Bass CEO Autodesk

Jussi Piitulainen

11/7/2015 1:47:00 PM

Pascal J. Bourguignon writes:

> Yes, but it would be useless to switch to python, it won't be easier
> to understand it in python:
>
> def our_member(obj,lst) :
> if []==lst :
> return []
> else :
> if lst[0]==obj :
> return lst
> else :
> return our_member(obj,lst[1:])
>
> our_member(3,[1,2,3,4,5])
> --> [3,4,5]
>
> Is it any clearer?

Python:

cons = lambda a, d : (a, d)
car = lambda p : p[0]
cdr = lambda p : p[1]
member = (lambda obj, lst:
lst and (lst if obj == car(lst) else member(obj, cdr(lst))))

datumi = cons(1, cons(1, cons(2, cons(3, ()))))
print('#', member(1, datumi))
print('#', member(2, datumi))
print('#', member(3, datumi))
print('#', member(4, datumi))

# C-u M-! python3 cons.py RET
# (1, (1, (2, (3, ()))))
# (2, (3, ()))
# (3, ())
# ()

--
....

William James

11/7/2015 3:37:00 PM

Pascal J. Bourguignon wrote:

> > From what I understand about the different terms :
> >
> > (defun our-member (obj 1st) ------ (1)
> > (if (null 1st) ------ (2)
> > nil ------ (3)
> > (if (eql (car 1st) obj) ------ (4)
> > 1st ------ (5)
> > (our-member obj (cdr 1st))))) ------ (6)
> >
> >
> > Line 1 : Defines a function called our-member that takes 2 inputs
> > (obj and 1st)
> > Line 2 : null returns t if the object is the empty list, otherwise
> > returns nil
> > Line 3 : nil --- First it means empty list. Second it means false
> > and is the value returned when a true-or-false test tests false.
> > Line 4 : eq1 is a predicate that tests whether its two arguments
> > are identical
> > Line 5 : Just an input called 1st
> > Line 6 : cdr is everything after the 1st element
> >
> >
> > This is the first time I've been so lost ... I am totally clueless
> > what the entire piece of code means. Must be the pizza I just ate lol
> > ...
>
> Yes, but it would be useless to switch to python, it won't be easier to
> understand it in python:
>
> def our_member(obj,lst) :
> if []==lst :
> return []
> else :
> if lst[0]==obj :
> return lst
> else :
> return our_member(obj,lst[1:])
>
> our_member(3,[1,2,3,4,5])
> --> [3,4,5]
>
> Is it any clearer?

MatzLisp (Ruby):

def member obj,array
array.drop_while{|x| x != obj}
end

member(3,[1,2,3,4,5])
==>[3, 4, 5]
member(9,[1,2,3,4,5])
==>[]

--
Man is a social animal just like ants or bees or wolves. All have their living
space, which they defend to the very end.
http://www.kolumbus.fi/aquilon/aquilon...

Barry Margolin

11/7/2015 6:14:00 PM

In article <ac5bc6b1-8605-40a1-8833-993fbe146a7e@googlegroups.com>,
CAI GENGYANG <gengyangcai@gmail.com> wrote:

> This is a recursive function :
>
> (defun our-member (obj 1st)
> (if (null 1st)
> nil
> (if (eql (car 1st) obj)
> 1st
> (our-member obj (cdr 1st)))))
>
> Here it is in action :
>
> > (our-member 'b '(a b c))
> (B C)
> > (our-member 'z '(a b c))
> NIL
>
>
> This is a tough piece of code --- how do I understand it ?

Translate it to English:

If the list is empty, it has no members, so obiously obj is not a member.

Otherwise, obj is a member of a list if:
a) it's the first element of the list, or
b) it's a member of the rest of the list

--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

comp.lang.lisp

Recursion

gengyangcai

Pascal J. Bourguignon

gengyangcai

Teemu Likonen

gengyangcai

gengyangcai

Pascal J. Bourguignon

gengyangcai

Jussi Piitulainen

William James

Barry Margolin

x Login to ForumsZone