![]() | This article has not yet been rated on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
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)
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)
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)
How about I replace the hand-drawn diagrams with some graphviz svgs?
graph G {
{
nodelabel=""];
_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 {
_rlabel=""];
a b
{
nodelabel=""];
_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 {
_rlabel=""];
a b
{
nodelabel=""];
_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
}
Vlisch ( talk) 04:59, 11 December 2018 (UTC)
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)
![]() | This article has not yet been rated on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
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)
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)
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)
How about I replace the hand-drawn diagrams with some graphviz svgs?
graph G {
{
nodelabel=""];
_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 {
_rlabel=""];
a b
{
nodelabel=""];
_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 {
_rlabel=""];
a b
{
nodelabel=""];
_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
}
Vlisch ( talk) 04:59, 11 December 2018 (UTC)
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)