Please help for the beginner

Discussion of Common Lisp
Post Reply
indianerrostock
Posts: 8
Joined: Sat Mar 20, 2010 11:38 am
Contact:

Please help for the beginner

Post by indianerrostock » 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!
"Wenn du nicht irrst, kommst du nicht zu Verstand! Willst du entstehn, entsteh auf eigne Hand!" » FAUST II «
-----
http://www.faustas.de
http://www.makeaims.com
http://www.nebelklar.de

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Please help for the beginner

Post by nuntius » 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)

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: Please help for the beginner

Post by Jasper » 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?

indianerrostock
Posts: 8
Joined: Sat Mar 20, 2010 11:38 am
Contact:

Re: Please help for the beginner

Post by indianerrostock » 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?
"Wenn du nicht irrst, kommst du nicht zu Verstand! Willst du entstehn, entsteh auf eigne Hand!" » FAUST II «
-----
http://www.faustas.de
http://www.makeaims.com
http://www.nebelklar.de

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Please help for the beginner

Post by nuntius » 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).

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: Please help for the beginner

Post by Jasper » 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.

indianerrostock
Posts: 8
Joined: Sat Mar 20, 2010 11:38 am
Contact:

Re: Please help for the beginner

Post by indianerrostock » 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.
"Wenn du nicht irrst, kommst du nicht zu Verstand! Willst du entstehn, entsteh auf eigne Hand!" » FAUST II «
-----
http://www.faustas.de
http://www.makeaims.com
http://www.nebelklar.de

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: Please help for the beginner

Post by Jasper » 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?

indianerrostock
Posts: 8
Joined: Sat Mar 20, 2010 11:38 am
Contact:

Re: Please help for the beginner

Post by indianerrostock » 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 :)
"Wenn du nicht irrst, kommst du nicht zu Verstand! Willst du entstehn, entsteh auf eigne Hand!" » FAUST II «
-----
http://www.faustas.de
http://www.makeaims.com
http://www.nebelklar.de

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: Please help for the beginner

Post by Jasper » 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))))

Post Reply