Implementing "last" with do*

Discussion of Common Lisp

Implementing "last" with do*

Postby dragmnl123 » Sat Dec 10, 2011 12:42 pm

Hello everyone.
I'm trying to implement ITERATIVE "last" function.
But it doesn't seem to work. It is important I use do* . However if you have any suggestion of good "alternatives" it's ok!
I know "last" function accepts &optional n , but this is a "simplified" one. However I accept any suggestion to do the "full" one.

(defun last-it (lista)
( do*
;; NO VARS ;;
(
(equal (list-length lista) 1) ;; <== when there is just one element left ==> stop
lista ; return lista
)
(set lista (cdr lista)) ; ** ;; <== like "cdr recursion"
)
)

What is wrong? It loads...but give error "setf has no value".
And if here ** I write
((set lista (cdr lista))
==> infinite loop

Thank you
dragmnl123
 
Posts: 11
Joined: Fri Oct 07, 2011 2:39 am

Re: Implementing "last" with do*

Postby Konfusius » Sat Dec 10, 2011 1:55 pm

Code: Select all
(defun last-it (lista)
  (do* ()
       ((equal (list-length lista) 1) ;; <== when there is just one element left ==> stop
        lista) ; return lista
    (setf lista (cdr lista)))) ; ** ;; <== like "cdr recursion"
Konfusius
 
Posts: 62
Joined: Fri Jun 10, 2011 6:38 am

Re: Implementing "last" with do*

Postby dragmnl123 » Sat Dec 10, 2011 2:36 pm

thank you very much!!
Very useful :)
Any hints to make the "full" version? (the one which returns "last n elements")
dragmnl123
 
Posts: 11
Joined: Fri Oct 07, 2011 2:39 am

Re: Implementing "last" with do*

Postby Konfusius » Sat Dec 10, 2011 6:40 pm

Code: Select all
<== when there is just one element left ==> stop
Konfusius
 
Posts: 62
Joined: Fri Jun 10, 2011 6:38 am

Re: Implementing "last" with do*

Postby smithzv » Sat Dec 10, 2011 9:05 pm

Konfusius wrote:
Code: Select all
       ((equal (list-length lista) 1) ;; <== when there is just one element left ==> stop


Just a note. The first step is getting something that works; this function presumably does this. A fairly important second concern is the efficiency of the code you produced. This particular line will, in most if not all Lisp implementations, produce code that takes a long time to execute for long lists because of the way list-length works. If you wanted something more efficient, the first thing would be to find a way to replace this entire line of code.
smithzv
 
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: Implementing "last" with do*

Postby dragmnl123 » Sat Dec 10, 2011 9:08 pm

I cannot understand what you mean with "replace the line".
I don't see any way to replace that line...is the "end condition" (recursion is based on: end case , recursive call. No?)
dragmnl123
 
Posts: 11
Joined: Fri Oct 07, 2011 2:39 am

Re: Implementing "last" with do*

Postby smithzv » Sat Dec 10, 2011 9:56 pm

Right but there are different ways to write the same en condition. For instance, you could also write:

Code: Select all
               ((equal 1 (list-length lista)) ;; <== when there is just one element left ==> stop


although it would have the same behavior. There is a way to write that exit condition so that it takes a constant amount of time (i.e. doesn't take an amount of time proportional to the length of the list).
smithzv
 
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: Implementing "last" with do*

Postby dragmnl123 » Sun Dec 11, 2011 4:19 am

ok thank you. But is not supposed to be "automatically" done by the compiler?
I mean new compilers optimize the code
dragmnl123
 
Posts: 11
Joined: Fri Oct 07, 2011 2:39 am

Re: Implementing "last" with do*

Postby dragmnl123 » Sun Dec 11, 2011 4:33 am

(Sorry for double reply)
I tried to update the code to handle "last n elements".
I know it give INFINITIVE LOOP because I will go matching NIL with NIL.
But how to save the lenght of the list t to match it?
For example:
- I pass list of 7 elements: ' (1 2 3 4 5 6 7)
- I want last 4 elements: '4
- Result expected: ' (4 5 6 7)

Any idea?

Code: Select all
(defun last-it3 (lista n)
  (do* ()
       (
      (equal (list-length lista) (- (list-length lista) n)) ;;        lista  ; return lista
      )
   (format t "~%~A" lista) ;; TEST
    (setf lista (cdr lista))
   (format t "~%~A" lista) ;; TEST
 )
) ; ** ;; <== like "cdr recursion"
dragmnl123
 
Posts: 11
Joined: Fri Oct 07, 2011 2:39 am

Re: Implementing "last" with do*

Postby smithzv » Sun Dec 11, 2011 5:23 am

Yes and no. I am perhaps spoiling the pedagogy here (which I take is the essence of the exercise), but just so we're clear, I talking about instead of computing the length of the list and then seeing it equals 1, just checking the CDR of the list to see if it is NIL (which works out to be the same). I am not sure I know of compilers that will do this optimization. Perhaps a Haskell compiler can? I am almost certain that no Common Lisp compilers do this, so that's something to keep in mind. In Paul Graham's books, one of the first examples he gives is a function that basically does this test efficiently (it's in On Lisp and probably Ansi CL).

Common Lisp has a feature called compiler macros. They are a pretty cool feature that allows users to write these kinds of source level optimizations. However, so you don't shoot yourself in the foot, you can only define these kind of optimization for user defined symbols (i.e. functions like EQUAL are off limits). You can get around this, if you really want. Point is, you can implement this optimization yourself, but it is pretty narrow in applicability.

BTW, I just tried to write this compiler macro myself and succeeded in shooting myself in the foot.

Regarding your second post: your exit form makes no sense. How is it ever true? Given a list L, with length x, how is it ever true that x=x-n unless n=0? That is what you have written.

Also, you might get more interest if you properly formatted your code. It is hard to read they way it is written.
smithzv
 
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Next

Return to Common Lisp

Who is online

Users browsing this forum: Bing [Bot], Yahoo [Bot] and 1 guest

cron