Publication View

Functional Data Structures (1996)

Chris Okasaki

Abstract

this paper. Note that the cons operation supplied by this library is strict, not lazy. In fact, the only lazy operations in this library are ++ (infix append) and reverse. 2 FIFO Queues Stacks and queues are usually the first two data structures studied by beginning computer science students. The typical imperative implementation of (unbounded) stacks as linked lists translates very naturally to a functional setting. However, the typical imperative implementation of (unbounded) queues as linked lists does not because it uses destructive updates at the end of the list. Thus, queues are perhaps the simplest example of a data structure whose implementation in a functional setting is substantially different from its implementation in an imperative setting. For this reason, functional queues have been widely studied [11, 9, 3, 23, 24]. A minimal signature for queues appears in Figure 2. The three main operations are snoc (q, x), which adds an element x to the rear of queue q ; head (q),

Publication details

Download	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.6229
Source	http://www.cs.columbia.edu/~cdo/ssafp96.ps
Publisher	Cambridge University Press
Contributors	CiteSeerX
Repository	CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
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