Scan Higher Order Function
In functional programming terms, the prefix sum may be generalized to any binary operation (not just the addition operation); the higher order function resulting from this generalization is called a scan, and it is closely related to the fold operation. Both the scan and the fold operations apply the given binary operation to the same sequence of values, but differ in that the scan returns the whole sequence of results from the binary operation, whereas the fold returns only the final result. For instance, the sequence of factorial numbers may be generated by a scan of the natural numbers using multiplication instead of addition:
-
input numbers 1 2 3 4 5 6 ... prefix products 1 2 6 24 120 720 ...
In Haskell, there are two variants of scan, called scanl and scanl1, differing slightly in their argument signature, and the prefix sum operation may be written scanl1 (+). The corresponding suffix operations are also available as scanr and scanr1. The procedural Message Passing Interface libraries provide an operation MPI_Scan for computing a scan operation between networked processing units. The C++ language has a standard library function partial_sum; despite its name, it takes a binary operation as one of its arguments, and performs a scan with that operation.
Read more about this topic: Prefix Sum
Famous quotes containing the words higher, order and/or function:
“For my part, I have no hesitation in saying that although the American woman never leaves her domestic sphere and is in some respects very dependent within it, nowhere does she enjoy a higher station . . . if anyone asks me what I think the chief cause of the extraordinary prosperity and growing power of this nation, I should answer that it is due to the superiority of their woman.”
—Alexis de Tocqueville (1805–1859)
“Children need people in order to become human.... It is primarily through observing, playing, and working with others older and younger than himself that a child discovers both what he can do and who he can become—that he develops both his ability and his identity.... Hence to relegate children to a world of their own is to deprive them of their humanity, and ourselves as well.”
—Urie Bronfenbrenner (b. 1917)
“Advocating the mere tolerance of difference between women is the grossest reformism. It is a total denial of the creative function of difference in our lives. Difference must be not merely tolerated, but seen as a fund of necessary polarities between which our creativity can spark like a dialectic.”
—Audre Lorde (1934–1992)