Как удвоить список с помощью хвостовой рекурсии?

Question

(define (lst-double-helper lst acc)
  (if (empty? list)
      acc
      (lst-double-helper (rest lst) (cons (* (first lst) 2) acc))))

(define (lst-double lst)
  (lst-double-helper lst '()))

Я чувствую, что делаю это правильно.Но это дает мне ошибку

(lst-double '(1,2,3))
*: contract violation
  expected: number?
  given: ',2
  argument position: 1st
  other arguments...:

Почему ожидается, что второй аргумент будет числом?

Answer 1

Одним из таких способов является использование стиля прохождения продолжения.Здесь мы добавляем параметр с именем return, который эффективно кодирует поведение, напоминающее возврат, с помощью лямбды.double теперь принимает два аргумента: список удваивается, xs и продолжение результата, return -

(define (double xs return)
  (if (empty? xs)
      (return empty)
      (double (cdr xs)
              (lambda (result)
                (return (cons (* 2 (car xs))
                              result))))))

В качестве примера, результатdouble, примененный к списку '(1 2 3), отправляется на print

(double '(1 2 3) print)
;; '(2 4 6)
;; => #<void>

double, что соответствует конечному продолжению;в этом случае print оценивается как #<void>.Мы можем использовать функцию identity для эффективного вывода значения -

(double '(1 2 3) identity)
;; => '(2 4 6)

Racket позволяет легко указывать аргументы по умолчанию, поэтому мы можем изменить double, чтобы использовать identity в качестве продолжения по умолчанию

(define (double xs <b>(return identity))</b>
  ;; ...
  )

Этот стиль позволяет создавать удобные программы, которые работают одновременно в двух стилях вызова: стиль продолжения -

(double '(10 11 12) print)
;; '(20 22 24)
;; => #<void>

(double '(10 11 12) length)
;; => 3

(double '(10 11 12) car)
;; => 20

(double '(10 11 12) cdr)
;; => '(22 24)

... или в прямом стилес использованием identity продолжения по умолчанию

(print (double '(10 11 12)))
;; '(20 22 24)

(length (double '(10 11 12)))
;; => 3

(car (double '(10 11 12)))
;; => 20

(cdr (double '(10 11 12)))
;; => '(22 24)

Answer 2

Пара комментариев:

• Элементы списка разделяются пробелами, а не запятыми.Это ошибка, о которой сообщают.
• Базовый случай рекурсии должен ссылаться на параметр lst, а не на list.
• Ваше хвостово-рекурсивное решение переворачивает список, дополнительноreverse необходим в конце, чтобы восстановить первоначальный порядок

С учетом вышеуказанных изменений он работает как ожидалось:

(define (lst-double-helper lst acc)
  (if (empty? lst) ; parameter is called `lst`
      acc
      (lst-double-helper (rest lst) (cons (* (first lst) 2) acc))))

(define (lst-double lst)
  (reverse ; required to restore original order
   (lst-double-helper lst '())))

(lst-double '(1 2 3)) ; use spaces to separate elements
=> '(2 4 6) 

Имейте в виду, что хвост-рекурсивенРешение, которое пересекает входной список и cons его элементы для построения выходного списка, обязательно изменит порядок элементов в входном списке.Это нормально, и нормально делать reverse в конце.Возможные альтернативы, чтобы избежать реверсирования элементов в конце, - это изменить список входных данных в начале или написать нерегулярно-рекурсивное решение.

Answer 3

Для вложенных списков:

(define (atom? x)
  (and (not (null? x))
       (not (pair? x))))

(define (lst-double-helper lst acc)
  (cond ((empty? lst) acc)
        ((atom? (car lst)) (lst-double-helper (rest lst) (cons (* (first lst) 2) acc)))
        (else (lst-double-helper (rest lst) (cons (lst-double (first lst))
                                         acc) ))))

(define (lst-double lst)
  (reverse ; required to restore original order
   (lst-double-helper lst '())))

, но на самом деле сделать эту функцию рекурсивной немного бессмысленно, потому что, как упоминал @simmone, map сделает это

(define (list-doubler lst) 
  (map (lambda (x) (* 2 x)) lst))


(list-doubler '(1 2 3))
;; '(2 4 6)

Answer 4

использовать карту.

(карта (лямбда (a) (* a 2)) '(1 2 3))