Scheme代码，用于根据作为函数参数传递的运算符对嵌套列表进行排序

Please help me to write a code in scheme since being a beginner I am having a bit trouble in recursive code:

请帮我写一个方案中的代码,因为作为初学者我在递归代码中有点麻烦:

I want a code like:

我想要一个代码:

1) (my_fn 'a symbol<?) should output---> a
2)(my_fn '((((a)) b) c) symbol<?) ---> '((((a)) b) c)
3)(my_fn '(1 (20 (3 (4 40) 3) 2) 1) >) ---->'(40 (20 (4 (3 3) 2) 1) 1)
4)(my_fn '((((a)) b) c) (lambda (x y) (symbol<? y x))) Output---> '((((c)) b) a)

1)(my_fn'符号 a 2)(my_fn'(((((a))b)c)符号 '((((a))b )c)3)(my_fn'(1(20(3(4 40)3)2)1)>)---->'(40(20(4(3 3)2)1)1)4) (my_fn'(((((())b)c)(lambda(xy)(符号 '(((((c))b)a)

1 个解决方案

#1

The way to sort the atomic elements is to flatten the list:

对原子元素进行排序的方法是将列表展平:

(flatten '(((4) 2) 3)) ; ==> (4 2 3)

Then you can use the standard list-sort (R6RS here, for R5RS use SRFI-95 sort instead)

然后你可以使用标准列表排序(R6RS在这里,对于R5RS使用SRFI-95排序)

(list-sort < '(4 2 3)) ; ==> (2 3 4)

Then you need some way of recursing the original structure and for each atomic value you use one of the values in the sorted list instead:

然后,您需要一些递归原始结构的方法,并且对于每个原子值,您使用排序列表中的一个值:

(restructure '(((4) 2) 3) '(2 3 4)) ; ==> (((2) 3) 4)

Here is a version of restructure that would work, but it uses mutation:

这是一个可以工作的重组版本,但它使用了变异:

;; (restructure '(((a) b) c) '(1 2 3)) ; ==> (((1) 2) 3)
(define (restructure tree elements)
  ;; replaces an atom with the next 
  ;; element in elements
  (define (term x)
    (let ((x (car elements)))
      (set! elements (cdr elements))
      x))

  (accumulate-tree tree term cons '()))

Finally you put it all together. A possible implementation would look like this:

最后你把它们放在一起。可能的实现如下所示:

(define (structure-sort < tree)
  (if (pair? tree)
      (restructure tree 
                   (list-sort < (flatten tree)))
      tree)) ; for atomic values there isn't anything to sort

Now. If I have a structure with data you can sort the atomic values in the structure into something that doesn't make sense:

现在。如果我有一个包含数据的结构,你可以将结构中的原子值排序成没有意义的东西:

(structure-sort string<? '("person" ("name" "John") ("number" "555-8907")))
; ==>  ("555-8907" ("John" "name") ("number" "person"))

#1