スキーム - ユーザー定義ソートと平均関数を使用してメジアンを見つける方法

Question

私はSchemeを初めて使い、壁に当たった。私はソートと平均関数を持っており、私はこのサイトで見つかった関数の中央値を変更しようとしています。しかし、何を試しても、メディアン関数に複数の式がある場合はエラーが発生します。メディアン関数でソートを使用しようとすると、「未定義」になります。

(define (sort1 L) 
    (if (or (null? L) (<= (length L) 1)) L 
    (let loop ((l null) (r null) 
     (pivot (car L)) (rest (cdr L))) 
     (if (null? rest) 
      (append (append (sort1 l) (list pivot)) (sort1 r)) 
     (if (<= (car rest) pivot) 
      (loop (append l (list (car rest))) r pivot (cdr rest)) 
      (loop l (append r (list (car rest))) pivot (cdr rest))))))) 

(define (avg lst) 
    (let loop ((count 0) (sum 0) (args lst)) 
    (if (not (null? args)) 
     (loop (add1 count) (+ sum (car args)) (cdr args)) 
     (/ sum count)))) 

(define (median L) 
(if (null? L) (error "The list is empty") 
    (let loop ((L1 L) (L2 L)) 
     (cond ((null? (cdr L2)) (car L1)) 
      ((null? (cddr L2)) (list (car L1) (cadr L1))) 
      (else (loop (cdr L1) (cddr L2))))))) 

私は最初のリストをソートするために、中央値関数を編集しようとしている、と偶数の要素が存在する場合、私はリストの平均を取り、平均値に最も近い要素を使用する必要があります。

ご協力いただきますようお願い申し上げます。ありがとうございます。

Answer 1

私はあなたが欲しいものを、コメントで言ったようにletではない、それは関数合成です。

あなたの現在の中央値関数はこれです：

(define (median L) 
    (if (null? L) 
     (error "The list is empty") 
     (let loop ((L1 L) (L2 L)) 
     (cond ((null? (cdr L2)) (car L1)) 
       ((null? (cddr L2)) (list (car L1) (cadr L1))) 
       (else (loop (cdr L1) (cddr L2))))))) 

しかし、オスカー・ロペスが指摘したように、これは適切に中央値を計算しません。しかし、それは仕事のいくつかを行うので、それを保つ。名前をmedian-helperなどに変更します。

(define (median-helper L) 
    (if (null? L) 
     (error "The list is empty") 
     (let loop ((L1 L) (L2 L)) 
     (cond ((null? (cdr L2)) (car L1)) 
       ((null? (cddr L2)) (list (car L1) (cadr L1))) 
       (else (loop (cdr L1) (cddr L2))))))) 

次に、あなたが「本物」の中央値関数を定義する関数合成を使用することができます。

(define (median lst) 
    (median-helper (sort1 lst))) 

これは、奇数長リストの中間の要素を返し、偶数長のリストの中の二つの要素。これが望めば欲しい、偉大な。そうでない場合は、condの2番目のケースで平均を返して、median-helperを修正することができます。したがって、(list (car L1) (cadr L1))の代わりに、(avg (list (car L1) (cadr L1)))となります。

;; median-helper : (Listof Number) -> Number 
(define (median-helper L) 
    (if (null? L) 
     (error "The list is empty") 
     (let loop ((L1 L) (L2 L)) 
     (cond ((null? (cdr L2)) (car L1)) 
       ((null? (cddr L2)) (avg (list (car L1) (cadr L1)))) 
       (else (loop (cdr L1) (cddr L2))))))) 

;; median : (Listof Number) -> Number 
(define (median lst) 
    (median-helper (sort1 lst))) 

Answer 2

medianの定義を誤解していると思います。 （特に効率的ではない場合）非常に単純な実装は以下：

(define (my-sort L) 
    (sort L <)) 

(define (average x y) 
    (exact->inexact (/ (+ x y) 2))) 

(define (median L) 
    (if (null? L) 
     (error "The list is empty") 
     (let* ((n (length L)) 
      (sorted (my-sort L)) 
      (half (quotient n 2))) 
     (if (odd? n) 
      (list-ref sorted half) 
      (average (list-ref sorted half) 
        (list-ref sorted (sub1 half))))))) 

定義されるようにそれが動作します。

(median '()) 
=> The list is empty 
(median '(3 2 1 5 4)) 
=> 3 
(median '(6 4 3 1 2 5)) 
=> 3.5