merging sorted sequences generically in Python

Dave Long dave.long at bluewin.ch
Mon Dec 12 13:36:29 EST 2011


> Merging sorted sequences was the fundamental data processing  
> framework of the COBOL era, and again of the MapReduce era.

Just to point out some tangential connections:
* boolean operations can also be synthesized by merging in two or  
three dimensions, not just linearly. [NAT1990]
* conversely, a sorted sequence is the linear equivalent of a binary  
space partition, due to transitivity of ordering. [HP2006]

-Dave

[NAT1990]
Naylor, Amantides, & Thibault, "Merging BSP Trees Yield Polyhedral  
Set Operations", 1990
http://www.mcs.csueastbay.edu/~tebo/papers/siggraph90.pdf

[HP2006]
Hinze & Paterson, "Finger trees: a simple general-purpose data  
structure", 2006
4.7 Application: ordered sequences
http://www.cs.ox.ac.uk/ralf.hinze/publications/FingerTrees.pdf



More information about the Kragen-discuss mailing list