函数式编程-使用Fold实现扫描（前缀和）

Question

我一直在自学函数式编程，目前正在使用折叠编写不同的高阶函数。我陷入了执行扫描（也称为前缀和）的困境。我使用折叠的地图实现如下所示：

(define (map op sequence)
  (fold-right (lambda (x l) (cons (op x) l))
              nil
              sequence))

我的扫描镜头如下所示：

(define (scan sequence)
  (fold-left (lambda (x y)
               (append x (list (+ y (car (reverse x))))))
             (list 0)
             sequence))

我的观察是“x”是到目前为止的结果数组，“y”是传入列表中的下一个元素。这会产生：

(scan (list 1 4 8 3 7 9)) -> (0 1 5 13 16 23 32)

但这看起来相当难看，结果列表的反转在 lambda 内部进行。我更不想对结果列表进行全局操作，因为我的下一次尝试是尝试并行化其中的大部分内容（这是一个不同的故事，我正在查看几篇 CUDA 论文）。

有人有更优雅的扫描解决方案吗？

顺便说一句，我的左折叠和右折叠的实现是：

(define (fold-left op initial sequence)
 (define (iter result rest)
  (if (null? rest)
   result
   (iter (op result (car rest)) (cdr rest))))
 (iter initial sequence))

(define (fold-right op initial sequence)
 (if (null? sequence)
  initial
  (op (car sequence) (fold-right op initial (cdr sequence)))))

Answer 1

恕我直言，扫描可以很好地用折叠来表达。

Haskell 示例：

scan func list = reverse $ foldl (\l e -> (func e (head l)) : l) [head list] (tail list)

应该翻译成这样

(define scan
  (lambda (func seq)
    (reverse 
      (fold-left 
       (lambda (l e) (cons (func e (car l)) l))
       (list (car seq))
       (cdr seq)))))

Answer 2

我不会这样做。 fold 实际上可以通过 scan （扫描列表的最后一个元素）来实现。但scan和fold实际上是正交操作。如果您读过 CUDA 论文，您会注意到扫描由两个阶段组成：第一个阶段产生折叠结果作为副产品。第二阶段仅用于扫描（当然，这仅适用于并行实现；如果不依赖于扫描，则fold的顺序实现会更有效）根本没有）。

Answer 3

恕我直言，达里奥通过使用反向进行作弊，因为练习是用折叠而不是反向折叠来表达的。当然，这是一种可怕的表达扫描的方式，但却是将方钉塞入圆孔的有趣练习。

这是在 haskell 中，当然我不懂 lisp

let scan f list = foldl (\ xs next -> xs++[f (last xs) next]) [0] list
scan (+) [1, 4, 8, 3, 7, 9]
[0,1,5,13,16,23,32]

，使用与 Dario 相同的技巧可以摆脱前导 0：

let scan f list = foldl (\ xs next -> xs++[f (last xs) next]) [head list] (tail list)
scan (+) [1, 4, 8, 3, 7, 9]
[1,5,13,16,23,32]