Page 1 of 1

end chapter exercise's doubts...

Posted: Sun Nov 04, 2012 1:05 pm
by megera
HI
the exercise says:
"""Define iterative and recursive versions of a function that takes an object x and vector v, and returns a list of all the objects that immediately precede x in v:
> (precedes #\a "abracadabra")
(#\c #\d #\r) """
ok, my solution (iterative mode):

Code: Select all

(defun precedes(car vec)
	   (let((lista nil))
	     (dotimes (i (length  vec))
	       (if (and (equal (aref vec i) car)(> i 0))
		       (setf lista (cons (aref vec (- (position car vec :start i) 1)) lista))))
	     lista))
online book solution:

Code: Select all

(defun presedes (x v)
            (let (acc (v (concatenate 'vector v))) ;; on book ther's  v1 instead v...;)
               (dotimes (i (length v))
                  (if (and (eql x (svref v i)) (< 0 i))
	                (push (svref v (- i 1)) acc)))
              (remove-duplicates acc)))
First:
probably my solution runs slower then correct solution, isn't it?? becouse my solution sets 'list' for each iteration and lacks "remove-duplicates " that parse the vector...
then, is my solution more inefficient than correct solution? then is always preferable works with latter?
thanks in advance

Re: end chapter exercise's doubts...

Posted: Sun Nov 04, 2012 3:21 pm
by Paul
No. Yours pointlessly calls POSITION to find something you've already located, but otherwise they're the same (except for REMOVE-DUPLICATES). (PUSH x y) == (SETQ y (CONS x y))

Re: end chapter exercise's doubts...

Posted: Mon Nov 05, 2012 1:56 am
by wvxvw
If you are concerned with efficiency, then the solution in the book probably isn't the most efficient either...

Code: Select all

(defun precedes (element vector)
  (let ((hash (make-hash-table)))
    (do ((i (1- (length vector)) (1- i))
         compare-to result backref)
        ((= i 0) result)
      (setf compare-to (aref vector (1- i)))
      (when (and (eql element (aref vector i))
                 (not (gethash compare-to hash)))
        (setf (gethash compare-to hash) t)
        (if result
            (setf (cdr backref) (list compare-to)
                  backref (cdr backref))
            (setf result (list compare-to)
                  backref result))))))
While the code is longer, it will do it in general faster + it will return the preceding elements in the same order they appeared in the source vector (sans repetitions).
For some reason the exercises which use lists for the purpose they aren't good for are very trendy in Lisp :/ This is certainly a task that benefits from using a hash-map.

Re: end chapter exercise's doubts...

Posted: Mon Nov 05, 2012 5:17 am
by stackman
You can use pushnew instead of push if you don't want duplicates in the result.

Re: end chapter exercise's doubts...

Posted: Mon Nov 05, 2012 5:37 am
by megera
HI Paul , wvxvw and stackman ...thanks for your support and suggestions!! ;)

Now I have some questions for wvxvw about his syntax's code that are new for me :roll:

First:
---- the third, fourth and fifth expressions in the fisrt “do”’s argument : compare-to result backref will be evaluated and returned as the value of the do loop when iteration terminates, as happens in dolist ??right? then so far it's ok..but:

Second:
--- is it possible call variables or expression before declare it? Also in an iterations or conditionals?
What seems strange to me is that it’s possible ,for example, initiate a conditional with a variable or expression that will be defined afterwards!!!:
for example in your code :
> (if result… setf result (list compare-to)….)
result is also used as expression of second argument in "do"....... :roll:
honestly now I'm a little confused about this behavior....can you briefly explain me that???
thanks again!!!

Re: end chapter exercise's doubts...

Posted: Mon Nov 05, 2012 6:40 am
by Goheeca
If you look at the definition of do, you can see that the result is actually defined/declared (I don't know the exact terminology) by the do:

Code: Select all

((i (1- (length vector)) (1- i)) compare-to result backref)
And returned from the do is:

Code: Select all

((= i 0) result)
the first part is a condition and the rest is an implicit progn.

Re: end chapter exercise's doubts...

Posted: Mon Nov 05, 2012 11:58 am
by wvxvw
> is it possible call variables or expression before declare it?

Perhaps, confusing terminology here. Usually, when you say "call", you intend to call something which is callable. In the context of CL that would be either functions or macros. So, if you are asking if it is possible to call a function before it is declared, then answer would be that, you can, sort of, but not directly. For example:

Code: Select all

(foo) ;; error
(defun foo ())
will fail, because foo symbol is not bound to any function, i.e. it's (symbol-function 'foo) is nil.
But you can declare a function that calls a function, which is not defined yet:

Code: Select all

(defun bar () (foo)) ;; warning here, but this is a legitimate code
(defun foo () (print "foo"))
(bar) ;; prints "foo"
And of course you can do it like this, to make it more fail-safe:

Code: Select all

(defun bar () (when (fboundp 'foo) (funcall 'foo)) ;; no warning here
(defun foo () (print "foo"))
(bar) ;; prints "foo"
There's really no way I could think of calling an expression before declaring it... I mean, once you have an expression, you have already declared it.

Re: end chapter exercise's doubts...

Posted: Mon Nov 05, 2012 1:18 pm
by megera
Hi and thanks very much guys for good explanations!!! ;)
eventually I continue to make the same mistake!! uffff :x : I forget that it’s possible initialize a variable without value, then take nil to default…

like compare-to result backref in wvxvw's code ..
thanks again!!!