Как работает функция скремблирования? (Глава 1 Опытного интригана)

Question

Согласно книге, это определение функции,

Функция scramble принимает непустой кортеж, в котором ни один аргумент не больше его собственного индекса, и возвращает кортеж той же длины. Каждое число в аргументе рассматривается как обратный индекс от его собственной позиции до точки, предшествующей в кортеже. Результат в каждой позиции получается путем обратного отсчета от текущей позиции по этому индексу.

И это несколько примеров,

      ; Examples of scramble
(scramble '(1 1 1 3 4 2 1 1 9 2))       ; '(1 1 1 1 1 4 1 1 1 9)
(scramble '(1 2 3 4 5 6 7 8 9))         ; '(1 1 1 1 1 1 1 1 1)
(scramble '(1 2 3 1 2 3 4 1 8 2 10))    ; '(1 1 1 1 1 1 1 1 2 8 2)

Вот реализация,

      (define pick
  (λ (i lat)
    (cond
      ((eq? i 1) (car lat))
      (else (pick (sub1 i)
                  (cdr lat))))))

(define scramble-b
  (lambda (tup rev-pre)
    (cond
      ((null? tup) '())
      (else
       (cons (pick (car tup) (cons (car tup) rev-pre))
             (scramble-b (cdr tup)
                         (cons (car tup) rev-pre)))))))

(define scramble
  (lambda (tup)
    (scramble-b tup '())))

Answer 1

Если словесное описание выглядит расплывчатым и трудным для понимания, мы можем попробовать следовать самому коду, превращая его в более наглядный псевдокод по мере продвижения:

      pick i [x, ...ys] = 
  case i { 
     1 --> x ;
     pick (i-1) ys }
==>
  pick i xs = nth1 i xs
     (* 1 <= i <= |xs| *)

scramble xs = 
   scramble2 xs []

scramble2 xs revPre =
 case xs {
   [] --> [] ;
   [x, ...ys] -->
     [ pick x [x, ...revPre],
       ...scramble2 ys
              [x, ...revPre]] }

Таким образом,

      scramble [x,y,z,w, ...] 
 =
  [ nth1 x [x]       (*x=1..1*)
  , nth1 y [y,x]     (*y=1..2*)
  , nth1 z [z,y,x]   (*z=1..3*)
  , nth1 w [w,z,y,x] (*w=1..4*)
  , ... ]

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

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