Как улучшить эту схему слияния?

Я программист на C++, я написал этот код, чтобы посмотреть, могу ли я мыслить функционально :) Какие-нибудь намеки, чтобы улучшить его ?

(define (append listOne listTwo)
  (cond
    ((null? listOne) listTwo)
    (else (cons (car listOne) (append (cdr listOne) listTwo)))))

(define (merge listOne listTwo)
  (cond
    ((null? listOne) listTwo)
    ((null? listTwo) listOne)
    ((< (car listOne) (car listTwo))
     (append (cons (car listOne) '())
             (merge (cdr listOne) listTwo)))
    ((= (car listOne) (car listTwo))
     (append (cons (car listOne) '())
             (merge (cdr listOne) listTwo)))
    (else (append (cons (car listTwo) '())
                  (merge listOne (cdr listTwo))))))

(define (mergesort lis)
  (cond
    ((null? lis) '())
    ((null? (cdr lis)) lis)
    (else (merge (cons (car lis) '())
                 (mergesort (cdr lis))))))

(mergesort '(99 77 88 66 44 55 33 11 22 0))
2 2
algorithm scheme mergesort

2 ответа:

Есть только одно небольшое улучшение, которое я вижу: 

(append (cons (car listTwo) '())
              (merge listOne (cdr listTwo))))

Можно везде упростить до 

(cons (car listTwo)
      (merge listOne (cdr listTwo)))

Я думаю, вы думали о чем-то вроде (в синтаксисе Python-esque): 

[car(listTwo)] + merge(listOne, cdr(listTwo))

Но минусы добавляют элемент непосредственно в начало списка, как функционал push, так что это похоже на следующий код: 

push(car(listTwo), merge(listOne, cdr(listTwo)))

В конечном счете дополнительное добавление приводит только к двойному выделению ячеек для каждого элемента, так что это не так уж и важно.

Кроме того, я думаю, что вы могли бы стать лучше. производительность, если вы сделали mergesort fancier таким образом, что он поддерживает длину списка и сортирует обе половины списка на каждом шаге. Это, вероятно, не подходит для такого примера обучения, как этот.

Что-то вроде: 

(define (mergesort l)
  (let sort-loop ((l l) (len (length l)))
    (cond
      ((null? l) '())
      ((null? (cdr l)) l)
      (else (merge (sort-loop (take (/ len 2) l) (/ len 2)))
                   (sort-loop (drop (/ len 2) l) (/ len 2)))))))))
(define (take n l)
  (if (= n 0)
      '()
      (cons (car l) (take (sub1 n) (cdr l)))))
(define (drop n l)
  (if (= n 0)
      l
      (drop (sub1 n) (cdr l))))
3

Вообще, mergesort делает много манипуляций со списком, поэтому гораздо лучше делать все деструктивно, сортируя подразделы "на месте". Вы можете увидеть реализацию sort в схеме PLT на примере общего кода, который возник в SLIB. (На первый взгляд это может показаться пугающим, но если Вы читаете комментарии и игнорируете кнопки и оптимизации, вы увидите все это там.)

Кроме того, вы должны посмотреть на SRFI-32 для расширенного обсуждения a интерфейс сортировки.

1