Functional Programming - Implementing Scan (Prefix Sum) using Fold

Question

Hi guys!

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)))))

Answer 1

I wouldn’t do this. fold can actually be implemented in terms of scan (last element of the scanned list). But scan and fold are in fact orthogonal operations. If you’ve read the CUDA papers you’ll notice that a scan consists of two phases: the first yields the fold result as a by-product. The second phase is only used for the scan (of course, this only counts for parallel implementations; a sequential implementation of fold is more efficient if it doesn’t rely on scan at all).

Answer 2

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)))))

Answer 3

imho Dario cheated by using reverse since the exercise was about expressing in terms of fold not a reverse fold. This, of course, is a horrible way to express scan but it is a fun exercise of jamming a square peg into a round hole.

Here it is in haskell, I don't know 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]

of course, using teh same trick as Dario one can get rid of that leading 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]