方案中的可变数据返回对，其中右侧元素是匹配条件的最大后缀

Question

我有这个定义“排序左侧列表”，它是根据每对的左侧元素排序的对列表，左侧元素必须是非负整数，并且右组件可以是任何类型的值

我必须编写一个过程 mkjump ，它将非负整数的排序列表作为参数， sorted-lst = (x1 ... xn) 并返回左排序列表： sort left list = ((x1.y1)...(xn.yn)) 这样：yi 是 sort left list 的最大后缀， ((xj . yj)...(xn . yn)) 其中对于所有 xk，xk>(xi)^2。例如：

   >(define lst (list 2 3 4 15 16 17))
   >(mkjump lst)
   >lst
    ( (2 (15) (16) (17))
    (3 (15) (16) (17))
    (4 (17))
    (15)
    (16)
    (17) )

res 中的第 6 个元素是 (x6 . y6)，其中 x6=17 且 y6=null。 res 中的第三个元素是 (x3 . y3)， 其中x3=4，y3是包含(x6.y6)的列表，它是res的最大后缀，其中xk>(xi)^2 for all xk

怎么写呢？

Answer 1

我在麻省理工学院的计划中做到了这一点，希望它也适用于球拍。我假设您实际上不必使用突变，因为您的示例并不依赖于它。

(define (square x) (* x x))

(define (mkjump lst)
  (if (null? lst)
      '()
      (cons (cons (car lst) (wrapper (car lst) (cdr lst)))
        (mkjump (cdr lst)))))

(define (wrapper item lst)
  (modmap (lambda (x) 
         (if (< (square item) x)
             (list x)
             #f))
         lst))

(define (modmap proc lst)
  (cond ((null? lst) '())
        ((proc (car lst)) (cons (proc (car lst)) (modmap proc (cdr lst))))
        (else (modmap proc (cdr lst))))) 

Answer 2

如前所述，您不需要可变状态来完成您的工作。但是，如果您确实想使用它们，您可以轻松更改 Keen 的解决方案以获得您想要的。首先你必须以尾递归的方式翻译他的代码。你可以从mkjump开始

(define (mkjump lst) (reverse (mkjump-tr lst '())))

(define (mkjump-tr lst sol)
  (if (null? lst)
      sol
      (mkjump-tr (cdr lst) 
                 (cons (cons (car lst) (wrapper (car lst) (cdr lst)))
                       sol)) ))

，然后你可以改变modmap

(define (modmap proc lst) (reverse (modmap-tr proc lst '())))

(define (modmap-tr proc lst sol)
  (cond ((null? lst) sol)
        ((proc (car lst)) (modmap-tr proc 
                                     (cdr lst) 
                                     (cons (proc (car lst)) sol) ))
        (else (modmap-tr proc (cdr lst) sol)))) 

尾递归mkjump-tr将在迭代过程中被翻译。这是因为它可以被视为一个 while 循环。这使您能够使用 do 构造创建此循环。这样 mkjump-tr 可以写成

(define (mkjump-tr lst sol)
  (do ((lst lst (cdr lst))
       (sol sol (cons (cons (car lst) (wrapper (car lst) (cdr lst)))
                       sol)) )
    ((null? lst) sol)
    ))

modmap-tr 可以翻译为

(define (modmap-tr proc lst sol)
  (do ((lst lst (cdr lst))
       (sol sol (if (proc (car lst)) (cons (proc (car lst)) sol) sol)) )
    ((null? lst) sol)
    ))

但是由于我们没有递归形式，所以我们可以直接写这些 do< /code> 位于之前的函数 mkjump 和 modmap 中。所以我们

(define (mkjump lst) 
  (do ((lst lst (cdr lst))
       (sol '() (cons (cons (car lst) (wrapper (car lst) (cdr lst)))
                       sol)) )
    ((null? lst) (reverse sol))
    ))

(define (modmap proc lst) 
  (do ((lst lst (cdr lst))
       (sol '() (if (proc (car lst)) (cons (proc (car lst)) sol) sol)) )
    ((null? lst) (reverse sol))
    ))

可以看到一些细微的变化：reverse 在 sol 之前添加，并且 sol 在两种情况下都由空列表初始化。

最后，如果您确实想在某处看到一些set!，只需通过破坏do循环结构来添加它们即可。这是mkjump的解决方案，

(define (mkjump lst)
  (let ((elt 'undefined)
        (lst lst)
        (sol '()))
  (do () 
    ((null? lst) (reverse sol))
    (set! elt (car lst))
    (set! lst (cdr lst))
    (set! sol (cons (cons elt (wrapper elt lst)) sol))
    )))

我会让你改变modmap。最后这两个修改混淆了算法背后的想法。因此，以这种方式改变它们是一个坏主意，因为它们不会改进任何东西。然而，第一个修改可能是个好主意。所以我建议你保留第一次修改。

这是你所期望的吗？