Talk:Finger tree

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
WikiProject Computing  
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

Speedy request[edit]

I hardly think this is patent nonsense. If you'll just hold on for a while and follow the links, it's a perfectly sensible computer science topic. --Gwern (contribs) 20:45 16 January 2008 (GMT)

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. --88.75.239.114 (talk) 12:49, 7 January 2010 (UTC)

Finger tree in Scala[edit]

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 84.162.175.154 (talk) 10:40, 26 September 2010 (UTC) 

Unpacking the 2-3 Finger tree paper[edit]

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:

There are possibly more ideas how the 2-3 finger tree works, but explaining these should give a pretty good understanding. --Kakurady (talk) 12:05, 24 April 2014 (UTC)

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)