Sort a list by number and char

user_14840130 0
Viewed 118

I have the list in LISP:

((1 b) (1 a) (2 D) (1 z) (1 t) (2 a) (3 n))

I have to order it first on the number and if equal on the lexichographic order of the char, the output should be:

((1 a) (1 b) (1 t) (1 z) (2 a) (2 d) (3 n))

I have tried to sort on one parameter and then the other, how can I compose the two function ?

;;(sort '((1 b) (1 a) (2 D) (1 z) (1 t) (2 a) (3 n)) #'< :key #'car )
;;(sort '((1 b) (1 a) (2 D) (1 z) (1 t) (2 a) (3 n)) #'string< :key #'second )

Are there easier ways to do it?

Thanks

common-lisp lisp list sorting
2 Answers

You have basically two options:

  • define a comparison function of two elements (x0 y0) and (x1 y1) that returns T if:

    • x0 < x1, or
    • x0 and x1 are equivalent [*] and y0 <' y1.

    You could also generalize this solution by defining a higher-order functions that accepts a list of test and key parameters and combines them to create a comparison function that applies them all on two values.

    [*] equivalence being defined as neither a < b or b < a in the general case when < is a user-provided comparison function.

  • sort the list once to compare the respective second fields of entries, then call stable-sort on the result to sort according to the first field: you have to start from least significant field (changing the order of application of sorts changes the results). For example:

    ((1 c) (2 b) (0 a) (1 b))

    sort by second field #'string<

    ((0 a) (1 b) (2 b) (1 c))

    then stable-sort by first field #'<

    ((0 a) (1 b) (1 c) (2 b))    #### RES 1

    The result would be as follows by sorting by the first field first:

    ((0 a) (1 c) (1 b) (2 b))

    Then (stably) by the second:

    ((0 a) (1 b) (2 b) (1 c))    #### RES 2

    By calling stable-sort, when the first field of two elements are equal, the stability of the sort guarantees they will keep being sorted by their second field. You can apply stable-sort multiple times if you have more fields to compare.

Be careful, in Common Lisp sort mutates the input.

user_1243190

As coredump says, since you really need a list comparison function, a nice approach is do the meta thing: don't write one, but write a function which makes functions which compare lists. Here is such a function:

(defun make-list-comparator (&rest predicates)
  (labels ((tails< (l1t l2t pt)
             (let ((< (first pt))
                   (e1 (first l1t))
                   (e2 (first l2t)))
               (cond
                ((funcall < e1 e2) t)
                ((funcall < e2 e1) nil)
                ((and (null l1t) (null l2t) (null pt)) nil)
                ((or (null l1t) (null l2t) (null pt))
                 (error "crashed into the end"))
                (t (tails< (rest l1t) (rest l2t) (rest pt)))))))
    (lambda (l1 l2)
      (tails< l1 l2 predicates))))

And now

> (sort (copy-list '((1 b) (1 a) (2 D) (1 z) (1 t) (2 a) (1)))
        (make-list-comparator
         #'<
         (lambda (s1 s2)
           (string< (string s1) (string s2)))))
((1 a) (1 b) (1 t) (1 z) (2 a) (2 d) (3 n))
Admin1
Related