我一直在自学函数式编程,目前正在使用折叠编写不同的高阶函数。我陷入了执行扫描(也称为前缀和)的困境。我使用折叠的地图实现如下所示:
(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)))))
恕我直言,扫描可以很好地用
fold
来表达。
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)))))
我不会这样做。
fold
实际上可以用scan
(扫描列表的最后一个元素)来实现。但scan
和fold
实际上是正交运算。如果您阅读过 CUDA 论文,您会注意到扫描由两个阶段组成:第一个阶段产生折叠结果作为副产品。第二阶段仅用于扫描(当然,这只适用于并行实现;如果完全不依赖于fold
,scan
的顺序实现会更高效)。
恕我直言,达里奥(Dario)通过使用反向进行作弊,因为练习是用折叠而不是反向折叠来表达的。当然,这是一种可怕的表达扫描的方式,但它是将方钉塞入圆孔的有趣练习。
这是用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]