Functional Programming - Implementing Scan (Prefix Sum) using Fold

Question

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

Prothalamium

Answer 1

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

Ukulele

Awesome, that's exactly what i was looking for. – Prothalamium

Answer 2

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

Faculty

You're correct that this is not "the way to do it", but it is an interesting exercise, which is why I'm doing it. I did read the CUDA papers, and I won't try to actually use this in a real system. It's just a curiosity. – Prothalamium

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]

Geniculate

my bad, i guess I should read the question before commenting, though I can't read lisp, it looks like the asker already had this solution but didn't like it? – Geniculate

Yea, you see, this is a great solution except for the (last xs) since that's very non-functional! I'm starting to wonder whether this is something that can easily be done. – Prothalamium