If you have a list of words that are ALL UNIQUE, and you call sort
with a predicate of string< like this:
(sort word-list #'string<)
Will the sort be stable? Is there a reason to use stable-sort. I don't
see a reason of hand, but I am being told otherwise. I can see it
being unstable if there are some words that are equal. If it is
unstable, please help me understand why.
Thanks in advance!
Mike
In article <························@r29g2000hsg.googlegroups.com>,
skibud2 <·············@gmail.com> wrote:
> If you have a list of words that are ALL UNIQUE, and you call sort
> with a predicate of string< like this:
>
> (sort word-list #'string<)
>
> Will the sort be stable? Is there a reason to use stable-sort. I don't
> see a reason of hand, but I am being told otherwise. I can see it
> being unstable if there are some words that are equal. If it is
> unstable, please help me understand why.
Stability refers to the way that records with equivalent keys are
treated. If there aren't any, then the question "is it stable?" makes
no sense.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Barry --
Thank you, thank you, thank you. That is what I was argument that I
was making.
Mike
On Oct 5, 9:47 pm, Barry Margolin <······@alum.mit.edu> wrote:
> In article <························@r29g2000hsg.googlegroups.com>,
>
> skibud2 <·············@gmail.com> wrote:
> > If you have a list of words that are ALL UNIQUE, and you call sort
> > with a predicate of string< like this:
>
> > (sort word-list #'string<)
>
> > Will the sort be stable? Is there a reason to use stable-sort. I don't
> > see a reason of hand, but I am being told otherwise. I can see it
> > being unstable if there are some words that are equal. If it is
> > unstable, please help me understand why.
>
> Stability refers to the way that records with equivalent keys are
> treated. If there aren't any, then the question "is it stable?" makes
> no sense.
>
> --
> Barry Margolin, ······@alum.mit.edu
> Arlington, MA
> *** PLEASE post questions in newsgroups, not directly to me ***
> *** PLEASE don't copy me on replies, I'll read them in the group ***
Can I get one more person agree with this argument?
On Oct 5, 10:28 pm, skibud2 <·············@gmail.com> wrote:
> Barry --
>
> Thank you, thank you, thank you. That is what I was argument that I
> was making.
>
> Mike
>
> On Oct 5, 9:47 pm, Barry Margolin <······@alum.mit.edu> wrote:
>
> > In article <························@r29g2000hsg.googlegroups.com>,
>
> > skibud2 <·············@gmail.com> wrote:
> > > If you have a list of words that are ALL UNIQUE, and you call sort
> > > with a predicate of string< like this:
>
> > > (sort word-list #'string<)
>
> > > Will the sort be stable? Is there a reason to use stable-sort. I don't
> > > see a reason of hand, but I am being told otherwise. I can see it
> > > being unstable if there are some words that are equal. If it is
> > > unstable, please help me understand why.
>
> > Stability refers to the way that records with equivalent keys are
> > treated. If there aren't any, then the question "is it stable?" makes
> > no sense.
>
> > --
> > Barry Margolin, ······@alum.mit.edu
> > Arlington, MA
> > *** PLEASE post questions in newsgroups, not directly to me ***
> > *** PLEASE don't copy me on replies, I'll read them in the group ***
On Oct 5, 8:00 pm, skibud2 <·············@gmail.com> wrote:
> Can I get one more person agree with this argument?
> > > Stability refers to the way that records with equivalent keys are
> > > treated. If there aren't any, then the question "is it stable?" makes
> > > no sense.
Yes, that's right.
-- Scott
In article <························@y42g2000hsy.googlegroups.com>,
skibud2 <·············@gmail.com> wrote:
> Can I get one more person agree with this argument?
Come on. Isn't it trivially obvious, just based on the definitions of
the words?
Why don't you get the person who is telling you otherwise to explain how
it could possibly be otherwise?
>
>
>
> On Oct 5, 10:28 pm, skibud2 <·············@gmail.com> wrote:
> > Barry --
> >
> > Thank you, thank you, thank you. That is what I was argument that I
> > was making.
> >
> > Mike
> >
> > On Oct 5, 9:47 pm, Barry Margolin <······@alum.mit.edu> wrote:
> >
> > > In article <························@r29g2000hsg.googlegroups.com>,
> >
> > > skibud2 <·············@gmail.com> wrote:
> > > > If you have a list of words that are ALL UNIQUE, and you call sort
> > > > with a predicate of string< like this:
> >
> > > > (sort word-list #'string<)
> >
> > > > Will the sort be stable? Is there a reason to use stable-sort. I don't
> > > > see a reason of hand, but I am being told otherwise. I can see it
> > > > being unstable if there are some words that are equal. If it is
> > > > unstable, please help me understand why.
> >
> > > Stability refers to the way that records with equivalent keys are
> > > treated. If there aren't any, then the question "is it stable?" makes
> > > no sense.
> >
> > > --
> > > Barry Margolin, ······@alum.mit.edu
> > > Arlington, MA
> > > *** PLEASE post questions in newsgroups, not directly to me ***
> > > *** PLEASE don't copy me on replies, I'll read them in the group ***
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
OK,
I have to say I am a little frustrated; I don't get frustrated very
easily, but I am now.
Recently, I submitted a job application to a local company that does
Lisp. As part of their application process, they requested each
applicant to do a problem from their website. I completed the problem,
tested it, and submitted it. The recruiter replied to me via e-mail
saying that I needed to change my sort function calls to stable-sort.
Naturally, my instinct was to understand why I needed to change my
calls from sort to stable-sort. Since I was already familiar with sort
and stable-sort issues, I didn't think that this request was correct.
Either way, I brought up the good old common-lisp hyperspec and double
checked whether I needed stable-sort; I concluded that I didn't need
it. After going back and forth with the company, they finally told me
the reviewer changed the code himself and it worked. However, I just
don't understand how it stable-sort could have made a difference.
Here is what I was doing. Please tell me if stable-sort would make a
difference:
(setf word-list '("foo" "bar" .. "foobar")) ;; Many words (which
are actually from a file)
(sort word-list #'string<)
(setf *word-list-array* (make-array (length word-list) :initial-
contents word-list))
And from that point on, *word-list-array* was used to do a binary
search for words. word-list was not used after the sort.
The reviewer gave me a hint by telling me what word in the list was
getting screwed up. The unique feature of the word was that another
word was a substring of it (a prefix). However string< is supposed to
handle this according to the common-lisp hyperspec. Therefore, I think
it could be a bug with the reviewers version of common lisp, but I
think I may have already sufficiently pissed him off by disagreeing
with him. I guess I would have been better off just agreeing and
making the changes. What do you all think?
Mike
On Oct 6, 10:57 pm, Barry Margolin <······@alum.mit.edu> wrote:
> In article <························@y42g2000hsy.googlegroups.com>,
>
> skibud2 <·············@gmail.com> wrote:
> > Can I get one more person agree with this argument?
>
> Come on. Isn't it trivially obvious, just based on the definitions of
> the words?
>
> Why don't you get the person who is telling you otherwise to explain how
> it could possibly be otherwise?
>
>
>
>
>
> > On Oct 5, 10:28 pm, skibud2 <·············@gmail.com> wrote:
> > > Barry --
>
> > > Thank you, thank you, thank you. That is what I was argument that I
> > > was making.
>
> > > Mike
>
> > > On Oct 5, 9:47 pm, Barry Margolin <······@alum.mit.edu> wrote:
>
> > > > In article <························@r29g2000hsg.googlegroups.com>,
>
> > > > skibud2 <·············@gmail.com> wrote:
> > > > > If you have a list of words that are ALL UNIQUE, and you call sort
> > > > > with a predicate of string< like this:
>
> > > > > (sort word-list #'string<)
>
> > > > > Will the sort be stable? Is there a reason to use stable-sort. I don't
> > > > > see a reason of hand, but I am being told otherwise. I can see it
> > > > > being unstable if there are some words that are equal. If it is
> > > > > unstable, please help me understand why.
>
> > > > Stability refers to the way that records with equivalent keys are
> > > > treated. If there aren't any, then the question "is it stable?" makes
> > > > no sense.
>
> > > > --
> > > > Barry Margolin, ······@alum.mit.edu
> > > > Arlington, MA
> > > > *** PLEASE post questions in newsgroups, not directly to me ***
> > > > *** PLEASE don't copy me on replies, I'll read them in the group ***
>
> --
> Barry Margolin, ······@alum.mit.edu
> Arlington, MA
> *** PLEASE post questions in newsgroups, not directly to me ***
> *** PLEASE don't copy me on replies, I'll read them in the group ***
In article <························@v3g2000hsg.googlegroups.com>,
skibud2 <·············@gmail.com> wrote:
> OK,
>
> I have to say I am a little frustrated; I don't get frustrated very
> easily, but I am now.
>
> Recently, I submitted a job application to a local company that does
> Lisp. As part of their application process, they requested each
> applicant to do a problem from their website. I completed the problem,
> tested it, and submitted it. The recruiter replied to me via e-mail
> saying that I needed to change my sort function calls to stable-sort.
>
> Naturally, my instinct was to understand why I needed to change my
> calls from sort to stable-sort. Since I was already familiar with sort
> and stable-sort issues, I didn't think that this request was correct.
> Either way, I brought up the good old common-lisp hyperspec and double
> checked whether I needed stable-sort; I concluded that I didn't need
> it. After going back and forth with the company, they finally told me
> the reviewer changed the code himself and it worked. However, I just
> don't understand how it stable-sort could have made a difference.
>
> Here is what I was doing. Please tell me if stable-sort would make a
> difference:
>
> (setf word-list '("foo" "bar" .. "foobar")) ;; Many words (which
> are actually from a file)
> (sort word-list #'string<)
> (setf *word-list-array* (make-array (length word-list) :initial-
> contents word-list))
>
>
> And from that point on, *word-list-array* was used to do a binary
> search for words. word-list was not used after the sort.
>
> The reviewer gave me a hint by telling me what word in the list was
> getting screwed up. The unique feature of the word was that another
> word was a substring of it (a prefix). However string< is supposed to
> handle this according to the common-lisp hyperspec. Therefore, I think
> it could be a bug with the reviewers version of common lisp, but I
> think I may have already sufficiently pissed him off by disagreeing
> with him. I guess I would have been better off just agreeing and
> making the changes. What do you all think?
>
> Mike
There are two errors in your code you show here:
1) '("foo" "bar") is a literal list.
Common Lisp does not allow you to change that list.
SORT may change it.
You need to cons up a fresh list before calling SORT.
If you read the list from a file, that would be fine.
2) SORT returns the sorted list. The variable holding the list
may not contain the sorted list, since SORT can destructively
modify it.
Write:
(setf word-list (sort word-list #'string<))
This will update the variable, too.
(let ((l (list 4 2 5 32 333)))
(let ((ls (sort l #'<)))
(print ls)
(print l)))
(2 4 5 32 333)
(4 5 32 333)
You see that ls has the sorted list, but not l. So you
need to set l to the result of SORT.
>
>
>
> On Oct 6, 10:57 pm, Barry Margolin <······@alum.mit.edu> wrote:
> > In article <························@y42g2000hsy.googlegroups.com>,
> >
> > skibud2 <·············@gmail.com> wrote:
> > > Can I get one more person agree with this argument?
> >
> > Come on. Isn't it trivially obvious, just based on the definitions of
> > the words?
> >
> > Why don't you get the person who is telling you otherwise to explain how
> > it could possibly be otherwise?
> >
> >
> >
> >
> >
> > > On Oct 5, 10:28 pm, skibud2 <·············@gmail.com> wrote:
> > > > Barry --
> >
> > > > Thank you, thank you, thank you. That is what I was argument that I
> > > > was making.
> >
> > > > Mike
> >
> > > > On Oct 5, 9:47 pm, Barry Margolin <······@alum.mit.edu> wrote:
> >
> > > > > In article <························@r29g2000hsg.googlegroups.com>,
> >
> > > > > skibud2 <·············@gmail.com> wrote:
> > > > > > If you have a list of words that are ALL UNIQUE, and you call sort
> > > > > > with a predicate of string< like this:
> >
> > > > > > (sort word-list #'string<)
> >
> > > > > > Will the sort be stable? Is there a reason to use stable-sort. I don't
> > > > > > see a reason of hand, but I am being told otherwise. I can see it
> > > > > > being unstable if there are some words that are equal. If it is
> > > > > > unstable, please help me understand why.
> >
> > > > > Stability refers to the way that records with equivalent keys are
> > > > > treated. If there aren't any, then the question "is it stable?" makes
> > > > > no sense.
> >
> > > > > --
> > > > > Barry Margolin, ······@alum.mit.edu
> > > > > Arlington, MA
> > > > > *** PLEASE post questions in newsgroups, not directly to me ***
> > > > > *** PLEASE don't copy me on replies, I'll read them in the group ***
> >
> > --
> > Barry Margolin, ······@alum.mit.edu
> > Arlington, MA
> > *** PLEASE post questions in newsgroups, not directly to me ***
> > *** PLEASE don't copy me on replies, I'll read them in the group ***
Hmmmm, I think your second point is the problem here. On Clisp it is
not a problem. Can you run the same thing using stable-sort?
Thanks,
Mike
On Oct 8, 6:31 pm, Rainer Joswig <······@lisp.de> wrote:
> In article <························@v3g2000hsg.googlegroups.com>,
>
>
>
> skibud2 <·············@gmail.com> wrote:
> > OK,
>
> > I have to say I am a little frustrated; I don't get frustrated very
> > easily, but I am now.
>
> > Recently, I submitted a job application to a local company that does
> > Lisp. As part of their application process, they requested each
> > applicant to do a problem from their website. I completed the problem,
> > tested it, and submitted it. The recruiter replied to me via e-mail
> > saying that I needed to change my sort function calls to stable-sort.
>
> > Naturally, my instinct was to understand why I needed to change my
> > calls from sort to stable-sort. Since I was already familiar with sort
> > and stable-sort issues, I didn't think that this request was correct.
> > Either way, I brought up the good old common-lisp hyperspec and double
> > checked whether I needed stable-sort; I concluded that I didn't need
> > it. After going back and forth with the company, they finally told me
> > the reviewer changed the code himself and it worked. However, I just
> > don't understand how it stable-sort could have made a difference.
>
> > Here is what I was doing. Please tell me if stable-sort would make a
> > difference:
>
> > (setf word-list '("foo" "bar" .. "foobar")) ;; Many words (which
> > are actually from a file)
> > (sort word-list #'string<)
> > (setf *word-list-array* (make-array (length word-list) :initial-
> > contents word-list))
>
> > And from that point on, *word-list-array* was used to do a binary
> > search for words. word-list was not used after the sort.
>
> > The reviewer gave me a hint by telling me what word in the list was
> > getting screwed up. The unique feature of the word was that another
> > word was a substring of it (a prefix). However string< is supposed to
> > handle this according to the common-lisp hyperspec. Therefore, I think
> > it could be a bug with the reviewers version of common lisp, but I
> > think I may have already sufficiently pissed him off by disagreeing
> > with him. I guess I would have been better off just agreeing and
> > making the changes. What do you all think?
>
> > Mike
>
> There are two errors in your code you show here:
>
> 1) '("foo" "bar") is a literal list.
> Common Lisp does not allow you to change that list.
> SORT may change it.
> You need to cons up a fresh list before calling SORT.
> If you read the list from a file, that would be fine.
>
> 2) SORT returns the sorted list. The variable holding the list
> may not contain the sorted list, since SORT can destructively
> modify it.
>
> Write:
>
> (setf word-list (sort word-list #'string<))
>
> This will update the variable, too.
>
> (let ((l (list 4 2 5 32 333)))
> (let ((ls (sort l #'<)))
> (print ls)
> (print l)))
>
> (2 4 5 32 333)
> (4 5 32 333)
>
> You see that ls has the sorted list, but not l. So you
> need to set l to the result of SORT.
>
>
>
> > On Oct 6, 10:57 pm, Barry Margolin <······@alum.mit.edu> wrote:
> > > In article <························@y42g2000hsy.googlegroups.com>,
>
> > > skibud2 <·············@gmail.com> wrote:
> > > > Can I get one more person agree with this argument?
>
> > > Come on. Isn't it trivially obvious, just based on the definitions of
> > > the words?
>
> > > Why don't you get the person who is telling you otherwise to explain how
> > > it could possibly be otherwise?
>
> > > > On Oct 5, 10:28 pm, skibud2 <·············@gmail.com> wrote:
> > > > > Barry --
>
> > > > > Thank you, thank you, thank you. That is what I was argument that I
> > > > > was making.
>
> > > > > Mike
>
> > > > > On Oct 5, 9:47 pm, Barry Margolin <······@alum.mit.edu> wrote:
>
> > > > > > In article <························@r29g2000hsg.googlegroups.com>,
>
> > > > > > skibud2 <·············@gmail.com> wrote:
> > > > > > > If you have a list of words that are ALL UNIQUE, and you call sort
> > > > > > > with a predicate of string< like this:
>
> > > > > > > (sort word-list #'string<)
>
> > > > > > > Will the sort be stable? Is there a reason to use stable-sort. I don't
> > > > > > > see a reason of hand, but I am being told otherwise. I can see it
> > > > > > > being unstable if there are some words that are equal. If it is
> > > > > > > unstable, please help me understand why.
>
> > > > > > Stability refers to the way that records with equivalent keys are
> > > > > > treated. If there aren't any, then the question "is it stable?" makes
> > > > > > no sense.
>
> > > > > > --
> > > > > > Barry Margolin, ······@alum.mit.edu
> > > > > > Arlington, MA
> > > > > > *** PLEASE post questions in newsgroups, not directly to me ***
> > > > > > *** PLEASE don't copy me on replies, I'll read them in the group ***
>
> > > --
> > > Barry Margolin, ······@alum.mit.edu
> > > Arlington, MA
> > > *** PLEASE post questions in newsgroups, not directly to me ***
> > > *** PLEASE don't copy me on replies, I'll read them in the group ***
In article <·······················@22g2000hsm.googlegroups.com>,
skibud2 <·············@gmail.com> wrote:
> Hmmmm, I think your second point is the problem here. On Clisp it is
> not a problem. Can you run the same thing using stable-sort?
STABLE-SORT has the same constraint. It is also destructive
and may change the original list. The only difference is
that it preserves the order of 'equal' elements in the
list.
Rainer Joswig <······@lisp.de> wrote:
> In article <·······················@22g2000hsm.googlegroups.com>,
> skibud2 <·············@gmail.com> wrote:
>
> > Hmmmm, I think your second point is the problem here. On Clisp it is
> > not a problem. Can you run the same thing using stable-sort?
>
> STABLE-SORT has the same constraint. It is also destructive
> and may change the original list. The only difference is
> that it preserves the order of 'equal' elements in the
> list.
And if you have just a single list, it doesn't matter if the order of
'equal' elements is preserved. Where stable sorts are needed is when
there are multiple "fields" in an element.
If there is a list like '(a b b a c d c d), then sorting it results in
'(a a b b c c d d). It doesn't matter which a, b, c, or d comes first.
So I'm having trouble buying the "string/substring" explanation.
Now suppose you have a list like '((a 2) (b 2) (b 1) (a 1) (c 2) (d 2)
(c 1) (d 1)). To put this in order, you'd first sort on the second
element, giving '((a 1) (b 1) (c 1) (d 1) (a 2) (b 2) (c 2) (d 2)).
Then you'd stable sort on the first element, because you want, for
example, (a 1) to stay before (a 2). A non-stable sort might leave (a
2) before (a 1).
Hope this helps.
BTW, as someone who has to interview people, I like it when candiates
challenge me -- as long as they're right! If a candidate left the
interview thinking that I screwed up, thought about it, and sent me an
e-mail the following day, if he (or she) was right I'd be mighty
impressed. The same is true if the candidate leaves thinking he/she
messed up and wanted to correct it. Passion + getting things done right
is a potent combination. If a boss gets upset because he's wrong and
you're right, then you don't want to work for them. IMO. YMMV.
OTOH, if you've claimed 10 years of experience in Lisp and don't know
that sort is destructive then nothing is going to help you.
From: Kent M Pitman
Subject: Re: Question about the sort function
Date:
Message-ID: <ufy0lgf4b.fsf@nhplace.com>
····@stablecross.com (Bob Felts) writes:
> > STABLE-SORT has the same constraint. It is also destructive
> > and may change the original list. The only difference is
> > that it preserves the order of 'equal' elements in the
> > list.
>
> And if you have just a single list, it doesn't matter if the order of
> 'equal' elements is preserved. Where stable sorts are needed is when
> there are multiple "fields" in an element.
Well, that depends on the ordering predicate and the nature of
equality. (Cue reference to my equality paper.) Consider the same
field being predicated multiple times, which effectively views the
same field as if it were multiple ones with differing predicates on
each pass; for example, numerically sorting numeric suffixes and then
doing a stable postpass to alphabetically sort prefixes in a
suffix-neutral way. The data is the same both times, but what counts
as "equal" or "lessp" is different on the two passes.
Going back to your original: It sounds like probably this STABLE-SORT
has the accidental property of its implementation that it happened to
give you back a pointer into the same list cells when no sorting (or
minimal sorting) was required. However, that's not a required aspect
of its behavior. Nothing keeps stable-sort from nreversing the result
(destroying the original list) and then consing up a new result that
was the elements in the stable order, leaving the caller pointing to
garbage, just as often happens in SORT. The stability STABLE-SORT
promises is the stability of order, not the integrity of individual
cons cells.
So my quick personal analysis is that you should not have quoted your
input for reasons others have probably cited; never destructively
modify constant data.
But the apparent argument by anyone that "because using a certain
operator leads to a desired functional effect it's ipso facto an
appropriate use of the operator" is really typical of the way newbies
get themselves in trouble... the use contracts of some operators in CL
are quite complicated in some cases for portability reasons and you can't
just rely on seeing an effect and assuming it valid. The "delete bug"
is a classic in this regard.
> OTOH, if you've claimed 10 years of experience in Lisp and don't know
> that sort is destructive then nothing is going to help you.
I like to believe that people are not required to know the entire
language to use it. It doesn't seem inconceivable to me someone could
go 10 years never using SORT, and yet be a good programmer. I often
look up the semantics of operators after almost 30 years of programing
Lisp, just because there are many Lisps and many semantics, and it never
hurts to re-read what an implementation is promising to make sure.
I think programming tests should be used narrowly for the purpose of
seeing how people think about problems; spot-testing for specific
knowledge and generalizing from trivia like that is a good way to
accidentally hire a well-prepared idiot or to lose a very good
candidate who happens to have a momentary lapse. In interview
questions, if someone missed that question, it would be reason to
probe further their understanding of destructive operations and their
significance.
Kent M Pitman <······@nhplace.com> wrote:
> ····@stablecross.com (Bob Felts) writes:
>
> > > STABLE-SORT has the same constraint. It is also destructive and may
> > > change the original list. The only difference is that it preserves the
> > > order of 'equal' elements in the list.
> >
> > And if you have just a single list, it doesn't matter if the order of
> > 'equal' elements is preserved. Where stable sorts are needed is when
> > there are multiple "fields" in an element.
>
> Well, that depends on the ordering predicate and the nature of
> equality. (Cue reference to my equality paper.) Consider the same
> field being predicated multiple times, which effectively views the
> same field as if it were multiple ones with differing predicates on
> each pass; for example, numerically sorting numeric suffixes and then
> doing a stable postpass to alphabetically sort prefixes in a
> suffix-neutral way. The data is the same both times, but what counts
> as "equal" or "lessp" is different on the two passes.
Which, in essence, has the sort looking at different fields, even though
it's the same element each time. Just trying to retain what little
dignity I have left... ;-)
[...]
>
> > OTOH, if you've claimed 10 years of experience in Lisp and don't know
> > that sort is destructive then nothing is going to help you.
>
> I like to believe that people are not required to know the entire
> language to use it.
Agreed. But where does one draw the line between enough and not enough?
At the moment, I'd rather lose a good candidate than hire a bad one.
Although I may have to revise this strategy, given what I think is the
coming implosion of engineering talent, even though it's often true that
a bad engineer is worse than no engineer.
> It doesn't seem inconceivable to me someone could go 10 years never using
> SORT, and yet be a good programmer.
It isn't inconceivable to me, either; but I would think it would be
rare. I've been doodling in Lisp as time permits for two years and have
had to use sort.
> I often look up the semantics of operators after almost 30 years of
> programing Lisp, just because there are many Lisps and many semantics, and
> it never hurts to re-read what an implementation is promising to make
> sure.
Even for Common Lisp? The Hyperspec is clear that sort and stable-sort
are destructive. Maybe I'm being naive...
> I think programming tests should be used narrowly for the purpose of
> seeing how people think about problems; spot-testing for specific
> knowledge and generalizing from trivia like that is a good way to
> accidentally hire a well-prepared idiot or to lose a very good
> candidate who happens to have a momentary lapse. In interview
> questions, if someone missed that question, it would be reason to
> probe further their understanding of destructive operations and their
> significance.
Sure. Granted, I was a bit abrupt in my statement; I don't reject
candidates because of not knowing something (unless they come across as
a self-proclaimed expert; they get little to no slack). I may also be a
bit jaded; I've interviewed too many engineers with 10 - 25 years
experience in C who just couldn't code simple stuff. In the last 5
people we've interviewed, we've had zero success. And that's with 5
people individually interviewing each candidate for at least 45 minutes
and we've all been unanimous in our assessments.
In article <··························@stablecross.com>,
····@stablecross.com (Bob Felts) wrote:
...
> Even for Common Lisp? The Hyperspec is clear that sort and stable-sort
> are destructive. Maybe I'm being naive...
It is not intuitive (at least for me) that one sorts a list
and the variable pointing to that list is not updated
to point to the sorted list. It is a consequence of
Lisp evaluation rules an the type of lists (made of cons cells)
it uses, but may not clear for somebody
who also uses programming languages where you
can pass variables differently or lists are implemented differently.
It is a typical topic for a Common Lisp tutorial explaining
how destructive list operations should be used.
...
Rainer Joswig <······@lisp.de> wrote:
> In article <··························@stablecross.com>,
> ····@stablecross.com (Bob Felts) wrote:
>
> ...
>
> > Even for Common Lisp? The Hyperspec is clear that sort and stable-sort
> > are destructive. Maybe I'm being naive...
>
> It is not intuitive (at least for me) that one sorts a list
> and the variable pointing to that list is not updated
> to point to the sorted list. It is a consequence of
> Lisp evaluation rules an the type of lists (made of cons cells)
> it uses, but may not clear for somebody
> who also uses programming languages where you
> can pass variables differently or lists are implemented differently.
>
> It is a typical topic for a Common Lisp tutorial explaining
> how destructive list operations should be used.
>
Well, even if the behavior of sort isn't intuitive (and I'm not arguing
that it is), shouldn't someone with 10 years of Lisp experience have
learned its behavior by then? I tend to think yes; Kent made an
argument that this might not be the case even with a good programmer.
I'm interested in other viewpoints. It seems to me that good artists
have to be familiar with their tools, and the more experienced claimed,
the better the familiarity. But, perhaps we agree on principle, but
aren't sure where to actually draw the line.
So, I never claimed to have 10 years of experience (in case any of you
were wondering). For some reason I had the impression that calling
sort on a list left the list as a sorted list; Clisp & SBCL does this,
but it is not standard Common Lisp. I am very familiar with lisp and I
use many languages. Sadly enough, my memory is not infinite and I
sometimes forget the details. Let's just say, I won't forget this
detail about sort from now on. ;)
However wrong I was, I am the type of person that will not change my
solution without understanding the reasoning. Changing sort to stable-
sort would have made the problem work, but it was the wrong answer.
That is the reason I posted this question on the user group. The
reviewer may have been annoyed with the fact that I was challenging
his requested fix, but the fact is: his fix was incorrect. I always
assumed there was something I was doing wrong, but I was pretty sure
it had nothing to do with stable-sort vs sort.
Well damn, that is one out of ten lisp jobs that I cannot apply to
anymore. Oh well. Next time I will just agree and figure it out later.
PS. I am really not a difficult person, although I sure feel like one
right now.
On Oct 9, 10:12 am, ····@stablecross.com (Bob Felts) wrote:
> Rainer Joswig <······@lisp.de> wrote:
> > In article <··························@stablecross.com>,
> > ····@stablecross.com (Bob Felts) wrote:
>
> > ...
>
> > > Even for Common Lisp? The Hyperspec is clear that sort and stable-sort
> > > are destructive. Maybe I'm being naive...
>
> > It is not intuitive (at least for me) that one sorts a list
> > and the variable pointing to that list is not updated
> > to point to the sorted list. It is a consequence of
> > Lisp evaluation rules an the type of lists (made of cons cells)
> > it uses, but may not clear for somebody
> > who also uses programming languages where you
> > can pass variables differently or lists are implemented differently.
>
> > It is a typical topic for a Common Lisp tutorial explaining
> > how destructive list operations should be used.
>
> Well, even if the behavior of sort isn't intuitive (and I'm not arguing
> that it is), shouldn't someone with 10 years of Lisp experience have
> learned its behavior by then? I tend to think yes; Kent made an
> argument that this might not be the case even with a good programmer.
> I'm interested in other viewpoints. It seems to me that good artists
> have to be familiar with their tools, and the more experienced claimed,
> the better the familiarity. But, perhaps we agree on principle, but
> aren't sure where to actually draw the line.
On 9 Oct, 15:51, skibud2 <·············@gmail.com> wrote:
> So, I never claimed to have 10 years of experience (in case any of you
> were wondering). For some reason I had the impression that calling
> sort on a list left the list as a sorted list; Clisp & SBCL does this,
> but it is not standard Common Lisp. I am very familiar with lisp and I
> use many languages.
My version of SBCL (1.09 I think) doesn't.
>(defparameter *test* (list 2 1 3 4))
*TEST*
>(sort *test*)
(1 2 3 4)
>*test*
(2 3 4)
In general, if you want the output of a function to be assigned to a
variable you called it with, you should do so explicitly.
It's good form, it signals your intentions, and generally only the
output (and not the side effects) of destructive functions are
guaranteed.
Mind you I'd probably use:
(make-array (length words) :initial-contents (sort words #'string<))
and skip the assignment entirely.
From: Don Geddis
Subject: Re: Question about the sort function
Date:
Message-ID: <87hckzy3hv.fsf@geddis.org>
skibud2 <·············@gmail.com> wrote on Tue, 09 Oct 2007:
> For some reason I had the impression that calling sort on a list left the
> list as a sorted list;
So, to better understand this issue, here's an exercise for you:
please write a sort function YOURSELF that works the way you think
this sort function should work.
(Hint: you may eventually discover that it's not possible to do it with
a function; you need a macro. And then you may realize that the ANSI CL
spec doesn't require leaving the original list as a sorted list, because
it's not actually possible, not because they were just being annoying.)
> Clisp & SBCL does this
That can't be true. It may accidentally work with the particular data you
happened to try once, but you have NOT described how those implementations
have implemented the SORT function.
> but it is not standard Common Lisp.
It's actually not a guarantee in any implementation. It might work, or might
not, for any given example on any given implementation. But you can basically
never count on it.
> However wrong I was, I am the type of person that will not change my
> solution without understanding the reasoning. Changing sort to stable-
> sort would have made the problem work, but it was the wrong answer.
That's true.
> The reviewer may have been annoyed with the fact that I was challenging his
> requested fix, but the fact is: his fix was incorrect. I always assumed
> there was something I was doing wrong, but I was pretty sure it had nothing
> to do with stable-sort vs sort.
Your intuition was correct.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
No matter how hard you throw a dead fish in the water, it still won't swim.
In article <··············@geddis.org>, Don Geddis <···@geddis.org>
wrote:
> skibud2 <·············@gmail.com> wrote on Tue, 09 Oct 2007:
> > For some reason I had the impression that calling sort on a list left the
> > list as a sorted list;
>
> So, to better understand this issue, here's an exercise for you:
> please write a sort function YOURSELF that works the way you think
> this sort function should work.
>
> (Hint: you may eventually discover that it's not possible to do it with
> a function; you need a macro.
No you don't. If you move the elements around by assigning the CARs
rather than relinking the CDRs, you can reorder the list in place.
(defun sort-in-place (list pred)
(let ((temp-list (sort (copy-list list) pred)))
(loop for cons on list
for element in temp-list
do (setf (car cons) element))))
> (setq *l* (list 3 2 5 4))
(3 2 5 4)
> (sort-in-place *l* '<)
nil
> *l*
(2 3 4 5)
You're correct for some destructive functions, though. For instance,
DELETE might need to return NIL if it deletes all the elements of the
list. This can't be accomplished by updating the list in place, you
have to assign to the original variable that points to it.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
From: Don Geddis
Subject: Re: Question about the sort function
Date:
Message-ID: <87y7eavsan.fsf@geddis.org>
Barry Margolin <······@alum.mit.edu> wrote on Wed, 10 Oct 2007:
> In article <··············@geddis.org>, Don Geddis <···@geddis.org> wrote:
>> So, to better understand this issue, here's an exercise for you:
>> please write a sort function YOURSELF that works the way you think
>> this sort function should work.
>> (Hint: you may eventually discover that it's not possible to do it with
>> a function; you need a macro.
>
> No you don't. If you move the elements around by assigning the CARs
> rather than relinking the CDRs, you can reorder the list in place.
All right! All right. I concede.
So then it _was_ a good homework assignment after all! (Better than I
thought.)
> You're correct for some destructive functions, though. For instance,
> DELETE might need to return NIL if it deletes all the elements of the
> list. This can't be accomplished by updating the list in place, you
> have to assign to the original variable that points to it.
Yeah, yeah. So do I get partial credit for having vaguely recalled this
case, but inappropriately assuming it also applied to SORT?
It seems I need to study harder for the next exam...
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
It's easy to sit there and say you'd like to have more money. And I guess
that's what I like about it. It's easy. Just sitting there, rocking back and
forth, wanting that money. -- Deep Thoughts, by Jack Handey
From: Robert Maas, see http://tinyurl.com/uh3t
Subject: Re: Question about the sort function
Date:
Message-ID: <rem-2007oct11-004@yahoo.com>
> From: Don Geddis <····@geddis.org>
> So, to better understand this issue, here's an exercise for you:
> please write a sort function YOURSELF that works the way you think
> this sort function should work.
> (Hint: you may eventually discover that it's not possible to do it with
> a function; you need a macro. And then you may realize that the ANSI CL
> spec doesn't require leaving the original list as a sorted list, because
> it's not actually possible, not because they were just being annoying.)
Incorrect. See the hack I wrote a few minutes ago, elsewhere in
this thread, which does the original sort but then swaps the
original and new first-elements in the list, and does a bunch of
RPLACDs to patch the list structure to swap the original and new
head cell, thereby getting the effect that the OP expected, at
great pain, but nevertheless *possible*.
skibud2 wrote:
> However wrong I was, I am the type of person that will not change my
> solution without understanding the reasoning. Changing sort to stable-
> sort would have made the problem work, but it was the wrong answer.
> That is the reason I posted this question on the user group. The
> reviewer may have been annoyed with the fact that I was challenging
> his requested fix, but the fact is: his fix was incorrect. I always
> assumed there was something I was doing wrong, but I was pretty sure
> it had nothing to do with stable-sort vs sort.
>
> Well damn, that is one out of ten lisp jobs that I cannot apply to
> anymore. Oh well. Next time I will just agree and figure it out later.
In your case, if some company insists on your changing something for the
wrong reason, and are annoyed at your challenging them on it, is it
really a loss if you can not apply to them anymore? I'm beginning to
think that when I go into a job interview, I need to bring a list of
technical questions for me to ask the person interviewing me. If they
would get annoyed with my asking such questions or with my not simply
accepting something they're telling me, I think that this would be an
indication of what it would be like to work with that person.
From: Robert Maas, see http://tinyurl.com/uh3t
Subject: Re: Question about the sort function
Date:
Message-ID: <rem-2007oct11-003@yahoo.com>
> From: Rainer Joswig <······@lisp.de>
> It is not intuitive (at least for me) that one sorts a list and
> the variable pointing to that list is not updated to point to the
> sorted list.
In virtually any common programming language, even C, parameters
are passed by value. No assign-back ever occurs. If you write a
function call with a simple variable given in the syntax for a
parameter, what is passed is a copy of the value of that variable,
not a reference to the variable, so there is no way whatsoever that
the function called could update the variable even if it wanted to.
So when you pass a pointer to a structure, such as a sequence, what
is the *object* that is passed? In Java, when you pass a container
containing a whole sequence, generally you pass a toplevel
framework that encapsulates the whole sequence, and you can then
ask some function to rearrange elements, and the toplevel framework
now has the new sequence. But in lisp, when you pass a list to a
function, the thing you pass is just a pointer to a single CONS
cell, whose CAR is the first element of the list, with the rest o
the list daisy-chained onto the CDR of that single CONS cell. If a
function is called to rearrange the list and return a rearranged
list, that original pointer to that original CONS cell still points
to that CONS cell, not to some other CONS cell that is now at the
front of the returned list.
By comparison, an array is a whole object in Lisp, so any function
that rearranges the elements of the array in-place will probably
cause the original pointer-to-array to now point to that same array
which is in fact now in the new ordering.
Now if you encapulated a list in an extra level of structure, and
wrote a function that sorted the list and assigned it back to the
extra level, then you could have the effect you want, for example:
(defun make-encapsulated-list (l)
(list :EL l))
(defun is-encapsulated-list (el)
(eq :EL (car el)))
(defun check-encapsulated-list (el)
(unless (is-encapsulated-list el)
(error "Invalid argument, not an encapsulated-list: %S" el)))
(defun encapsulated-list-extract (el)
(check-encapsulated-list el)
(cadr el))
(defun encapsulated-list-sort (el sortfn)
(check-encapsulated-list el)
(setf (cadr el) (sort (cadr el) sortfn))
el)
(setq l1 (list 3 7 5 1))
(setq el1 (make-encapsulated-list l1)) ;At this point l1 is garbage
(encapsulated-list-sort el1 #'<) ;Container is modified in place, no setq needed
(setq l2 (encapsulated-list-extract el1))
Normally it'd be easier to just remember to do a setq when you call
sort directly. But I can imagine a situation where there are
multiple pointers to a single sequence, and you want that single
sequence sorted once, and then all the references will
automatically share that newly-sorted sequence, especially if you
might want to sort the same sequence per several different sorting
functions and each time have all references immediately share that
newly-resorted sequence, where encapsulating as above (or using
CLOS to create a fullfledged OO-object) might be useful.
An alternative is to write a wrapper around sort which makes sure
the original CONS cell is still at the front of the list, by
swapping CARs between the old head and new head and also swapping
the CONS cells themselves. But the code for that would be *hairy*,
because you have to first find where the old CONS cell is within
the newly sorted list, but actually find the CONS cell just before
it in the sorted list so that its CDR can be modified, and deal
with lots of special cases as to whether the old head-CONS is now
in first or second or third-or-later position. Putting a wrapper
around the whole list and SETFing it inside the wrapper, as I did
above, is so much easier to code correctly, IMO.
But here's my attempt at the messy thing:
(defun sort-keeping-head-cell (oldhead sortfn)
(let* ((tmphead (sort oldhead sortfn))
(ix (position (car oldhead) tmphead)))
(cond ((null tmphead)) ;Empty list, no patch needed
((= 0 ix)) ;Same old head, no patch needed
((= 1 ix)
(rotatef (car tmphead) (car oldhead))
(rplacd tmphead (cdr oldhead))
(rplacd oldhead tmphead))
(t (let ((preold (nthcdr (+ -1 ix) tmphead))
(postold (cdr oldhead)))
(rotatef (car tmphead) (car oldhead))
(rplacd oldhead (cdr tmphead))
(rplacd preold tmphead)
(rplacd tmphead postold))))
oldhead))
(setq l1 (list 3 7 5 1))
(sort-keeping-head-cell l1 #'<) ;IX was 1
l1
(setq l1 (list 7 3 5 1))
(sort-keeping-head-cell l1 #'<) ;IX was 3
l1
;It works! But what a mess to show the person who has check your code for bugs!
On Mon, 08 Oct 2007 22:19:16 -0000, skibud2 <·············@gmail.com> tried to
confuse everyone with this message:
>OK,
>
>I have to say I am a little frustrated; I don't get frustrated very
>easily, but I am now.
>
>Recently, I submitted a job application to a local company that does
>Lisp. As part of their application process, they requested each
>applicant to do a problem from their website. I completed the problem,
>tested it, and submitted it. The recruiter replied to me via e-mail
>saying that I needed to change my sort function calls to stable-sort.
>
>Naturally, my instinct was to understand why I needed to change my
>calls from sort to stable-sort. Since I was already familiar with sort
>and stable-sort issues, I didn't think that this request was correct.
>Either way, I brought up the good old common-lisp hyperspec and double
>checked whether I needed stable-sort; I concluded that I didn't need
>it.
>After going back and forth with the company, they finally told me
>the reviewer changed the code himself and it worked.
Love it! I can just imagine his thoughts: "That doesn't work. I wonder
why? It SHOULD work! Why doesn't it sort??? Perhaps the sort function is
too unstable for strings? Let's change it to stable-sort... Whoa!"
Little did he now that it was just pure luck.
>However, I just
>don't understand how it stable-sort could have made a difference.
>
>Here is what I was doing. Please tell me if stable-sort would make a
>difference:
>
> (setf word-list '("foo" "bar" .. "foobar")) ;; Many words (which
>are actually from a file)
> (sort word-list #'string<)
> (setf *word-list-array* (make-array (length word-list) :initial-
>contents word-list))
o_O
<ubersnip>
--
|Don't believe this - you're not worthless ,gr---------.ru
|It's us against millions and we can't take them all... | ue il |
|But we can take them on! | @ma |
| (A Wilhelm Scream - The Rip) |______________|
skibud2 <·············@gmail.com> wrote:
+---------------
| If you have a list of words that are ALL UNIQUE, and you
| call sort with a predicate of string< like this:
| (sort word-list #'string<)
+---------------
Others have addressed your question about the sort being stable,
but since no-one else mentioned it... The bare expression:
(sort word-list #'string<)
returns the sorted list, true, but does *not* leave the sorted
list in WORD-LIST. As it says in CLHS "Function SORT, STABLE-SORT":
The sorting operation can be destructive in all cases.
In the case of a vector argument, this is accomplished
by permuting the elements in place. In the case of a list,
the list is destructively reordered in the same manner
as for nreverse.
This means that the following result is perfectly legal:
> (let ((word-list (list :foo :bar :baz :quux)))
(sort word-list #'string<)
...[other stuff]...
word-list)
(:FOO :QUUX)
>
For this reason, if you want the sorted result you must save
it somehow, e.g.:
> (let ((word-list (list :foo :bar :baz :quux))
result)
(setf result (sort word-list #'string<))
...[other stuff]...
result)
(:BAR :BAZ :FOO :QUUX)
>
-Rob
p.s. If you already knew this and simply didn't bother to show
the saving of the SORT result in your question/example, then my
apologies for the unnecessary tutorial. It's just that a SORT
outside of the context of a SETF [or as an argument to another
immediate function call] almost always signals a mistake.
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607