LispForum

Discuss and learn Lisp programming of all dialects

This is a read-only archive of lispforum.com. The forum was locked to new users and posts and is preserved here as static HTML from a database snapshot taken on 2019-09-07.

Implementing "last" with do*

20 posts · 11274 views

dragmnl123
#1
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
Konfusius
#2

Re: Implementing "last" with do*

(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"
dragmnl123
#3

Re: Implementing "last" with do*

thank you very much!!
Very useful :)
Any hints to make the "full" version? (the one which returns "last n elements")
Konfusius
#4

Re: Implementing "last" with do*

<== when there is just one element left ==> stop
smithzv
#5

Re: Implementing "last" with do*

Konfusius wrote:
       ((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.
dragmnl123
#6

Re: Implementing "last" with do*

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?)
smithzv
#7

Re: Implementing "last" with do*

Right but there are different ways to write the same en condition. For instance, you could also write:
               ((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).
dragmnl123
#8

Re: Implementing "last" with do*

ok thank you. But is not supposed to be "automatically" done by the compiler?
I mean new compilers optimize the code
dragmnl123
#9

Re: Implementing "last" with do*

(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?
(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"
smithzv
#10

Re: Implementing "last" with do*

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.
dragmnl123
#11

Re: Implementing "last" with do*

Yeah.
Thank you for the very exaustive explanation.
However I'm doing a BASIC common list course at university...but the info you gave me will be useful (and I will save them on my PC) because I'm (and I will keep) studying A.I. .

(I don't well how to format the code..etc..I'm a "novice" of this forum (I suppose it is algo related to the functions on the top of the text area where I'm writing). )

However... I know there is an infinitive loop (I specified it). And I'm sure I have to save in a variable ** "difference between original list length and n" (or something similar) and use it as base base.
But
1) I don't have any idea if I can declare this variable ** inside the function and WHERE.
2) I'm not sure of the basic case. I mean... if I use "difference between original list length and n" I will have iterate (example: with a LOOP FOR) from 1 to variable value.... but how to do it with a (equal (...)) ? And how to do it in recursive move (told I know it is less efficent..) ?

Thank you
smithzv
#12

Re: Implementing "last" with do*

dragmnl123 wrote:1) I don't have any idea if I can declare this variable ** inside the function and WHERE.
Hopefully you have heard of binding variables. If not, check out LET. It allows you to define a variable. You don't even have to use LET in this case, because DO basically has a LET built in.

As for the base case, I might suggest that you want something like (equal (list-length lista) n), using your notation. This will be true when the length of the list equals n.
dragmnl123 wrote:And how to do it in recursive move (told I know it is less efficent..) ?
How indeed. It is actually a pretty interesting problem. Here is a quite inefficient way of doing it:
(defun last-it3 (list n)
  (if (equal n (list-length list))
      list
      (last-it3 (cdr list) n)))
The trick to making it better is to find a way to avoid calling list-length at every function call.
dragmnl123
#13

Re: Implementing "last" with do*

Well...

1) About your function: WORKS (but I changes list to LISTA , because "list" is a KEY-WORD ). Just I don't understand: how can it works? equal match pointers... 2 integers are supposed to be the same if they are the same object..not the same value.. Indeed, I used EQL and it works fine.

2) About ITERATIVE one... why mine doesn't work? It runs...but it returns the ORIGINAL list (not last N elements..)
(defun last-it3 (lista n) ;;; ## TO FIX ##
  (do* ( (n (list-length lista)) )
       (
	   (eql (list-length lista) n)
        lista  ; return lista
	   )
    (setf lista (cdr lista))
 )
)
smithzv
#14

Re: Implementing "last" with do*

List isn't a keyword, but it does happen to be the name of a common function. But call your variables what you wish.

I think you are confused on how the equality operators work. EQ is more like "checking pointers" and it might not work. EQL and above (EQUAL and EQUALP) would all work for this, as would =. If we ignore EQ, then we can treat integers with the same value as the same object.

In your function you are taking a variable N, then ignoring it and setting N equal to the length of the list. This means that you are always getting the last N elements (where N = the length of the original list). So it was actually working. You made excellent use of the DO bindings, however, you actually don't need to use it.

Do this instead:
(defun last-it3 (lista n)
  (do* ()
       ((eql (list-length lista) n) lista)
    (setf lista (cdr lista))))
dragmnl123
#15

Re: Implementing "last" with do*

I don't why..but I was thinking the code you just wrote is the SAME I tried (without success) in the beginning..
...however it works!

Thank you
smithzv wrote:List isn't a keyword, but it does happen to be the name of a common function. But call your variables what you wish.

I think you are confused on how the equality operators work. EQ is more like "checking pointers" and it might not work. EQL and above (EQUAL and EQUALP) would all work for this, as would =. If we ignore EQ, then we can treat integers with the same value as the same object.

In your function you are taking a variable N, then ignoring it and setting N equal to the length of the list. This means that you are always getting the last N elements (where N = the length of the original list). So it was actually working. You made excellent use of the DO bindings, however, you actually don't need to use it.

Do this instead:
(defun last-it3 (lista n)
  (do* ()
       ((eql (list-length lista) n) lista)
    (setf lista (cdr lista))))
smithzv
#16

Re: Implementing "last" with do*

It's the same as Konfusius' except now 1->n, which was the hint he was giving you.
sw2wolf
#17

Re: Implementing "last" with do*

(set-difference '(1 2 3 4 5 6 7) (butlast '(1 2 3 4 5 6 7)))
dragmnl123
#18

