Functional Data Structures:Difficulties and Further Reading

By -

Difficulties

As this chapter has shown, many data structures work quite nicely in a functional setting. However, some do not. We close with a description of several warning signs to watch for.

• Random access: All of the data structures described in this chapter have been pointer-based. Unfortunately, data structures that depend on arrays—such as hash tables—are more difficult to handle. No entirely satisfactory approach is known for making arrays persistent. The best known approach from a theoretical point of view is that of Dietz [6], in which array accesses run in O(log log n) expected amortized time. However, his approach is quite complicated and difficult to implement. Competing approaches, such as [1, 4, 27], degrade to logarithmic (or worse!) time per access in common cases.

• Cycles : Not all pointer-based data structures are suitable for implementation in a functional setting. The most common problem is the presence of cycles, such as those found in doubly-linked lists or in binary search trees with parent pointers.

Path copying requires copying all paths from the root to the site of the update.

In the presence of cycles, this frequently means copying the entire data structure.

• Multiple entry points: Even without cycles, a pointer-based data structure can run into difficulties if it has multiple entry points. For example, consider a pointer based implementation of the union-find data structure [33]. All the pointers go from children to parents, so there are no cycles (except sometimes trivial ones at the roots). However, it is common for every node of the union-find data structure to be a potential entry point, rather than just the root(s). Path copying requires copying all paths from any entry point to the site of the update. With multiple entry points, this again frequently degrades into copying the entire data structure.

• Unpredictable access patterns : Section 40.4 described how to use lazy evaluation to make an amortized data structure persistent. Although this works for many amortized data structures, such as skew heaps [32], it does not work for all amortized data structures. In particular, data structures with highly unpredictable access patterns, such as splay trees [31] (see Chapter 12), are difficult to make persistent in this fashion.

Further Reading

The most complete general reference on functional data structures is Okasaki [24]. For more information on specific data structures, consult the following sources:

• queues and deques [5, 10, 11, 21]

• priority queues and priority search queues [3, 8]

• random-access lists and flexible arrays [9, 12, 13, 16, 20, 23]

• catenable lists and deques [14, 19, 22]

Comments

Post a Comment

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

By -
Introduction Important advances in programming languages have occurred since the early days of assembly languages and op codes, and modern programming languages have significantly simplified the task of writing computer programs. Unfortunately, tools for un d e rstanding programs have not achieved the accompanying levels of improvement. Software developers still face difficulties in understanding, analyzing, debugging, and improving code. As an example of the difficulties still evident, consider a developer who has just implemented a new algorithm and is now ready to examine the program’s behavior. After issuing a command to begin program execution, the developer examines output data and/or inter- active behavior, attempting to ascertain if the program functioned correctly, and if not, the reasons for the program’s failure. This task can be laborious and usually requires the use of a debugger or perhaps even the addition of explicit checking code, usually through output statements. Furt
Read more

Collision Detection:Penetration Depth Computation

By -
Image
Penetration Depth Computation In this section, we give a brief overview of penetration depth (PD) computation algorithms between convex polytopes and general polyhedral models. The PD of two inter-penetrating objects A and B is defined as the minimum translation distance that one object undergoes to make the interiors of A and B disjoint. It can be also defined in terms of the TCSO. When two objects are overlapping, the origin of the Minkowski sum of A and − B is contained inside the TCSO. The penetration depth corresponds to the minimum distance from the origin to the surface of TCSO [18]. PD computation is often used in motion planning [37], contact resolution for dynamic simulation [38, 39] and force computation in haptic rendering [40]. For example, computation of dynamic response in penalty-based methods often needs to perform PD queries for imposing the non-penetration constraint for rigid body simulation. In addition, many applications, such as motion planning and dynamic simula
Read more

Concurrent Data Structures:Linked Lists

By -
Linked Lists Consider implementations of concurrent search structures supporting insert, delete, and search operations. If these operations deal only with a key value, then the resulting data structure is a se t ; if a data value is associated with each key, we have a dic tionary [24]. These are closely related data structures, and a concurrent set implementation can often be adapted to implement a dictionary. In the next three sections, we concentrate on implementing sets using different structures: linked lists, hash tables, and trees. Suppose we use a linked list to implement a set. Apart from globally locking the linked list to prevent concurrent manipulation, the most popular approach to concurrent lock- based linked lists is ha nd-over-hand locking (sometimes called l o c k coupling ) [14, 89]. In this approach, each node has an associated lock. A thread traversing the linked list releases a node’s lock only after acquiring the lock of the next node in the list, thus preventin
Read more