Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Data Structure
Function Representation
Functional Language
Functional Programming
Related Publications
(5)
Making data structures confluently persistent
AVLTrees for Localized Search
Making Data Structures Persistent
Optimal Purely Functional Priority Queues
Design and Analysis of a Data Structure for Representing Sorted Lists
Subscribe
Academic
Publications
Purely functional representations of catenable sorted lists
Purely functional representations of catenable sorted lists,10.1145/237814.237865,Haim Kaplanl,Robert Endre Tarjan
Edit
Purely functional representations of catenable sorted lists
(
Citations: 27
)
BibTex

RIS

RefWorks
Download
Haim Kaplanl
,
Robert Endre Tarjan
The power of purely
functional programming
in the construction of data structures has receivedmuch attention, not only because functional languages have many desirable properties,but because structures built purely functionally are automatically fully persistent: any andall versions of a structure can coexist indefinitely. Recent results illustrate the surprisingpower of pure functionality. One such result was the development of a representation ofdoubleended queues with catenation that...
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 202211, 1996
DOI:
10.1145/237814.237865
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
doi.acm.org
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(16)
...Our algorithm uses 23 finger trees [6], [
23
] to maintain the list of leaves in each subtree...
...These require no layout decision, and can be made into a singleton finger tree of size 1 in constant time [
23
]...
...Complexity: Kaplan and Tarjan [
23
] describe split and append (þþ) operations on 23 finger trees...
...The total complexity is bounded by the shared complexity of lines 5, 6, and 10. Since the sum of the logarithms is maximized when all the dis are equal [
23
], the complexity is thus Oð P i�j qj log diÞ¼Oðjqjlogð jpj jqj ÞÞ...
Balaji Venkatachalam
,
et al.
Untangling Tanglegrams: Comparing Trees by Their Drawings
...For further examples of structures that use the regular system, see [8,
9
]...
...This approach was used in [14] for constructing catenable deques, in [
9
] for constructing catenable finger search trees, and in [8] for constructing meldable priority queues...
Amr Elmasry
,
et al.
StrictlyRegular Number System and Data Structures
...For each internal node, we not only decide the optimal order for its children, we also construct a 23 finger tree , an ordered search tree with fast split and append operations [
17
]...
...These require no layout decision, and can be made into a singleton finger tree of size 1 in constant time [
17
]...
...Complexity Kaplan and Tarjan [
17
] describe split and append (+ +) operations on 23 finger trees...
...The total complexity is bounded by the shared complexity of lines 6, 7 and 11. Since the sum of the logarithms is maximized when all the dis are equal [
17
], the complexity is thus O �P...
Balaji Venkatachalam
,
et al.
Untangling Tanglegrams: Comparing Trees by Their Drawings
...
Kaplan and Tarjan (1996)
dened two functional data structures with the same time bounds as here, except that their bounds are worst case, and do not require laziness...
Ralf Hinze
,
et al.
Finger trees: a simple generalpurpose data structure
...Since the seminal paper of Driscoll et al. [14], there has been considerable development of persistent data structures [21, 22, 23,
24
]...
Sung Eun Bae
,
et al.
Improved Algorithms for the KMaximum Subarray Problem
References
(36)
Design and Analysis of a Data Structure for Representing Sorted Lists
(
Citations: 88
)
Mark R. Brown
,
Robert Endre Tarjan
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 9, no. 3, pp. 594614, 1980
The theory and practice of firstclass prompts
(
Citations: 142
)
Matthias Felleisen
Conference:
ACM SIGPLANSIGACT Symposium on Principles of Programming Languages  POPL
, pp. 180190, 1988
An optimal RAM implementation of catenable min doubleended queues
(
Citations: 12
)
S. Rao Kosaraju
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 195203, 1994
Worstcase priority queues
(
Citations: 5
)
G. S. Brodal
Published in 1996.
Fully persistent lists with catenation
(
Citations: 25
)
James R. Driscoll
,
Daniel Dominic Sleator
,
Robert Endre Tarjan
Journal:
Journal of The ACM  JACM
, vol. 41, no. 5, pp. 943959, 1994
Sort by:
Citations
(27)
Untangling Tanglegrams: Comparing Trees by Their Drawings
(
Citations: 2
)
Balaji Venkatachalam
,
Jim Apple
,
Katherine St. John
,
Daniel Gusfield
Journal:
IEEE/ACM Transactions on Computational Biology and Bioinformatics  TCBB
, vol. 7, no. 4, pp. 588597, 2010
StrictlyRegular Number System and Data Structures
Amr Elmasry
,
Claus Jensen
,
Jyrki Katajainen
Conference:
Scandinavian Workshop on Algorithm Theory  SWAT
, pp. 2637, 2010
Untangling Tanglegrams: Comparing Trees by Their Drawings
(
Citations: 6
)
Balaji Venkatachalam
,
Jim Apple
,
Katherine St. John
,
Dan Gusfield
Conference:
International Symposium on Bioinformatics Research and Applications  ISBRA
, pp. 8899, 2009
Finger trees: a simple generalpurpose data structure
(
Citations: 20
)
Ralf Hinze
,
Ross Paterson
Journal:
Journal of Functional Programming  JFP
, vol. 16, no. 2, pp. 197217, 2006
Improved Algorithms for the KMaximum Subarray Problem
(
Citations: 7
)
Sung Eun Bae
,
Tadao Takaoka
Journal:
The Computer Journal  CJ
, vol. 49, no. 3, pp. 358374, 2006