segmented exclusive scan

[melsman]

We need such a beast...

[athas]

What should the type be? In particular, what should be the size of the resulting array?

[melsman]

The type of segmented_excl_scan:

val segmented_excl_scan [n] 't : (t -> t -> t) -> t -> [n]bool -> [n]t -> [n]t 

This type is the same as the type for segmented_scan. The semantics, however, is different:

segmented_excl_scan (+) 0 [true,false,false,true,false,false] [1,2,3,4,5,6]  
--> [0,1,3,0,4,9]

Do we have an excl_scan somewhere in the libraries?

[melsman]

Here is an implementation:

let segmented_excl_scan [n] 't (op: t -> t -> t) (ne:t) (flags:[n]bool) (data:[n]t) : [n]t =
  let data = map (\i -> if i == 0 || flags[i] then ne
                        else data[i-1]) (iota n)
  in segmented_scan op ne flags data