DocumentCode :
3398602
Title :
Amortization, lazy evaluation, and persistence: lists with catenation via lazy linking
Author :
Okasaki, Chris
Author_Institution :
Sch. of Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA
fYear :
1995
fDate :
23-25 Oct 1995
Firstpage :
646
Lastpage :
654
Abstract :
Amortization has been underutilized in the design of persistent data structures, largely because traditional accounting schemes break down in a persistent setting. Such schemes depend on saving “credits” for future use, but a persistent data structure may have multiple “futures”, each competing for the same credits. We describe how lazy evaluation can often remedy this problem, yielding persistent data structures with good amortized efficiency. In fact, such data structures can be implemented purely functionally in any functional language supporting lazy evaluation. As can example of this technique, we present a purely functional (and therefore persistent) implementation of lists that simultaneously support catenation and all other usual list primitives in constant amortized time. This data structure is much simpler than the only existing data structure with comparable bounds, the recently discovered catenable lists of Kaplan and Tarjan, which support all operations in constant worst-case time
Keywords :
data structures; list processing; amortization; catenation; lazy evaluation; lazy linking; persistence; persistent data structures; Computer science; Contracts; Costs; Data analysis; Data structures; Delay effects; Electrostatic discharge; Functional programming; History; Joining processes;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on
Conference_Location :
Milwaukee, WI
ISSN :
0272-5428
Print_ISBN :
0-8186-7183-1
Type :
conf
DOI :
10.1109/SFCS.1995.492666
Filename :
492666
Link To Document :
بازگشت