Content deleted Content added
m Fixing archives for YouTube videos (WP:Link_Rot, WP:CEFC#Pre-emptive_archiving, phab:T294880) |
|||
Line 543:
=== Persistent hash array mapped trie ===
A persistent hash array mapped trie is a specialized variant of a [[hash array mapped trie]] that will preserve previous versions of itself on any updates. It is often used to implement a general purpose persistent map data structure.<ref name=":1">{{Citation|last=BoostCon|title=C++Now 2017: Phil Nash "The Holy Grail!? A Persistent Hash-Array-Mapped Trie for C++"|date=2017-06-13|url=https://www.youtube.com/watch?v=WT9kmIE3Uis |archive-url=https://ghostarchive.org/varchive/youtube/20211221/WT9kmIE3Uis |archive-date=2021-12-21 |url-status=live|access-date=2018-10-22}}{{cbignore}}</ref>
Hash array mapped tries were originally described in a 2001 paper by [[Phil Bagwell]] entitled "Ideal Hash Trees". This paper presented a mutable [[Hash table]] where "Insert, search and delete times are small and constant, independent of key set size, operations are O(1). Small worst-case times for insert, search and removal operations can be guaranteed and misses cost less than successful searches".<ref>{{Cite journal|last=Phil|first=Bagwell|date=2001|title=Ideal Hash Trees|url=https://infoscience.epfl.ch/record/64398|language=en}}</ref> This data structure was then modified by [[Rich Hickey]] to be fully persistent for use in the [[Clojure]] programming language.<ref>{{Cite web|url=https://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hickey|title=Are We There Yet?|website=InfoQ|access-date=2018-10-22}}</ref>
Line 587:
=== Scala ===
The Scala programming language promotes the use of persistent data structures for implementing programs using "Object-Functional Style".<ref>{{Cite news|url=https://blog.codecentric.de/en/2015/08/essence-of-object-functional-programming-practical-potential-of-scala/|title=The Essence of Object-Functional Programming and the Practical Potential of Scala - codecentric AG Blog|date=2015-08-31|work=codecentric AG Blog|access-date=2018-10-23|language=en-US}}</ref> Scala contains implementations of many Persistent data structures including Linked Lists, [[Red–black tree]]s, as well as persistent hash array mapped tries as introduced in Clojure.<ref>{{Citation|last=ClojureTV|title=Extreme Cleverness: Functional Data Structures in Scala - Daniel Spiewak|date=2013-01-07|url=https://www.youtube.com/watch?v=pNhBQJN44YQ|access-date=2018-10-23}}{{cbignore}}{{Dead Youtube links}}</ref>
==Garbage collection==
| |||