函數式編程 - 使用摺疊執行掃描（前綴總和）

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論文）。

有沒有人有更優雅的掃描解決方案？

BTW我實現摺疊左和摺疊式右邊是：

(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

Imho掃描在fold方面表現非常好。

哈斯克爾例如：

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論文，您會注意到掃描由兩個階段組成：第一個產生摺疊結果作爲副產品。第二階段僅用於掃描（當然，這僅適用於並行實現;如果不依賴於scan，則順序實現fold更爲有效）。

Answer 3

恕我直言，達里奧使用反向因爲鍛鍊被騙了關於不折反折來表達。當然，這是表達掃描的一種可怕的方式，但這是一種將方形釘塞入圓孔的有趣練習。

這是在Haskell，我不知道口齒不清

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] 

當然

，使用德相同伎倆達里奧一個可以擺脫那個領先的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]