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

Question

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

Answer 1

У меня есть версия, которая использует только операции "из первых принципов" и является эффективной (не требует более одного прохода через любой из списков, в отличие от 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. И, как видно из кода выше, это так просто построить из первых принципов!

Answer 2

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

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

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

Answer 3

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

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

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

flatten Функция может быть написана в терминах этого.

Не уверен, если это вне правил или нет:)