Common-Lisp: How to sort the characters of a string?

Question

I know how to do this in every other language that I know, but I'm just starting Lisp and not quite getting it. My idea of

• make a list of characters
• convert to ascii values
• sort
• convert back to characters
• convert back to a string

Seems heavy-handed. Is there some better way to do this? I'm trying to write a function that, given a string, returns a string with the letters sorted. So, for example:

gate => aegt
house => ehosu
door => door

This routine will be used as part of an anagram-finder.

Thanks!

Fellah

Answer 1

In Common Lisp strings are sequences, and sort works on any sequence type, so it will do the trick.

Here's an example:

(let ((the-string (copy-seq "this is the string")))
  (sort the-string #'char-lessp))
;; => "   eghhiiinrsssttt"

And here's the Hyperspec entry for sort and stable-sort. Just pick your predicate (the second argument to sort) to get your desired sort order.

Note that I used copy-seq in the example because sort is destructive - it modified the string in-place.

Hoarding

Great explanation, thanks. Is #'char-lessp preferred over #'char<, or is that just a stylistic thing? – Fellah

Thanks Olie, glad I could help. The difference is that #'char-lessp ignores case while #'char< does not. (The same is true of #'string-lessp compared to #'string<). – Hoarding

I think that copying a literal string is a bit excessive... you cannot possibly affect anything else by changing it in place because you just defined it here. – Pap

wxvw, very true. I just used it as hook to talk about sort being destructive. Interestingly, after I posted I noticed that the CLHS does the same. Maybe because of a general desire to avoid mutating literal data? Though I haven't thought of that applying to strings. – Hoarding

wxvw: true, but a more common case is to put a held-string (variable) into the situation. The "hello" example is just an example. Without the copy-seq, my code didn't work, so I'm glad it was in the answer! :) – Fellah

Copy-seq should prob be placed within the sort function; otherwise the the-string variable is destructively modified – Immolate

@wvxvw Constant-folding... I think (although I would have to read the CLHS with some care to confirm) that a CL implementation is perfectly allowed to fold (let ((a "foo") (b "foo")) ...) into (let ((#:temp "foo)) (let ((a #:temp) (b #:temp)) ...)) and in that case sorting a would, as a surprising side-effect, sort b. – Brain

@Brain well, even if it was possible, why would you ever do that? CL doesn't make any promises w/r to string immutability (unlike C, for example, where the consequences of modifying a statically allocated constant string are undefined). I think that a Lisp compiler, if it ever wanted to optimize that would have to come up with a proof, that the string isn't modified elsewhere... otherwise, that would be too "bold". – Pap

@wvxvw It is no different than "please don't mutate any quoted list in source" (where I know that constant-folding is allowed). If you replace "foo" with '(foo bar), the same argument holds. – Brain

@Brain nope, it is, the standard has to describe the operations on literal string as "unsafe" in some way, but I've not seen any such warning. Literal strings aren't considered constant data, symbols are constant strings of sorts, but regular strings - why would they be? That would be too taxing to require one to create mutable strings by writing something like (coerce '(\#f \#o \#o) 'string)... – Pap

To continue, by the same token, this #(1 2 3) would have to be considered constant data, likewise any printed representation of any object... There is a point in considering all quoted things to be constants, but just any literal? I don't think so... – Pap

@wvxvw, LispWorks's documentation explicitly identifies strings (and vectors generally) as eligible for constant folding. In the examples at the bottom they recommend against mutating vectors defined as literals without using copy-seq. – Hoarding

@Hoarding well... I'd trust them to know the standard better then I do :) still, this feels like a very liberal interpretation... nevertheless, good to know! – Pap

Answer 2

The sort function takes a sequence, which a string already is, so your only problem is finding the right comparison function. Characters are not numbers, so you should use the character comparison functions, e.g. char>:

* (sort (copy-seq "hello") #'char>)

"ollhe"

Footway

Ah thanks! I knew strings were sequences, but didn't know about #'char> -- perfect! – Fellah

Btw, your answer was correct & first, but I selected jbm's as (a) he gave a bit more detail, which was helpful to my case and (b) I wanted to encourage a low-rep poster who gives great answers (I think he was 2xx at the time I selected it.) So: nothing personal, your answer was great, too! But SO says "there can be only one." ;) – Fellah

Answer 3

A string is a sequence of characters. sort sorts sequences so it sorts a string like it sorts a list:

(setq tester (copy-seq "lkjashd")) =>  "lkjashd"
(stable-sort tester #'char-lessp) =>  "adhjkls"
tester => "adhjkls" ; NB: it mutates the string!

Applewhite