- It's probably not nonsense. However, no one can understand what it is exactly. Maybe some LISP or Haskell "code" can be added so we can then gripe about the syntax and how it creates the urge to punch people. --126.96.36.199 (talk) 12:49, 7 January 2010 (UTC)
Finger tree in Scala
the linked example used Scala 2.6.1, scalaz: http://code.google.com/p/scalaz/ also contains an implementation: http://code.google.com/p/scalaz/source/browse/trunk/core/src/main/scala/scalaz/FingerTree.scala?spec=svn1445&r=1445 It seems scalaz provides quite a lot of nice functional stuff from Haskell, but usable with Scala.
—Preceding unsigned comment added by 188.8.131.52 (talk) 10:40, 26 September 2010 (UTC)
Unpacking the 2-3 Finger tree paper
Two of the citation (the Guibas paper on finger B-trees and the Tsakalidis paper on finger AVL trees) seems to be about Finger search trees: they are imperative data structures, not functional data structures. My (possibly original research) thought is that Finger trees differ from Finger search trees in that with the right monoid, finger trees can also store unsorted values; thus function as a list/vector, or a stack/queue/deque.
In any case, when functional programming people talk about finger trees, they seem to be talking about the 2-3 version from Hinze and Paterson. The paper is quite hard to read, possibly because I don't understand Haskell, but also because it contains a few different ideas:
- Implementing different data structures by storing data in leaves, and labelling internal nodes with different monoids.
- Explained in http://apfelmus.nfshost.com/articles/monoid-fingertree.html, by showing how you can implement a list and a priority queue using monoid-labelled trees. I find the Haskell code in here much easier to understand.
- Also explained here. http://scienceblogs.com/goodmath/2009/05/27/finally-finger-trees/ (He initially thought that's all there is to finger trees, but realized in a later article that this isn't the case.)
- Implementing finger search by splitting the tree at the finger position; the new minimal/maximal elements in the new tree becomes fingers.
- "Folding up" an 2-3 tree to form a finger tree.
- http://maniagnosis.crsr.net/2010/11/finger-trees.html makes the observation that "bare finger trees by themselves [that is, without monoid labels] support efficient, amortized O(1) deque operations ([...]) as well as O(log n) sequence concatenation." --Kakurady (talk) 12:10, 24 April 2014 (UTC)