Back to search

University of Sheffield

On the Implementation of Purely Functional Data Structures for the Linearisation case of Dynamic Trees

Abstract

dc:description.abstract

Dynamic trees, originally described by Sleator and Tarjan, have been studied in detail for non persistent structures providing O(log n) time for update and lookup operations as shown in theory and practice by Werneck. However, there are two gaps in current theory. First, how the most common dynamic tree operations (link and cut) are computed over a purely functional data structure has not been studied in detail. Second, even in the imperative case, when checking whether two vertices u and v are connected (i.e. in the same component), it is taken for granted that the corresponding location indices (i.e. pointers, which are not allowed in purely functional programming) are known a priori and do not need to be computed, yet this is rarely the case in practice. In this thesis we address these omissions by formally introducing two new data structures, Full and Top, which we use to represent trees in a functionally efficient manner. Based on a primitive version of finger trees – the de facto sequence data structure for the purely lazy-evaluation programming language Haskell – they are augmented with collection (i.e. set-based) data structures in order to manage efficiently k-ary trees for the so-called linearisation case of the dynamic trees problem. Different implementations are discussed, and their performance is measured. Our results suggest that relative timings for our proposed structures perform sublinear time per operation once the forest is generated. Furthermore, Full and Top implementations show simplicity and preserve purity under a common interface.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Sheffield
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Saenz Carrasco, Juan Carlos
Advisors dc:contributor.advisor
  • Stannett, Mike
  • Struth, Georg

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Identifier
uk.bl.ethos.813863

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Saenz Carrasco, Juan Carlos. On the Implementation of Purely Functional Data Structures for the Linearisation case of Dynamic Trees. doctoral thesis, University of Sheffield, 2019.