争夺功能如何工作？ （经验丰富的Schemer的第1章）

Question

根据这本书，这是函数定义的内容，

功能争夺的元组不超过其自身索引，并返回相同长度的元组。参数中的每个数字都被视为从其自身位置到元组早期的向后索引。每个位置的结果是通过根据此索引从当前位置向后计数来获得的。

这些是一些示例，

; 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

在这种情况下，使用非常最小的语言版本意味着代码足够详细，以至于理解算法并不容易。

解决这个问题的一种方法是用更丰富的语言编写程序，然后确定现在很明显的算法如何在最低版本中实现。让我们选择球拍作为丰富的语言。

球拍具有一个函数（和方案），称为list-ref：（list-ref li）返回i 的TH元素l，基于零。

它也有一个很好的“序列”概念，这些序列几乎是“您可以迭代的东西”和一堆构造，其名称以为 for 开始，以迭代序列。有两个功能使我们关心的序列：

• in-Naturals是自然数的无限序列，默认情况下是从0开始的，但是（在-naturals n）从n开始。
• in-list从列表中制作一个序列（列表实际上已经是一个序列，但是in-list使事情变得更清晰，并且谣言也更快）。

我们关心的迭代构造是/列表，它通过某些序列进行迭代，并将其从身体收集到列表中。

鉴于这些，那么算法几乎是微不足道的：我们想沿列表迭代，跟踪当前索引，然后进行适当的扣除以在列表中更进一步。唯一的非平凡位是处理零与一个基于索引的零。

(define (scramble l)
  (for/list ([index (in-naturals)]
             [element (in-list l)])
    (list-ref l (+ (- index element) 1))))

实际上，如果我们导致naturals从1

(define (scramble l)
  (for/list ([index (in-naturals 1)]
             (element (in-list l)))
    (list-ref l (- index element))))

计数，该算法非常清楚，您可以检查它在书中给出答案：

> (scramble '(1 1 1 3 4 2 1 1 9 2))
'(1 1 1 1 1 4 1 1 1 9)

现在仍然可以阐明书中代码如何实现相同的算法。那是一个贴心的，但是一旦您知道算法是什么，它应该很简单。

Answer 2

如果口头描述看起来模糊且难以遵循，我们可以尝试遵循代码本身，将其变成更为视觉的伪代码，

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*)
  , ... ]

因此，输入列表中的每个元素都用作索引中的索引中的索引中的相反前缀。列表，直到和包括该元素。换句话说，在计数 backwards 时，一个索引从元素到左，IE，to list的 start 。

因此，我们现在已经可视化了代码在做什么，并且还发现了其输入列表元素的要求。