On Mar 10, 6:45 pm, ··················@gmail.com wrote:
> Hi,
>
> I have begun learning Lisp early this week. I'm stuck dealing with a
> piece of code that behaves in a really weird fashion.
Well, it is behaving in an allowable way. Let's look at the docs for
sort:
"sort and stable-sort destructively sort sequences according to the
order determined by the predicate function."
-- http://www.lisp.org/HyperSpec/Body/fun_sortcm_stable-sort.html
This means that sort is allowed to modify the actual structure of the
list passed into it. So, let's say we had the list
L = (2 3 1)
but lets look at it in terms of actual cons cells.
L = a=(2 . b=(3 . c=(1 . NIL)))
(sort L #'<) must return a list that looks like (1 2 3); that's
what sort guarantees. The actual memory locations a, b, and
c can be destructively modified however. So we might get
back something like
c=(1 . a=(2 . b=(3 . NIL)))
where the cdr of c has been set to a, and the cdr of b
has been set to NIL (and c is returned from sort.)
Now, if we were looking at code like:
(let ((L (list 2 3 1))) ;; L = a=(2 . b=(3 . c=(1 . NIL)))
(sort L #'<))
;=> c=(1 . a=(2 . b=(3 . NIL)))
but since L is still pointing to a,
(let ((L (list 2 3 1))) ; L = a=(2 . b=(3 . c=(1 . NIL)))
(sort L #'<) ; c=(1 . a=(2 . b=(3 . NIL)))
L) ; a=(2 . b=(3 . NIL))
;=> a=(2 . b=(3 . NIL))
and so the usual idiom is to do this:
(let ((L (list 2 3 1))) ;; L = a=(2 . b=(3 . c=(1 . NIL)))
(setf L (sort L #'<)) ; L <- c=(1 . a=(2 . b=(3 . NIL)))
L) ; c=(1 . a=(2 . b=(3 . NIL)))
;=> c=(1 . a=(2 . b=(3 . NIL)))
The behavior that /is/ actually somewhat odd is that some
other list manipulations, e.g., reverse, which don't destructively
modify their arguments, but for which there are n- (non-consing)
versions, e.g., nreverse, which /can/ modify their arguments.
With that convention, it might be reasonable to /expect/ sort to
return a new list and nsort to be a destructive version. Oh well;
it adds charm to the language (or something.)
Hope this helped,
--J
> I have this declaration: (defstruct (node) square board value). Inside
> a function I call (sort moves #'> :key #'node-value), with moves
> holding a list of nodes. Sometimes moves loses some members after
> sorting. I am completely sure about that.
>
> Here the result of printing moves exactly before and after calling
> sort:
>
> Before
>
> (#S(NODE
> :SQUARE 77
> :BOARD #(3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 2 3 3 1 1 1 1 2 1 2
> 2 3 3 1
> 1 1 1 1 1 2 2 3 3 2 1 1 1 2 1 2 2 3 3 2 1 1 1 2 1 2 2 3
> 3 2 1 1
> 2 1 2 2 2 3 3 2 2 2 2 2 2 2 2 3 3 2 2 1 1 1 1 0 0 3 3 3
> 3 3 3 3
> 3 3 3 3)
> :VALUE -4)
> #S(NODE
> :SQUARE 87
> :BOARD #(3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 2 3 3 1 1 1 1 2 1 2
> 2 3 3 1
> 1 1 1 1 1 2 2 3 3 2 1 1 1 2 1 2 2 3 3 2 1 1 1 2 1 2 2 3
> 3 2 1 1
> 2 1 1 2 2 3 3 2 2 2 2 1 1 0 2 3 3 2 2 2 2 2 2 2 0 3 3 3
> 3 3 3 3
> 3 3 3 3)
> :VALUE -2))
>
> After
>
> (#S(NODE
> :SQUARE 77
> :BOARD #(3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 2 3 3 1 1 1 1 2 1 2
> 2 3 3 1
> 1 1 1 1 1 2 2 3 3 2 1 1 1 2 1 2 2 3 3 2 1 1 1 2 1 2 2 3
> 3 2 1 1
> 2 1 2 2 2 3 3 2 2 2 2 2 2 2 2 3 3 2 2 1 1 1 1 0 0 3 3 3
> 3 3 3 3
> 3 3 3 3)
> :VALUE -4))
>
> I have tried several implementations of Lisp, but all of them treat
> the list in the same strange way. There may be a weird gotcha that I'm
> ignoring.
>
> Thanks
··················@gmail.com wrote:
> Hi,
>
> I have begun learning Lisp early this week. I'm stuck dealing with a
> piece of code that behaves in a really weird fashion.
>
> I have this declaration: (defstruct (node) square board value). Inside
> a function I call (sort moves #'> :key #'node-value), with moves
> holding a list of nodes. Sometimes moves loses some members after
> sorting. I am completely sure about that.
>
> Here the result of printing moves exactly before and after calling
> sort:
>
> Before
>
> (#S(NODE
> :SQUARE 77
> :BOARD #(3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 2 3 3 1 1 1 1 2 1 2
> 2 3 3 1
> 1 1 1 1 1 2 2 3 3 2 1 1 1 2 1 2 2 3 3 2 1 1 1 2 1 2 2 3
> 3 2 1 1
> 2 1 2 2 2 3 3 2 2 2 2 2 2 2 2 3 3 2 2 1 1 1 1 0 0 3 3 3
> 3 3 3 3
> 3 3 3 3)
> :VALUE -4)
> #S(NODE
> :SQUARE 87
> :BOARD #(3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 2 3 3 1 1 1 1 2 1 2
> 2 3 3 1
> 1 1 1 1 1 2 2 3 3 2 1 1 1 2 1 2 2 3 3 2 1 1 1 2 1 2 2 3
> 3 2 1 1
> 2 1 1 2 2 3 3 2 2 2 2 1 1 0 2 3 3 2 2 2 2 2 2 2 0 3 3 3
> 3 3 3 3
> 3 3 3 3)
> :VALUE -2))
>
> After
>
> (#S(NODE
> :SQUARE 77
> :BOARD #(3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 2 3 3 1 1 1 1 2 1 2
> 2 3 3 1
> 1 1 1 1 1 2 2 3 3 2 1 1 1 2 1 2 2 3 3 2 1 1 1 2 1 2 2 3
> 3 2 1 1
> 2 1 2 2 2 3 3 2 2 2 2 2 2 2 2 3 3 2 2 1 1 1 1 0 0 3 3 3
> 3 3 3 3
> 3 3 3 3)
> :VALUE -4))
>
> I have tried several implementations of Lisp, but all of them treat
> the list in the same strange way. There may be a weird gotcha that I'm
> ignoring.
Yup. Have you seen those little introductory diagrams illustrating
linked cons cells? Your variable moves starts out bound to the first
cell in that linked list. SORT may change the order by changing who gets
inked to whom, but it will not rebind the variable MOVES to whichever
cell ends up first. So you won't lose anyway if the first is still first
after the sort, other wise you will lose all the guys that end up ahead
of the original first element.
Try (setf moves (sort moves.....))
kt
--
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
"Algebra is the metaphysics of arithmetic." - John Ray
http://www.theoryyalgebra.com/
On Sun, 11 Mar 2007 00:45:46 +0100, <··················@gmail.com> wrote:
> I have tried several implementations of Lisp, but all of them treat
> the list in the same strange way. There may be a weird gotcha that I'm
> ignoring.
>
> Thanks
>
I don't see the call to sort, but it's a fair bet you are not using
the value returned by sort. (setf value (sort ...)) never (sort value ...).
(The same is true for nearly all destructive functions in lisp,
like delete, nreverse etc.)
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/