难以编写LISP递归函数进行合并排序

Question

嗨,所以我有疑问,我有一些困难解决,见下文

使用函数SPLIT-LIST和MERGE-LISTS来定义递归Lisp函数MSORT,使得如果L是实数列表,则(MSORT L)是由L的元素按升序组成的列表.在MSORT的定义中,您可以调用SPLIT-LIST,MSORT本身,MERGE-LISTS,CAR,CDR,CADR和ENDP,但是您不应该调用任何其他函数.一定要使用LET或LET*,这样MSORT只能调用一次SPLIT-LIST.

到目前为止,我能够正确编写SPLIT-LIST和MERGE-LISTS函数,但对于M-SORT,我在编写函数时遇到了困难.到目前为止,请参见以下所有三个定 如何按照问题中的指南正确编写MSORT功能的任何帮助将不胜感激.

(defun SPLIT-LIST (L)
  (if (endp L)
      '(nil nil)
    (let ((X (split-list (cdr L))))
      (list  (cons (car L)(cadr X)) (car X) ))))

(defun MERGE-LISTS (L1 L2)
  (cond
   ((and(endp L1 )(endp L2)) nil )
   ((endp L1) (cons (CAR L2) (MERGE-LISTS nil (CDR L2))))
   ((endp L2) (cons (CAR L1) (MERGE-LISTS (CDR L1) NIL)))
   ((< (CAR L1) (CAR L2)) (cons (CAR L1) (MERGE-LISTS (CDR L1) L2  )))  
   ((>= (CAR L1) (CAR L2)) (cons (CAR L2) (MERGE-LISTS L1 (CDR L2))  ))))

(defun MSORT (L)
  (cond ((endp L ) nil)
        ( (equal (Length L) 1) L)
        (T
         (let* (
                (S (SPLIT-LIST L ))
                (L1 (CAR S))
                (L2 (CADR S))
                (X (MSORT (cdr L1)))
                (Y (MSORT (cdr L2)))


                )
           (MERGE-LISTS 
            (if (and (numberp (car L1)) (numberp (car X))(<=  (car L1 ) (car X)))  
                (list (car L1) (car X))
              (list (car X) (car L1) )
              ) 

            (Cons (car L2) Y))

           )))
  )

Answer 1

你过度复杂了.您不需要对CDR返回的子列表进行SPLIT-LIST排序,只需对整个列表进行排序,然后合并它们.

(defun MSORT (L)
  (cond ((endp L) nil)
        ((endp (cdr L)) L)
        (t
         (let* ((S (SPLIT-LIST L ))
                (L1 (car S))
                (L2 (cadr S))
                (X (MSORT L1))
                (Y (MSORT L2)))
           (MERGE-LISTS X Y)))))