LispForum

Posted: **Sat Mar 20, 2010 11:42 am**

Hello,

I tried to write a little storting program, but I make a mistake in calling the function "sort-insert". Can anybody tell me my mistake?

Code: Select all

(setq test-list (list 3 5 1 2 9 4 7 8 6))

(defun sort-list(ulist)
        (let ((nlist (list)))
                (dolist (x ulist)
                        (setq nlist `(sort-insert ,x ,nlist))
                )
        (setq ulist nlist)
        )
        ulist
)

(defun sort-insert(element liste)
        (let ((blist (list)) (filled 0))
        (dolist (x liste)
                (when (and (> x element) (= filled 0))
                        (setq blist `(,@blist ,element))
                        (setq filled 1)
                )
                (setq blist `(,@blist ,x))
        )
        (print blist)
        (setq liste blist)
        )
        liste
)

Thanks in advance!

Posted: **Sat Mar 20, 2010 1:48 pm**

Please don't indent this like C.

Code: Select all

(setq test-list (list 3 5 1 2 9 4 7 8 6)) ;; this should be a defparameter or a defvar.

(defun sort-list(ulist)
  (let ((nlist (list)))
    (dolist (x ulist)
      (setq nlist `(sort-insert ,x ,nlist)))
    (setq ulist nlist))
  ulist)

