Как улучшить это объединение в схеме?

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

может везде быть упрощена

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

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

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

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

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

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

Кроме того, я думаю, что вы можете получить более высокую производительность, если вы сделали 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)))) 

Answer 2

В общем, mergesort делает много список манипуляций, поэтому гораздо лучше делать вещи деструктивно сортировкой югу частей «на месте». Вы можете увидеть implementation of sort in PLT Scheme, например, общий код, созданный в SLIB. (Это может показаться пугающим с первого взгляда, но если вы прочтете комментарии и проигнорируете ручки и оптимизацию, вы увидите все это там.)

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