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

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 对于所有xk

怎么写？

Answer 1

如前所述，您不需要可变状态来完成您的工作。但是，如果您确实想使用它们，您可以轻松更改 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写在前面的函数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。最后这两个修改混淆了算法背后的想法。因此，以这种方式改变它们是一个坏主意，因为它们不会改进任何东西。然而，第一个修改可能是个好主意。所以我建议你保留第一次修改。

这是你所期望的吗？