Implementing "last" with do*

Discussion of Common Lisp

Re: Implementing "last" with do*

Postby dragmnl123 » Sun Dec 11, 2011 5:54 am

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
dragmnl123
 
Posts: 11
Joined: Fri Oct 07, 2011 2:39 am

Re: Implementing "last" with do*

Postby smithzv » Sun Dec 11, 2011 6:27 am

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:

Code: Select all
(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.
smithzv
 
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: Implementing "last" with do*

Postby dragmnl123 » Sun Dec 11, 2011 6:39 am

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..)

Code: Select all
(defun last-it3 (lista n) ;;; ## TO FIX ##
  (do* ( (n (list-length lista)) )
       (
      (eql (list-length lista) n)
        lista  ; return lista
      )
    (setf lista (cdr lista))
 )
)
dragmnl123
 
Posts: 11
Joined: Fri Oct 07, 2011 2:39 am

Re: Implementing "last" with do*

Postby smithzv » Sun Dec 11, 2011 7:04 am

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:

Code: Select all
(defun last-it3 (lista n)
  (do* ()
       ((eql (list-length lista) n) lista)
    (setf lista (cdr lista))))
smithzv
 
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: Implementing "last" with do*

Postby dragmnl123 » Sun Dec 11, 2011 12:41 pm

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:

Code: Select all
(defun last-it3 (lista n)
  (do* ()
       ((eql (list-length lista) n) lista)
    (setf lista (cdr lista))))
dragmnl123
 
Posts: 11
Joined: Fri Oct 07, 2011 2:39 am

Re: Implementing "last" with do*

Postby smithzv » Sun Dec 11, 2011 12:44 pm

It's the same as Konfusius' except now 1->n, which was the hint he was giving you.
smithzv
 
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: Implementing "last" with do*

Postby sw2wolf » Tue Dec 13, 2011 6:18 pm

(set-difference '(1 2 3 4 5 6 7) (butlast '(1 2 3 4 5 6 7)))
sw2wolf
 
Posts: 2
Joined: Wed Oct 19, 2011 6:03 pm

Re: Implementing "last" with do*

Postby dragmnl123 » Thu Dec 15, 2011 5:27 am

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".
dragmnl123
 
Posts: 11
Joined: Fri Oct 07, 2011 2:39 am

Re: Implementing "last" with do*

Postby smithzv » Thu Dec 15, 2011 8:18 am

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:

Code: Select all
> (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.
smithzv
 
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: Implementing "last" with do*

Postby dragmnl123 » Thu Dec 15, 2011 8:21 am

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:

Code: Select all
> (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
 
Posts: 11
Joined: Fri Oct 07, 2011 2:39 am

Previous

Return to Common Lisp

Who is online

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