(defun sort-insert(element liste)
  (let ((blist (list)) (filled 0))
    (dolist (x liste)
      (when (and (> x element) (= filled 0))
        (setq blist `(,@blist ,element))
        (setq filled 1))
      (setq blist `(,@blist ,x)))
    (print blist)
    (setq liste blist))
  liste)

Posted: **Sat Mar 20, 2010 6:08 pm**

sort-insert might work if there are elements in the input list, but doesn't if ulist==nil. That seems to be the main problem.

Practice is good, but merge and sort can be used.

Also you could have made FILLED t/nil(true/false) instead of 0/1, and can you write it with recursion, without using setq?

Posted: **Sun Mar 21, 2010 8:48 am**

Hi, thanks for the answers. I changed the setq variable to a defparameter, checked for nil of the ulist and replaced the 0/1 with T/NIL for the filled variable.

But there's still one problem. I call the "sort-list" function with the defparameter:

(sort-list test-list)

The result looks like this:

Code: Select all

(SORT-INSERT 6
 (SORT-INSERT 8
  (SORT-INSERT 7
   (SORT-INSERT 4
    (SORT-INSERT 9
     (SORT-INSERT 2
      (SORT-INSERT 1 (SORT-INSERT 5 (SORT-INSERT 3 NIL)))))))))

It seems, that the function "sort-insert" is not used within the function call.

Any ideas?

Posted: **Sun Mar 21, 2010 1:03 pm**

That's because you're quoting (preventing evaluation of) the call. Change `(sort-insert ,x ,nlist) to (sort-insert x nlist).

Posted: **Mon Mar 22, 2010 4:18 am**

Avoid backquote when not making macros for now. (You should probably also avoid macros as a beginner for a while too) Realize that they make a list, in the code above, you essentially do (setq nlist (list 'sort-insert x nlist)), it is good to know what things expand to

Perhaps you need to read some about how variables work in common lisp, like via PCL. Ways of making variables, there are essentially two ways:

Via stuff like LET, DEFUN, LAMBDA, local variables, the mayority of macros have this origin.
Via DEFVAR and DEFPARAMETER, these are special variables; global variables with a twist, usually to be called at 'compile-time'.
The twist being that you can change them locally with LET and such, and they will remain locally so even within functions called there.
Symbol-macros via symbol-macrolet these aren't variables, they are symbols that are expanded to (possibly settable)expressions. An example is WITH-SLOTS, (with-slots (slot) struct ... ...) expands SLOT in it's body to (slot-value struct 'slot).

Never initiate make any variable via SETQ/SETF or such, but it seems you already get that.

So you probably shouldn't be using DEFPARAMETER in this code.

Posted: **Mon Mar 22, 2010 1:41 pm**

Hello,

thanks for the many really helpful answers. I currently read the Practical Common Lisp book and try to familiarize myself with Lisp.

I change the function call to "(setq nlist (sort-insert x nlist)))" but the result simply end in NIL.

Could anybody show me a result. Mostly, it is very helpful to learn from working code.

Thanks in advance.

Posted: **Tue Mar 23, 2010 2:00 pm**

Try (sort-insert 'anything nil), the result is nil. And if it stays nil the first time, it remains nil, that is your problem. (sort-insert 'anything (list 'something)) works. Why does it do that? What does (dolist (x liste) do for liste==nil? Nothing, it does something for each element of the list, it doesn't try to find a location because there is nowhere to find it. You do react differently when the list is nil; (if (null liste) (list x)) ....

Btw you can also eliminate the (setq liste blist) part; you can return blist directly. And (= filled 0) prerequisite can be removed by using (return ..) in to stop iterating the dolist. Can you post what you can put together with this info?

Posted: **Tue Mar 23, 2010 3:20 pm**

Hello,

I read some helpful articles and tried another approach to solve it. Here is my result:

Code: Select all

(defun rcsort (myl)
  (if (not (atom myl))
    (let ((x (smallest myl)))
      (cons x (rcsort (delete-smallest x myl)))
    )))

(defun smallest (myl)
  (if (not (null myl))
    (let ((x (car myl)))
      (dolist (elem myl)
        (if (and (not (null elem)) (< elem x))
          (setq x elem)
        )
      )
    x)))

(defun delete-smallest(elem myl)
  (let ((nlist '()) (deleted '()))
    (dolist (celem myl)
      (if (and (= elem celem) (not deleted))
        (setq deleted 't)
        (setq nlist (cons celem nlist))
      )
    )
    nlist))

You can try the sort with e.g.:
(rcsort (list 4 2 1 9 4 2 5))

This is definitely not the best solution and there are surely much better ways to solve it, but it's just a beginning. And it works

Posted: **Tue Mar 23, 2010 4:15 pm**

Oh so

, you weren't that far off with the earlier code:

Code: Select all

(defun sort-insert(element liste)
  (let ((blist (list)) (filled 0))
    (dolist (x liste)
      (when (and (> x element) (= filled 0))
        (setq blist `(,@blist ,element))
        (setq filled 1))
      (setq blist `(,@blist ,x)))
    (setq liste blist))
  liste)

The problem was, that if you didn't find one for which (> x element) you wouldn't insert element at all. Which would happen if you started with the empty list.

Or cleaned up a little; the 'setq liste blist' and such is not needed:

Code: Select all

(defun sort-list(ulist &optional (compare #'<))
  (let ((nlist (list)))
    (dolist (x ulist nlist)
      (setq nlist (sort-insert x nlist compare)))))

(defun sort-insert(element liste &optional (compare #'<))
  (let ((blist (list)) (filled nil))
    (dolist (x liste)
      (when (and (funcall compare x element) (not filled))
        (setq blist `(,@blist ,element)
	      filled t))
      (setq blist `(,@blist ,x)))
    (if filled 
      blist
      `(,@blist ,element))))

Eh why can't i replace `(,@blist ,element) with (cons element blist) and get reversed results.. Am guesssing it somehow sets that list?

Or a recursive approach:(of the same)

Code: Select all

(defun sort-list(ulist &optional (compare #'>) sorted-list)
  (if (null ulist)
    sorted-list
    (sort-list (cdr ulist) compare
	       (sort-insert (car ulist) sorted-list compare))))

(defun sort-insert(element liste &optional (compare #'>))
  (if (or (null liste) (funcall compare (car liste) element))
    (cons element liste)
    (cons (car liste) (sort-insert element (cdr liste) compare))))

LispForum

Please help for the beginner

Please help for the beginner

Re: Please help for the beginner

Re: Please help for the beginner

Re: Please help for the beginner

Re: Please help for the beginner

Re: Please help for the beginner

Re: Please help for the beginner

Re: Please help for the beginner

Re: Please help for the beginner

Re: Please help for the beginner