I'm not familiar with the syntax of functional PLs - what does the first 'a' stand for in scan::a -> ((a,a) -> a) -> seq a -> seq a? Is it the initial/starting element? Would that be 0 in this example?

@fdxmw yes I believe the first a is a number that dictates the result of the first operation (in this case, the sum with in[0]). I think this is necessary because the function is defined on pairs of elements (the element at index i and the element at index i-1). When i is 0, i-1 is undefined, so we pass in an extra element (in this case 0) to handle that case.

What is the difference between performing a scan inclusive as shown above and a fold beginning at zero as shown in the other slide? Seems like they would give the same input but how does the implementation of each affect how the outputs are calculated?

From what I understand, a scan inclusive outputs a sequence of all the intermediate sums. The fold operator shown before only outputs a single sum.

scan == fold with 0 as the initial value?

I think scan and fold are different since fold returns a single value after the "merge" while scan returns a collection of values with each value corresponding to each element at each iteration of the binary operator. I think fold with 0 as the initial value more resembles a reduce operation.

Fold is just a Reduce with an initial value, returns 1 value. Scan returns another sequence where the operation depends on previous elements in the sequence, whereas Map returns a sequence where the operations are independently applied.

Doesn't exclusive scan loses the information about the last element? The assignments pretty much always use exclusive scan instead of inclusive scan. I wonder if there's a problem which can be solved via exclusive scan but not inclusive scan.

I believe that an inclusive_scan is just an exclusive_scan that's shifted to the left. So to turn an inclusive_scan to an exclusive_scan simply insert a 0 at the beginning and discard the final element whereas to go from an exclusive_scan to an inclusive_scan we need to discard the first element (always 0) and insert the sum of the final element in the original input (before it got scanned) and the previously-final element in our exclusive scan to the end. So it's actually easier to go from an inclusive-scan to an exclusive-scan since we don't need to retrieve any elements from our original input. I believe the only reason we used exclusive-scan in most assignments is because in most of them we're indexing into arrays/memory regions and those are always indexed starting at 0 (in C/C++ and most programming languages at least) so using exclusive-scan to get those starting indices is more intuitive than using inclusive-scan to get the ending indices.