Publication View

Purely Functional Data Structures (1998)

Chris Okasaki

Abstract

When a C programmer needs an efficient data structure for a particular problem, he or she can often simply look one up in any of a number of good textbooks or handbooks. Unfortunately, programmers in functional languages such as Standard ML or Haskell do not have this luxury. Although some data structures designed for imperative languages such as C can be quite easily adapted to a functional setting, most cannot, usually because they depend in crucial ways on assignments, which are disallowed, or at least discouraged, in functional languages. To address this imbalance, we describe several techniques for designing functional data structures, and numerous original data structures based on these techniques, including multiple variations of lists, queues, double-ended queues, and heaps, many supporting more exotic features such as random access or efficient catenation. In addition, we expose the fundamental role of lazy evaluation in amortized functional data structures. Traditional methods of amortization break down when old versions of a data structure, not just the most recent, are available for further

Publication details

Download	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.3080
Source	http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
Publisher	Cambridge University Press
Contributors	CiteSeerX
Repository	CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
Keywords	functional programming, data structures, lazy evaluation, amortization For Maria
Type	text
Language	English
Relation	10.1.1.35.3570, 10.1.1.48.5674, 10.1.1.34.5353, 10.1.1.33.4591, 10.1.1.31.3551, 10.1.1.71.463, 10.1.1.14.7591, 10.1.1.25.6766, 10.1.1.37.4284, 10.1.1.110.7706, 10.1.1.30.4768, 10.1.1.72.1042, 10.1.1.42.1517, 10.1.1.46.223, 10.1.1.15.5130, 10.1.1.46.2207, 10.1.1.108.6851, 10.1.1.86.7239, 10.1.1.37.5452, 10.1.1.83.3189, 10.1.1.37.9152, 10.1.1.40.4117, 10.1.1.13.3451, 10.1.1.35.9427, 10.1.1.17.297, 10.1.1.46.1458, 10.1.1.12.3176, 10.1.1.2.6982, 10.1.1.35.8482, 10.1.1.74.8712, 10.1.1.9.8749, 10.1.1.134.6504, 10.1.1.68.6949, 10.1.1.17.9108, 10.1.1.2.6890, 10.1.1.18.1149, 10.1.1.21.2911, 10.1.1.46.571, 10.1.1.22.7159, 10.1.1.23.6717, 10.1.1.46.3691, 10.1.1.12.457, 10.1.1.29.6341, 10.1.1.69.1351, 10.1.1.37.5440, 10.1.1.28.9377, 10.1.1.26.155, 10.1.1.67.3989, 10.1.1.85.1317, 10.1.1.127.1667, 10.1.1.16.8985, 10.1.1.6.5373, 10.1.1.132.9862, 10.1.1.35.9196, 10.1.1.24.7575, 10.1.1.106.3989, 10.1.1.74.3718, 10.1.1.84.3347, 10.1.1.89.245, 10.1.1.95.451, 10.1.1.120.8394, 10.1.1.10.3479, 10.1.1.101.7118, 10.1.1.102.1901, 10.1.1.102.6641, 10.1.1.103.9637, 10.1.1.106.2946, 10.1.1.106.557, 10.1.1.106.8736, 10.1.1.13.1892, 10.1.1.2.8571, 10.1.1.25.9743, 10.1.1.35.9761, 10.1.1.39.5334, 10.1.1.44.4874, 10.1.1.61.3043, 10.1.1.108.1230, 10.1.1.62.9990, 10.1.1.66.2327, 10.1.1.66.9665, 10.1.1.69.4934, 10.1.1.70.1493, 10.1.1.70.1894, 10.1.1.70.6836, 10.1.1.70.9434, 10.1.1.72.1314, 10.1.1.72.4506, 10.1.1.73.2770, 10.1.1.76.2799, 10.1.1.77.9891, 10.1.1.78.9412, 10.1.1.85.6141, 10.1.1.87.5415, 10.1.1.87.613, 10.1.1.87.6620, 10.1.1.88.384, 10.1.1.90.1052, 10.1.1.90.6125, 10.1.1.95.3472, 10.1.1.95.4869, 10.1.1.95.6046, 10.1.1.96.2612, 10.1.1.97.3316, 10.1.1.97.5228, 10.1.1.97.5430, 10.1.1.97.9190, 10.1.1.68.6565, 10.1.1.98.6893, 10.1.1.110.66, 10.1.1.110.5578, 10.1.1.111.9498, 10.1.1.114.4484, 10.1.1.115.4096, 10.1.1.115.9718, 10.1.1.116.442, 10.1.1.116.4541, 10.1.1.116.5295, 10.1.1.117.4820, 10.1.1.117.8424, 10.1.1.117.9231, 10.1.1.118.6764, 10.1.1.1.6348, 10.1.1.119.1154, 10.1.1.119.5374, 10.1.1.120.2551, 10.1.1.120.6554, 10.1.1.121.573, 10.1.1.122.2786, 10.1.1.124.180, 10.1.1.125.4303, 10.1.1.125.4343, 10.1.1.127.2058, 10.1.1.128.2669, 10.1.1.130.216, 10.1.1.130.4356, 10.1.1.132.8223, 10.1.1.135.7628, 10.1.1.137.1114, 10.1.1.137.1411, 10.1.1.48.347, 10.1.1.52.566, 10.1.1.45.6532, 10.1.1.41.3407, 10.1.1.42.7414, 10.1.1.34.4704, 10.1.1.36.8323, 10.1.1.36.9165, 10.1.1.22.1322, 10.1.1.24.8145, 10.1.1.57.8039, 10.1.1.10.5608, 10.1.1.3.8044, 10.1.1.1.7953, 10.1.1.59.4852, 10.1.1.59.6394, 10.1.1.140.2512