This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
This article is or was the subject of a Wiki Education Foundation-supported course assignment. Further details are available on the course page. Student editor(s): Ethan McCue.
Above undated message substituted from Template:Dashboard.wikiedu.org assignment by PrimeBOT ( talk) 06:26, 17 January 2022 (UTC)
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)
Purely Functional describes how 'purely functional' computer languages deal with variables. So 1) the title Purely Functional is perfectly valid; it is the name of a category of computer programming languages, in the same way as Object Oriented, Imperative, Declarative, Duck-typed, etc. 2) This article should not be merged with any other discussion of data structures because this article is not about the data structures themselves, but rather the way that purely functional computer languages deal with them - whether or not they are persistent. —Preceding unsigned comment added by 202.63.49.61 ( talk) 10:45, 21 January 2010 (UTC)
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)
I would argue there is no implicit persistance. Although there is internal reference sharing, as is the case with list types in ML, there is no way to implicitly refer to these elements in the list. The programmer would have to declare variables for every sublist they wanted a reference to, but changing that reference would create a new list. Specificaly a list which references the values of the old list to the location where they differ and adds its unique elements and is therefore considered a new list. At this point the programmer is at a loss without language support for such a feature. There are similarities between the notion of persistance and functional data structures but nothing tangibly usefull. Every change made to a data structure in a functional language returns a new reference to the updated structure and provides no way to acceess the version previously modified. Now consider garbage collection on unreachable references, the removed element of the list.
I have removed the reference to the VList data structure. Vlists are not really a "persistent counterpart to the array". They are not persistent at all if you update them as an array. They do allow O(1) random read access if you update them as a list, but that's only if you update them in a partially persistent way. If you update them in a fully persistent way, then the random read access is not efficient. —Preceding unsigned comment added by Ken Hirsch ( talk • contribs) 07:40, 21 May 2008 (UTC)
"While persistence can be achieved by simple copying, this is inefficient in CPU and RAM usage" While true, I came here from Rope page and in general I would think as for Rope, some operations are slower (there e.g. indexing). Some data structures might be accessed a lot such as strings (ropes) in an editor say, but updated/edited at a human speed (to be fair data structute would also be read infrequently, when e.g. scrolling page?).
It seems to me that a structure based on pointers such as ropes and all persistents(?) would have less locality of reference than some simpler ones such as arrays. In general a hybrid might reduce that drawback arbitrarily (but possible and still be persistent).
I could look into all of this (anyone have answers and they belong here?); in general it seems to me lazy languages such as Haskell have not taken the world by a storm and the newer eager Julia is, and it is fast. I wander if the eager, side-effect functional variant is the way to go (want to find out if Julia has a fatal flaw..). comp.arch ( talk) 18:38, 1 November 2014 (UTC)
I was thinking that this article could be more useful with a description of Persistent Hash Array Mapped Tries and how they and other persistent data structures have been adopted by languages like Clojure, Scala, Java, Javascript, etc. I know at least that the "Persistent Map" based on that technique has a good deal of adoption in the React community. Curious as to anyone elses thoughts on that. — Preceding unsigned comment added by Ethan McCue ( talk • contribs) 21:28, 9 October 2018 (UTC)
The intro blurb is 4 paragraphs and mentions efficiency issues. Not that these aren't worth noting, but it seems dubious that this information would be useful at a glance. Maybe it should be broken down into a new or existing section? — Preceding unsigned comment added by Ethan McCue ( talk • contribs) 19:07, 26 November 2018 (UTC)
The page contains multiple statements like this one:
> Haskell is a pure functional language and therefore does not allow for mutation. Therefore all data structures in the language are persistent, as it is impossible to not preserve the previous state of a data structure with functional semantics.[15] This is because any change to a data structure that would render previous versions of a data structure invalid would violate referential transparency.
I have the feeling that the terms 'persistency' and 'immutability' are here conflated: It would be more correct to say that a pure language requires _immutable_ data structures (to not violate referential transparency), and that persistent data structures are the only (known) _efficient_ implementations of these.
Qqwy ( talk) 07:02, 13 May 2019 (UTC)
There is a claim in about the performance characteristics of Copy on Write algorithms. It is already marked for "Citation needed". I think it is factually false, as the CPU complexity of such a write is proportional to the number of writes and the length of the data structure. As the lengths of the data structure itself is proportional to the number of writes, we can say it is O(n^2). For space complexity, it is also O(n^2) for similar reasons.
I am not an editor, and I have very little experience on how such issues should be handled. — Preceding unsigned comment added by 2001:4C4C:20AD:E900:19A0:D648:E263:AD66 ( talk) 11:40, 17 November 2019 (UTC)
To my understanding, based on the description, Fat nodes and A combination are only partially persistent -- I.e. one can modify only the latest version of the data structure. That is because they assume that the time dimension is linear rather than a DAG. The article doesn't mention this though. In principle one could adapt Fat nodes to hold an entire revision DAG in each node to make them fully persistent, but I cannot think of a similar modification for A combination. Please correct me if I'm wrong. bungalo ( talk) 19:02, 26 November 2019 (UTC)
Path copying is a copy-on-write that copies a node when it's modified. Should be combined or mentioned in the article? bungalo ( talk) 19:36, 26 November 2019 (UTC)
This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
This article is or was the subject of a Wiki Education Foundation-supported course assignment. Further details are available on the course page. Student editor(s): Ethan McCue.
Above undated message substituted from Template:Dashboard.wikiedu.org assignment by PrimeBOT ( talk) 06:26, 17 January 2022 (UTC)
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)
Purely Functional describes how 'purely functional' computer languages deal with variables. So 1) the title Purely Functional is perfectly valid; it is the name of a category of computer programming languages, in the same way as Object Oriented, Imperative, Declarative, Duck-typed, etc. 2) This article should not be merged with any other discussion of data structures because this article is not about the data structures themselves, but rather the way that purely functional computer languages deal with them - whether or not they are persistent. —Preceding unsigned comment added by 202.63.49.61 ( talk) 10:45, 21 January 2010 (UTC)
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)
I would argue there is no implicit persistance. Although there is internal reference sharing, as is the case with list types in ML, there is no way to implicitly refer to these elements in the list. The programmer would have to declare variables for every sublist they wanted a reference to, but changing that reference would create a new list. Specificaly a list which references the values of the old list to the location where they differ and adds its unique elements and is therefore considered a new list. At this point the programmer is at a loss without language support for such a feature. There are similarities between the notion of persistance and functional data structures but nothing tangibly usefull. Every change made to a data structure in a functional language returns a new reference to the updated structure and provides no way to acceess the version previously modified. Now consider garbage collection on unreachable references, the removed element of the list.
I have removed the reference to the VList data structure. Vlists are not really a "persistent counterpart to the array". They are not persistent at all if you update them as an array. They do allow O(1) random read access if you update them as a list, but that's only if you update them in a partially persistent way. If you update them in a fully persistent way, then the random read access is not efficient. —Preceding unsigned comment added by Ken Hirsch ( talk • contribs) 07:40, 21 May 2008 (UTC)
"While persistence can be achieved by simple copying, this is inefficient in CPU and RAM usage" While true, I came here from Rope page and in general I would think as for Rope, some operations are slower (there e.g. indexing). Some data structures might be accessed a lot such as strings (ropes) in an editor say, but updated/edited at a human speed (to be fair data structute would also be read infrequently, when e.g. scrolling page?).
It seems to me that a structure based on pointers such as ropes and all persistents(?) would have less locality of reference than some simpler ones such as arrays. In general a hybrid might reduce that drawback arbitrarily (but possible and still be persistent).
I could look into all of this (anyone have answers and they belong here?); in general it seems to me lazy languages such as Haskell have not taken the world by a storm and the newer eager Julia is, and it is fast. I wander if the eager, side-effect functional variant is the way to go (want to find out if Julia has a fatal flaw..). comp.arch ( talk) 18:38, 1 November 2014 (UTC)
I was thinking that this article could be more useful with a description of Persistent Hash Array Mapped Tries and how they and other persistent data structures have been adopted by languages like Clojure, Scala, Java, Javascript, etc. I know at least that the "Persistent Map" based on that technique has a good deal of adoption in the React community. Curious as to anyone elses thoughts on that. — Preceding unsigned comment added by Ethan McCue ( talk • contribs) 21:28, 9 October 2018 (UTC)
The intro blurb is 4 paragraphs and mentions efficiency issues. Not that these aren't worth noting, but it seems dubious that this information would be useful at a glance. Maybe it should be broken down into a new or existing section? — Preceding unsigned comment added by Ethan McCue ( talk • contribs) 19:07, 26 November 2018 (UTC)
The page contains multiple statements like this one:
> Haskell is a pure functional language and therefore does not allow for mutation. Therefore all data structures in the language are persistent, as it is impossible to not preserve the previous state of a data structure with functional semantics.[15] This is because any change to a data structure that would render previous versions of a data structure invalid would violate referential transparency.
I have the feeling that the terms 'persistency' and 'immutability' are here conflated: It would be more correct to say that a pure language requires _immutable_ data structures (to not violate referential transparency), and that persistent data structures are the only (known) _efficient_ implementations of these.
Qqwy ( talk) 07:02, 13 May 2019 (UTC)
There is a claim in about the performance characteristics of Copy on Write algorithms. It is already marked for "Citation needed". I think it is factually false, as the CPU complexity of such a write is proportional to the number of writes and the length of the data structure. As the lengths of the data structure itself is proportional to the number of writes, we can say it is O(n^2). For space complexity, it is also O(n^2) for similar reasons.
I am not an editor, and I have very little experience on how such issues should be handled. — Preceding unsigned comment added by 2001:4C4C:20AD:E900:19A0:D648:E263:AD66 ( talk) 11:40, 17 November 2019 (UTC)
To my understanding, based on the description, Fat nodes and A combination are only partially persistent -- I.e. one can modify only the latest version of the data structure. That is because they assume that the time dimension is linear rather than a DAG. The article doesn't mention this though. In principle one could adapt Fat nodes to hold an entire revision DAG in each node to make them fully persistent, but I cannot think of a similar modification for A combination. Please correct me if I'm wrong. bungalo ( talk) 19:02, 26 November 2019 (UTC)
Path copying is a copy-on-write that copies a node when it's modified. Should be combined or mentioned in the article? bungalo ( talk) 19:36, 26 November 2019 (UTC)