For clarification: scan, unlike fold, assumes the binary operator is associative?

Why might someone want to use an exclusive scan?

I think both fold and scan are associative but fold returns the final value only while scan returns the intermediate values as well because if fold is not associative we cannot break up the calculation like in the previous slide.

I'm a bit confused by the function notation with the "::". I thought I was following this syntax until this slide. What is the significance of re-using a in the input and output for f? Similarly, what exactly is the scan definition communicating? I get that it's acting on the associative binary op defined by f, but I don't get how there can be multiple "->"'s in the definition without additional parenthesis to group inputs/outputs.

In Haskell, :: is just the symbol that separates a function name from its signature.

Here, we have a function f that maps from (a, a) (pairs of a) to a. The type a is left abstract here, but you could see + as a function (int, int) -> int.

Now let's look at scan. We imagine there is some type seq a, which is read as "a sequence of a", just as [a] would be "a list of a". Then given an a, some function (a, a) -> a (like f), and a seq a, scan returns a seq a. You could imagine an implementation like

scan init f [] = [] scan init f x:xs = let cur = f (init, x) in cur : scan cur f xs

I'm abusing notation here by pretending that seq a is the same as [a], but in general, we match the arguments init f and the third one to the argument types to see that init is of type a, f is of type (a, a) -> a, and [] in the first line and x:xs in the second line is of type seq a. Finally, [] indicates the empty list and x:xs is the list beginning with x (of type a) followed by the sequence xs (of type seq a). Generally, : can be thought of as pretending an element to a list, which is how we use it in the right hand side of the second line.

The last thing to note—because it's weird if you haven't seen it before—is the use of what're called "copatterns". You'll notice that I defined scan here twice by splitting it up into copatterns. The idea of copatterns is you can pattern match on the arguments to a function and give different definitions on different match cases. This is very useful for recursive algorithms, such as scan here because it allows me to tell the function what to do in the event it is given an empty sequence ([]) or a non-empty sequence beginning with x (x:xs).

If this is really confusing, Learn You a Haskell for a Great Good is a great resource.

@ufxela I think scan_inclusive with the (+) operator is the same as fold with 0 as the argument

@sagoyal I don't think that's right. fold produces one element, while scan_inclusive or scan_exclusive both produce a sequence.