Как написать обратную функцию в схеме?

Question

Мне нужно написать функцию схемы, которая выполняет следующие действия:

Определить функцию SCHEME с именем (rev p), которая принимает пару в качестве аргумента и оценивает другую пару с первым и вторым элементами в пара р в обратном порядке. Например,

( rev ( cons 1 2))
> (2 . 1)

Вот мой код:

(define (rev p)
  (cond ((null? p) '())
        (not (pair? (car p)) p)
        (else (append (rev (cdr p)) (list (rev (car p))))

Однако мой код возвращает (1 . 2), когда я проверяю его, когда он должен возвращать (2 . 1).

Answer 1

(define rev
  (lambda (l acc)
    (if (null? l)
        acc
        (rev (cdr l)(cons (car l) acc)))))

(rev '(1 2 3) '())

А вот, очевидно, запутанная версия, но идеи могут быть полезны.

(define rev
  (lambda (l k)
    (if (null? l)
        (k (lambda (x) x))
        (rev (cdr l)
             (lambda (k0)
               (k (lambda (r) (k0 (cons (car l) r)))))))))

((rev '(1 2 3) (lambda (x) x)) '())

-

Как предполагает Уилл, вот другой вариант, не хвост рекурсивный, следовательно, не полностью cps'd, это комбинация classi c recursion и cps.

(define rev
  (lambda (l k)
    (if (null? l)
        (k '())
        (rev (cdr l)
             (lambda (r)
               (cons (car l)
                     (k r)))))))

Answer 2

или выражается так же, как:

(define (rev p)
  (if (pair? p)
      (cons (cdr p) (car p))
      p))

Answer 3

Если это просто пара , которую вы хотите изменить, это довольно просто, вам даже не нужно делать рекурсию! И не забудьте использовать cons, а не append:

(define (rev p)
  (cond ((not (pair? p)) p)
        (else (cons (cdr p) (car p)))))

Например:

(rev '())
=> '()
(rev 5)
=> 5
(rev (cons 1 2))
=> '(2 . 1)