Talk:Finger tree

Speedy request

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

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

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.

  You can find this idea in Figure 3 of Tsakalidis, A. K. (1985), "AVL-trees for localized search", Information and Control, 67 (1–3): 173–194, doi:10.1016/S0019-9958(85)80034-6

• "Folding up" an 2-3 tree to form a finger tree.

  Explained at http://scienceblogs.com/goodmath/2010/04/26/finger-trees-done-right-i-hope/

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)

Diagrams

How about I replace the hand-drawn diagrams with some graphviz svgs?

graph G {
  {
     node[label=""];
    _r -- _t1
    _r -- _t2 
  
    _t1 -- _s1
    _t1 -- _s2
    _t1 -- _s3
  
    _t2 -- _s4
    _t2 -- _s5
    _t2 -- _s6
  }
  _s1 -- a
  _s1 -- b

  _s2 -- c
  _s2 -- d

  _s3 -- e
  _s3 -- f

  _s4 -- g
  _s4 -- h
  _s4 -- i

  _s5 -- j
  _s5 -- k

  _s6 -- l
  _s6 -- m
  _s6 -- n
}

graph G2 {
 _r[label=""];
 a b

 {
    node[label=""];
    _r _t1 _t2 _s1 _s2 _s3 _s4 _s5 _s6
 }

  _s1 -- a
  _s1 -- b
  _s1 -- _t1
  
  _s6 -- _t2
  _s6 -- l
  _s6 -- m
  _s6 -- n

  _t1 -- _r
  _t2 -- _r 

  _t1 -- _s2
  _t1 -- _s3

  _t2 -- _s4
  _t2 -- _s5

  _s2 -- c
  _s2 -- d

  _s3 -- e
  _s3 -- f

  _s4 -- g
  _s4 -- h
  _s4 -- i

  _s5 -- j
  _s5 -- k
}

graph G3 {
 _r[label=""];
 a b

 {
    node[label=""];
    _r _t _s _s2 _s3 _s4 _s5
 }

  _s -- a
  _s -- b

  _s -- _t
  
  _s -- l
  _s -- m
  _s -- n

  _t -- _r

  _t -- _s2
  _t -- _s3

  _t -- _s4
  _t -- _s5

  _s2 -- c
  _s2 -- d

  _s3 -- e
  _s3 -- f

  _s4 -- g
  _s4 -- h
  _s4 -- i

  _s5 -- j
  _s5 -- k
}

File:Finger tree one spine.svg

Vlisch (talk) 04:59, 11 December 2018 (UTC)

General Quality

I believe the quality of this whole article is pretty low. I'd suggest to use more of the [original paper](http://www.staff.city.ac.uk/~ross/papers/FingerTree.html) and these two: [1] and [2] as sources, and talk more about the ideas behind and the performance. Finger trees deserve it. Vlad Patryshev (talk) 18:03, 22 February 2020 (UTC)