Talk:Persistent data structure
I think this article needs to be merged from or to Purely functional. Persistent data structure is a better name for the page (functional is an adjective which therefore violates Wikipedia naming conventions). On the other hand, purely functional has some nice diagrams which I drew to explain the concept :-) What does everyone think? Richard W.M. Jones 18:52, 17 January 2006 (UTC)
I've never seen "persistent data structure" used in the way this article describes. It may be used that way in some obscure book or two, but in my experience, a persistent data structure is one that is automatically saved when the program exits, as is described in the link to persistence. Dave Gudeman 04:40, 29 August 2006 (UTC)
It's a matter of your field of study. The sense in which you use it is encountered in some papers on OODBMS's. But the functional data structure meaning is widely known in research (everyone I've talked to about them immediately understood) and used in an entire subfield of widely cited papers. To list a few:
- J. Driscoll, N. Sarnak, D. D. Sleator, and R. Tarjan. Making Data Structures Persistent. Journal of Computer and System Sciences, 38:86--124, 1989. [1] (123 citations)
- N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29(7):669--679, 1986. [2] (115 citations)
- P. F. Dietz. Fully persistent arrays. In Workshop on Algorithms and Data Structures, volume 382 of Lecture Notes in Computer Science, pages 67--74. SpringerVerlag, August 1989. [3] (28 citations)
- J. Driscoll, D. Sleator, and R. Tarjan. Fully persistent lists with catenation. Journal of the ACM, 41(5):943-959, 1994. [4] (22 citations)
- Okasaki, C. (1998). Purely Functional Data Structures. Cambridge University Press. [5][6] (104 citations) Used throughout this seminal book, occuring dozens of times. Section 9.2 is entitle "Persistent Data Structures".
The name collision with the idea of disk-persisted data structures is unfortunate, and I wouldn't object to adding a note to clarify this. Deco 05:36, 29 August 2006 (UTC)
Not all purely functional data structures are persistent
For example, consider a queue. A standard representation user two lists, one reversed. When adding an element we add it to the first list, when removing an element we remove it from the second. When the second list is empty and we want to remove an element from the queue, we have to reverse the first list (reversal is O(N)), and this list becomes the new second list. We can remove the element from the second list now. Because we don't have to reverse most of the time, this queue is amortized O(1). But occasionally O(N)!
This queue is *not* persistent: what if we have a queue with an empty second list, and a nonempty first list of length N. When we use this list several times, and remove elements from it several times, the remove takes O(N) time. So this is no longer an O(1) queue! —Preceding unsigned comment added by 84.25.34.87 (talk) 18:31, 12 October 2007 (UTC)