Scheme - Как найти медиану, используя пользовательские сортировки и средние функции?

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

Это возвращает средний элемент для списков нечетной длины, а среднего-два элемента даже списки длины , Если это так хочется, отлично. Если нет, то вы можете исправить median-helper, вернув среднее значение во втором случае cond. Итак, вместо (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