对嵌套列表进行排序

Question

我想按字母顺序对嵌套的字符串列表进行排序，例如：

(list 
   (list "Worcestershire" "Edinburgh")
   (list "Suffolk" "Liverpool")
   (list "Norfolk" "York")
   (list "Lincoln" "Malmesbury")
   (list "Glasgow" "Desmond"))

所以对于这个，我只想按每个子列表中的第一个单词对其进行排序（请暂时忽略第二个单词）。我的代码在这里：

(define (sort lst)
  (cond [(empty? lst) empty]
        [else (insert (first (first lst)) (second (first lst))
                      (sort (rest lst)))]))

;; helper function
(define (insert element1 element2 lst)
   (cond [(empty? lst) (list element1 element2)]
         [(string<=? element1 (first lst)) (cons element1 lst)]
         [else (cons (first lst) (insert element1 element2 (rest lst)))]))

程序理论上应该产生

(list 
    (list "Glasgow" "Desmond")
    (list "Lincoln" "Malmesbury")
    (list "Norfolk" "York")
    (list "Suffolk" "Liverpool")
    (list "Worcestershire" "Edinburgh"))

但现在正在生产

(list "Glasgow" "Desmond" "Lincoln" "Malmesbury" 
      "Norfolk" "Suffolk" "Worcestershire" "York")

该列表未嵌套，甚至缺少一些组件！有人可以检查我的代码吗？

Answer 1

你写了

(define (sort lst)
  (cond [(empty? lst) empty]
        [else (insert (first (first lst)) 
                      (second (first lst))
                      (sort (rest lst)))]))

这显然假设lst是[(a1 b1) (a2 b2) ... (an bn)]，然后它定义（用伪代码写）

sort [(a1 b1) (a2 b2) ... (an bn)]
 == 
insert a1 b1 (sort [(a2 b2) ... (an bn)])

和sort [] == [].

由此我们可以看出它必须满足

sort [(a1 b1)] == insert a1 b1 (sort [])
               == insert a1 b1 []
  == [(a1 b1)]

这给了我们 insert 的部分定义，甚至在我们开始自己编写它之前。

因此，您对 insert 的定义必须更正为

;; helper function
(define (insert e1 e2 lst)
  (cond [(empty? lst)     (list (list e1 e2))]
        [(string<=? e1 (first (first lst)))
                          (cons (list e1 e2) lst)]
        [else   (cons (first lst) 
                      (insert e1 e2 (rest lst)))]))

对嵌套列表进行排序

Sorting A Nested List

sorting

scheme

list

racket