功能编程 - 使用折叠执行扫描（前缀和） [英] Functional Programming - Implementing Scan (Prefix Sum) using Fold

问题描述

我一直在自学函数式编程，目前我正在使用折叠编写不同的高阶函数。我卡住实施扫描（也称为前缀总和）。我使用fold的地图实现如下所示：

 （define（map op sequence）
（fold-right（lambda xl）（cons（op x）l））nil sequence））
  

例如：

 （define（scan sequence）
（fold-left（lambda（xy）（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初始序列）
（define（iter result rest）
（if（null？休息）
结果
（iter（op result（car rest））（cdr rest））））
（iter初始序列））
 
（define（fold （如果（空？序列）
初始
（op（汽车序列）（右 - 右初始（cdr序列）））））
  




解决方案 Imho扫描在

Haskell示例：

  scan func list = reverse $ foldl（\le->（func e（head l））：l）[head lis t]（尾单）
  

应该翻译成类似这样的内容

 （define scan 
（lambda（func seq）
（reverse 
（fold-left 
（lambda（le ）（cons（func e（car l））l））
（list seq））
（cdr seq）））））
  pre> 
I've been teaching myself functional programming, and I'm currently writing different higher order functions using folds. I'm stuck implementing scan (also known as prefix sum). My map implementation using fold looks like:
(define (map op sequence)
  (fold-right (lambda (x l) (cons (op x) l)) nil sequence))
And my shot at scan looks like:
(define (scan sequence)
  (fold-left (lambda (x y) (append x (list (+ y (car (reverse x)))))) (list 0) sequence))
My observation being that the "x" is the resulting array so far, and "y" is the next element in the incoming list. This produces:
(scan (list 1 4 8 3 7 9)) -> (0 1 5 13 16 23 32)
But this looks pretty ugly, with the reversing of the resulting list going on inside the lambda. I'd much prefer to not do global operations on the resulting list, since my next attempt is to try and parallelize much of this (that's a different story, I'm looking at several CUDA papers).

Does anyone have a more elegant solution for scan?

BTW my implementation of fold-left and fold-right is:
(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)))))

解决方案
Imho scan is very well expressible in terms of fold.

Haskell example:
scan func list = reverse $ foldl (\l e -> (func e (head l)) : l) [head list] (tail list)
Should translate into something like this
(define scan
  (lambda (func seq)
    (reverse 
      (fold-left 
       (lambda (l e) (cons (func e (car l)) l))
       (list (car seq))
       (cdr seq)))))


                        
这篇关于功能编程 - 使用折叠执行扫描（前缀和）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！