Сгладить список, используя только формы в "The Little Schemer" - PullRequest
Новая
       51

Сгладить список, используя только формы в "The Little Schemer"

3 голосов
/ 06 сентября 2011

Я прохожу через LIttle Schemer, чтобы изучить Scheme (как старый программист на C), и в качестве упражнения я попытался написать процедуру для выравнивания списка, используя только формы в The Little Schemer;Т.е. define, lambda, cond, car, cdr, and, or и т. Д., Но не append.Я думал, что это будет легко, но я не смог найти решение.Как я могу это сделать?

Ответы [ 3 ]

10 голосов
/ 06 сентября 2011

У меня есть версия, которая использует только операции «из первых принципов» и является эффективной (не требует более одного прохода через любой из списков, в отличие от решений на основе append).: -)

Это делается путем определения двух простых строительных блоков (fold и reverse), а затем определения flatten (и его помощника, reverse-flatten-into) поверх этих (и обратите внимание, как каждыйфункция длиной всего одну или две строки): 

;; Similar to SRFI 1's fold
(define (fold1 kons knil lst)
  (if (null? lst)
      knil
      (fold1 kons (kons (car lst) knil) (cdr lst))))

;; Same as R5RS's reverse
(define (reverse lst)
  (fold1 cons '() lst))

;; Helper function
(define (reverse-flatten-into x lst)
  (if (pair? x)
      (fold1 reverse-flatten-into lst x)
      (cons x lst)))

(define (flatten . lst)
  (reverse (reverse-flatten-into lst '())))

Используются только внешние функции: cons, car, cdr, null? и pair?.

Ключевое понимание этой функции заключается в том, что fold является очень мощной операцией и должна быть частью любого набора инструментов Schemer.И, как видно из кода выше, это так просто построить из первых принципов!

2 голосов
/ 06 сентября 2011

Вот попытка. Он избегает использования «против» и избегает добавления, потому что он отбрасывает только первую непару, к которой он может добраться, и сводит это к расплющению нового хвоста, который он построил. Иногда он переписывает список, а затем просто снова вызывает вызовы. Деф не самый эффективный способ.

Фиксированный код: 

(define (flatten x)
  (cond 
    ((null? x) x)
    ((and (pair? x) 
          (not (pair? (car x))))
     (cond 
       ((null? (car x)) (flatten (cdr x)))
       (else (cons (car x) (flatten (cdr x))))))
    ((and (pair? x)
          (pair? (car x)))
     (flatten (cons (caar x) 
                    (cons (cdar x) (cdr x)))))
    (else (cons x '()))))
2 голосов
/ 06 сентября 2011

Я не знаком с примитивами Little Schemer, поэтому вам, возможно, придется приправить это, чтобы удовлетворить.

Я не уверен, что это ответ, который вы хотите, но вы можете написать appendс использованием примитивов: 

(define (append l1 l2)
  (cond
    ((null? l1) l2)
    (else (cons (car l1) (append (cdr l1) l2)))))

В таком случае можно написать функцию flatten.

Не уверен, что это за пределами правил:)

...