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:
“Universal empire is the prerogative of a writer. His concerns are with all mankind, and though he cannot command their obedience, he can assign them their duty. The Republic of Letters is more ancient than monarchy, and of far higher character in the world than the vassal court of Britain.”
—Thomas Paine (1737–1809)
“When we walk the streets at night in safety, it does not strike us that this might be otherwise. This habit of feeling safe has become second nature, and we do not reflect on just how this is due solely to the working of special institutions. Commonplace thinking often has the impression that force holds the state together, but in fact its only bond is the fundamental sense of order which everybody possesses.”
—Georg Wilhelm Friedrich Hegel (1770–1831)
“Every boy was supposed to come into the world equipped with a father whose prime function was to be our father and show us how to be men. He can escape us, but we can never escape him. Present or absent, dead or alive, real or imagined, our father is the main man in our masculinity.”
—Frank Pittman (20th century)