スキームでこのmergesortを改善するには？

Question

私は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)) 

Answer 1

私が見る唯一の小さな改善があります：

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

はどこでも、私はあなたが（Pythonの風の構文で）のようなものを考えていたと思います

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

に単純化することができます：

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

ただし、機能pushようなリストの前に直接アイテムを追加しますので、次のコードのようなものだ：それは大きくはないですので、最終的に余分な追記のみ各項目のダブルコンスセルの割り当てになり

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

対処。

さらに、mergesortを魅力的にして、リストの長さを維持し、各ステップでリストの半分をソートすると、パフォーマンスが向上すると思います。しかし、これはおそらくこのような学習の例には適していません。

ような何か：

一般に

(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)))) 

Answer 2

、mergesortは、リスト操作の多くをやっているので、「インプレース」のサブパーツをソートすることにより、破壊的なことを行うためにはるかに優れています。 implementation of sort in PLT Scheme（SLIBに由来する共通コードなど）が表示されます。 （一見すると怖いかもしれませんが、コメントを読んでノブと最適化を無視すると、そこにすべてが表示されます）

また、SRFI-32を見ると、並べ替えの詳細な説明がありますインタフェース。