Re: Implementing "last" with do*

sw2wolf wrote:(set-difference '(1 2 3 4 5 6 7) (butlast '(1 2 3 4 5 6 7)))
Soluciòn interesante, no conocìa la funciòn "set-difference". Pero suppongo que no hay manera de hacerlo por "los ultimos n".
smithzv
#19

Re: Implementing "last" with do*

Well, actually, BUTLAST has an optional 2nd argument that lets you say "but the last n elements".

Be that as it may, this solutions is actually just incorrect. It relies on the assumption that all elements in the list are unique. SET-DIFFERENCE is for taking the difference between two mathematical sets. Sets are oblivious to the ordering of elements and the number of times certain elements appear. Sets are often represented as lists in CL, which is an arguably bad representation for a set (an ordered tree is a much better one, see the FSet library). As a counter example:
> (let ((lst '(1 1 1 1 1 1 1))) (set-difference lst (butlast lst)))
NIL
You would expect (1 1 1 1 1 1), not nil. Also, depending on what you are doing, BUTLAST on an arbitrary length list can be a real bottleneck. It requires you to walk the entire list and copy the entire list. In this case you have to walk the entire list anyway, but you do not have to copy the entire list. But of course this is secondary to getting a correct solution.
dragmnl123
#20

Re: Implementing "last" with do*

Ok,all right!
Thank you
smithzv wrote:Well, actually, BUTLAST has an optional 2nd argument that lets you say "but the last n elements".

Be that as it may, this solutions is actually just incorrect. It relies on the assumption that all elements in the list are unique. SET-DIFFERENCE is for taking the difference between two mathematical sets. Sets are oblivious to the ordering of elements and the number of times certain elements appear. Sets are often represented as lists in CL, which is an arguably bad representation for a set (an ordered tree is a much better one, see the FSet library). As a counter example:
> (let ((lst '(1 1 1 1 1 1 1))) (set-difference lst (butlast lst)))
NIL
You would expect (1 1 1 1 1 1), not nil. Also, depending on what you are doing, BUTLAST on an arbitrary length list can be a real bottleneck. It requires you to walk the entire list and copy the entire list. In this case you have to walk the entire list anyway, but you do not have to copy the entire list. But of course this is secondary to getting a correct solution.