如何正确计算Scheme中的成对差异？

Question

给定一个数字列表，例如 (1 3 6 10 0)，如何计算差异 (x_i - x_i-1 ），前提是 x_-1 = 0 ？

（本例中的结果应该是 (1 2 3 4 -10)）

我发现这个解决方案是正确的：

(define (pairwise-2 f init l)
  (first 
   (foldl
    (λ (x acc-data)
      (let ([result-list (first acc-data)]
            [prev-x (second acc-data)])
        (list 
         (append result-list (list(f x prev-x)))
         x))) 
    (list empty 0)
    l)))

(pairwise-2 - 0 '(1 3 6 10 0))
;; => (1 2 3 4 -10)

但是，我认为应该有更优雅但同样灵活的解决方案。 实在是太丑了。

我是函数式编程的新手，希望听到有关代码的任何建议。

谢谢。

Answer 1

map 接受多个参数。 所以我会做

(define (butlast l)
  (reverse (cdr (reverse l))))
(let ((l '(0 1 3 6 10)))
  (map - l (cons 0 (butlast l)))

如果你想把它包装在一个函数中，说

(define (pairwise-call f init l)
  (map f l (cons init (butlast l))))

这当然不是小计划者的方式，而是避免自己编写递归的方式。 选择您最喜欢的方式。

Answer 2

我已经很久没有做过计划了，但这对我来说是一个典型的口语型小问题。

我从一个基本定义开始（请忽略括号的错误位置 - 我没有方便的方案解释器：

(define pairwise-diff
    (lambda (list)
      (cond
       ((null? list) '())
       ((atom? list) list)
       (t (pairwise-helper 0 list)))))

这处理 null 和atom 的垃圾情况，然后将肉情况委托给助手：

(define pairwise-helper
    (lambda (n list)
       (cond
         ((null? list) '())
         (t
            (let ([one (car list)])
               (cons (- one n) (pairwise-helper one (cdr list))))
         ))))

您可以使用“if”重写它，但我天生就使用 cond。

这里有两种情况：空列表 - 这很简单，还有其他一切。
对于其他所有内容，我抓住列表的头部并将此差异限制到递归情况下。 我认为事情并没有变得更简单。

Answer 3

改进并适应 PLT 方案 plinth 的 代码，我认为近乎完美的解决方案是：

(define (pairwise-apply f l0 l)
  (if (empty? l)
      '()
      (let ([l1 (first l)])
        (cons (f l1 l0) (pairwise-apply f l1 (rest l))))))

Answer 4

Haskell 告诉我使用 zip ;)

(define (zip-with f xs ys)
  (cond ((or (null? xs) (null? ys)) null)
        (else (cons (f (car xs) (car ys))
                    (zip-with f (cdr xs) (cdr ys))))))
(define (pairwise-diff lst) (zip-with - (cdr lst) lst))

(pairwise-diff (list 1 3 6 10 0))
; gives (2 3 4 -10)

Answer 5

无论如何，一旦最短参数列表用完，映射就不会结束吗？

(define (pairwise-call fun init-element lst)
  (map fun lst (cons init-element lst)))

编辑：jleedev 告诉我，至少在一个方案实现中并非如此。 这有点烦人，因为没有 O(1) 操作来截断列表的末尾。

也许我们可以使用reduce：（

(define (pairwise-call fun init-element lst)
  (reverse (cdr (reduce (lambda (a b)
                          (append (list b (- b (car a))) (cdr a)))
                        (cons (list init-element) lst)))))

免责声明：快速破解，未经测试）

Answer 6

这是最简单的方法：

(define (solution ls)
  (let loop ((ls (cons 0 ls)))
    (let ((x (cadr ls)) (x_1 (car ls)))
      (if (null? (cddr ls)) (list (- x x_1))
          (cons (- x x_1) (loop (cdr ls)))))))

(display (equal? (solution '(1)) '(1))) (newline)
(display (equal? (solution '(1 5)) '(1 4))) (newline)
(display (equal? (solution '(1 3 6 10 0)) '(1 2 3 4 -10))) (newline)

写出每个示例的代码扩展，看看它是如何工作的。

如果您有兴趣开始使用 FP，请务必查看如何设计程序。 当然，它是为编程新手编写的，但其中包含大量优秀的 FP 习惯用法。

Answer 7

(define (f l res cur)
  (if (null? l)
    res
    (let ((next (car l)))
      (f (cdr l) (cons (- next cur) res) next))))

(define (do-work l)
  (reverse (f l '() 0)))

(do-work '(1 3 6 10 0))

==> (1 2 3 4 -10)