Эффективный метод репликации функции длины

Question

Я воспроизвожу функцию длины ракетки, используя только машину & cdr, чтобы сравнить длину двух списков и вернуть более короткую из двух.

Функция длины просто положить является:

(define length 
(lambda (list) 
    (if (null? list) 
     0 
     (+ 1 (length (cdr list)))))) 

и при использовании в сравнении двух списков

(define short 
    (lambda (list1 list2) 
    (if (<= (length list1) (length list2)) 
     list1 
     list2))) 

> (short '(a b c) '(1 2 3 4 5 6 7)) 

вернет «(а б).

Однако этот метод неэффективен, особенно когда один список намного длиннее другого, так как он будет перебирать оба списка перед возвращением короче.

У меня более эффективный метод ниже. Однако мне было интересно, был ли более эффективный/альтернативный метод получения более короткой длины, не проверяя конца обоих списков. Возможно, рекурсивно просматривая списки одновременно с car/cdr, пока более короткий список не достигнет своего конца.

(define shorter? 
    (lambda (list1 list2) 
    (and (not (null? list2)) 
     (or (null? list1) 
      (shorter? (cdr list1) (cdr list2)))))) 

(define shorter 
    (lambda (list1 list2) 
    (if (shorter? list2 list1) 
     list2 
     list1))) 

Answer 1

Вашего shorter? процедура уже как можно более эффективная - как and и or специальных форм короткого замыкание и остановится, когда значение любого из оцененных выражений true (для or специальной формы) или false (для and особый вид). Поэтому, как только один из списков достигнет null, рекурсия прекращается. Ваша shorter? реализация эквивалентна, а так же эффективно, как это:

(define shorter? 
    (lambda (list1 list2) 
    (cond ((null? list2) #f) 
      ((null? list1) #t) 
      (else (shorter? (cdr list1) (cdr list2)))))) 

Если вы хотите получить более компактное решение, которое вы можете поставить обе процедуры внутри одной процедуры, с использованием имени let (как показано в другой ответ) или внутренняя вспомогательная процедура, оба эквивалентны. Я продемонстрирую более поздний подход:

(define (shorter lst1 lst2) 
    (define (shorter-list list1 list2) 
    (cond ((null? list2) lst2) 
      ((null? list1) lst1) 
      (else (shorter-list (cdr list1) (cdr list2))))) 
    (shorter-list lst1 lst2)) 

Answer 2

Я рекомендую начинать так:

(define (shorter list-1 list-2) (shorter-loop list-1 list-2 list-1 list-2)) 

затем

(define (shorter-loop list-1 list-2 result-1 result-2) 
    ;; 
) 

где вспомогательная функция короче петли рекурсивно вниз список-1 и список-2 одновременно. Если list-1 становится null, он возвращает результат-1, если list-2 возвращает null, он возвращает результат-2.

Answer 3

Метод «named let» обеспечивает легко поддающийся подшивку код. Комментарии предоставить объяснение:

(define (shorter l1 l2) 
    (let loop ((al l2)   ; start with both full lists 
      (bl l2)) 
    (cond 
     [(empty? al) l1]  ; if al finishes, return l1 and end; 
     [(empty? bl) l2]  ; if bl finishes, return l2 and end; 
     [else 
     (loop (cdr al) (cdr bl))] ; else loop again with cdr of lists; 
    ))) 

Эта функция заканчивается, когда Шорер список заканчивается и не будет понапрасну продолжаться до конца длинного списка.