2007-03-17.txt:01:28:16: <oerjan> I found a downloadable Data.FingerTree module in which you can select any Monoid as your size measure.
2007-03-17.txt:01:54:52: <bsmntbombdood> FingerTree!
2007-03-26.txt:23:42:24: <oerjan> The files are oerjan.nvg.org/esoteric/Dupdog.hs and oerjan.nvg.org/esoteric/FingerTree.hs (third party module)
2007-04-22.txt:00:47:15: <oerjan> http://oerjan.nvg.org/esoteric/Dupdog.hs + FingerTree.hs.  You can in theory use it if you can put the right functions together... 
2007-04-22.txt:00:54:45: <oerjan> by using the FingerTree module which implements lazily concatenated sequences
2007-04-22.txt:01:17:14: <oerjan> you must recurse in any case unless you use the very clever FingerTree stuff
2007-04-28.txt:06:13:03: <oerjan> Haskell uses finger trees.
2008-08-10.txt:19:39:20: <Deewiant> AnMaster: so you think it's a good idea to have a huge fingerprint tree, only one of which does something useful, the others are only supporting instructions for that one? :-P
2008-10-23.txt:07:37:37: <fizzie> Yes. The Funge-98 program uses the FILE fingerprint to seek around the tree-structured n-gram model (it's something like 200 megabytes for the IRC logs).
2009-05-28.txt:02:47:54: * oerjan thinks this ties into the recent finger tree post on good math, bad math
2011-02-08.txt:21:05:47: <oerjan> elliott_: Seq is a slightly restricted finger tree structure, constant whatchamacallit time appending at both ends
2011-02-08.txt:21:06:24: <oerjan> (it doesn't support FingerTree's general Monoid indexing
2011-02-08.txt:21:23:49: <oerjan> but fingertrees are probably pretty heavyweight
2011-02-08.txt:21:24:21: <elliott_> "the Yi text editor specializes finger trees to finger strings for efficient storage of buffer text"
2011-02-08.txt:21:24:53: <elliott_> data FingerTree a
2011-02-08.txt:21:24:54: <elliott_> 	| Deep {-# UNPACK #-} !Int !(Digit a) (FingerTree (Node a)) !(Digit a)
2011-02-08.txt:21:41:22: <elliott_> oerjan: do I even need finger trees at that point? :P
2011-02-08.txt:21:43:43: <oerjan> elliott_: um the finger trees are to get the efficient appending of an element at the end
2011-02-10.txt:20:52:01: <oerjan> elliott: fingertrees are very good for precisely that kind of query i think
2011-02-10.txt:20:52:12: <elliott> oerjan: O(log n) is good in my book... I'll try finger trees later
2011-05-13.txt:06:16:23: <elliott> Finger tree: http://i.imgur.com/sRyCi.png
2011-05-13.txt:06:18:25: <elliott> I kind of wish my hand was a finger tree now.
2011-05-13.txt:06:20:31: <elliott> i drew a finger tree http://i.imgur.com/sRyCi.png
2011-05-13.txt:06:21:15: <elliott> a finger tree, say
2011-05-13.txt:07:32:51: <elliott> oerjan: have you seen my picture of a finger tree
2011-05-13.txt:08:15:39: <oerjan> Sgeo: i suggest applying elliott's finger tree
2011-05-13.txt:08:15:54: <elliott> can never have enough fingers on the tree
2011-06-23.txt:18:49:40: <newsham> looks a little like a finger tree
2011-06-23.txt:18:49:49: <elliott_> newsham: Seq is based on finger trees, so...
2011-07-04.txt:00:25:16: <elliott_> oerjan: hmm, looks like finger trees are actually pretty close to this
2011-07-04.txt:00:25:43: <elliott_> oerjan: finger trees have O(n) indexing, right?
2011-07-04.txt:00:26:56: <oerjan> elliott_: finger trees have O(1) indexing at the end, is the major difference i think
2011-08-14.txt:20:28:25: <oerjan> fingerprinting should be done with finger trees, obviously
2011-09-05.txt:14:36:23: <elliott> Well, it's a finger tree, they're good at everything
2011-09-10.txt:03:48:42: <oerjan> even more superiorer: finger trees
2011-09-14.txt:01:34:12: <elliott> (Or, well, "finger tree of small vectors of codepoints" if you want to be precise.)
2011-09-16.txt:18:06:31: <elliott> Deewiant: Data.Sequence is literally just a rope done with finger trees, so ostensibly it should be suitable for just about anything
2011-09-16.txt:19:31:25: <Deewiant> I want FingerTree to use it, actually
2011-09-16.txt:19:31:39: <elliott> Deewiant: Which FingerTree
2011-09-16.txt:19:31:58: <Deewiant> He uses Data.FingerTree in trifecta
2011-09-16.txt:19:32:28: <Deewiant> Evidently just using a Trifecta parser requires using a FingerTree, a Rope, a UTF8 ByteString, and an ordinary ByteString
2011-09-19.txt:04:27:05: <elliott> wow, 2-3 finger trees were only invented in 2006?
2011-09-26.txt:11:56:35: <elliott> They're two-three finger trees and they're literally the best functional tree structure ever.
2011-09-26.txt:11:58:41: <CakeProphet> finger trees?
2011-09-26.txt:11:58:45: <elliott> http://en.wikipedia.org/wiki/Finger_tree
2011-09-26.txt:11:59:18: <elliott> apfelmus.nfshost.com/articles/monoid-fingertree.html
2011-10-07.txt:03:39:03: <elliott> auuugh return of the finger tree
2011-10-07.txt:03:41:27: <elliott> monqy: oh did you never see my finger tree
2011-10-07.txt:04:27:51: <oerjan> <elliott> shachaf: Also, what's a map structure with fast minKey (O(log n) at least) that isn't Map or IntMap? <-- finger trees
2011-10-07.txt:04:32:43: <CakeProphet> you probably want a finger tree of priority queues.
2011-10-13.txt:21:28:33: <elliott> oerjan: Hey, tell me why Data.Sequence doesn't export its finger tree implementation.
2011-10-13.txt:21:31:56: <oerjan> so it's more of a use case than a general finger tree
2011-10-13.txt:21:35:59: <oerjan> i recall i tried genuine Data.FingerTree for http://oerjan.nvg.org/esoteric/Dupdog.hs
2011-10-13.txt:21:39:13: <oerjan> i'm not convinced that haskell file could possibly compile, i'm using FingerTree unqualified...
2011-10-13.txt:21:40:42: <elliott> http://hackage.haskell.org/packages/archive/fingertree/0.0.1.0/doc/html/Data-FingerTree.html has generic finger trees, but dammit I want the specialised version
2011-10-13.txt:21:52:31: <elliott> oerjan: are you sure that FingerTree isn't the one I linked to?
2011-10-13.txt:21:54:19: <elliott> oerjan: maybe I should just write my own finger trees
2011-10-13.txt:21:55:58: <oerjan> Sgeo|web: yes, finger trees
2011-10-13.txt:21:56:00: <elliott> Sgeo|web: yes, finger trees
2011-10-13.txt:21:59:39: <oerjan> elliott: i am wondering if Data.FingerTree is lazy enough for my Dupdog.hs to actually work efficiently on huge duplications
2011-10-13.txt:22:08:06: <elliott> oerjan: anyway I don't really want to use the fingertree package because (a) it uses fundeps in a way that should really be type families and (b) I bet it's less tuned than the Data.Sequence specialisation that would work for me :P
2011-10-13.txt:22:08:26: <elliott> oerjan: (I want to create a rope type based on a finger tree of UTF-8 bytestrings, because Text is disappointing in its internals)
2011-10-13.txt:22:14:47: <copumpkin> for fingertrees?
2011-10-13.txt:22:15:02: <copumpkin> read the fingertree paper
2011-10-18.txt:23:42:30: <CakeProphet> (notice the infection of Haskell mind virus in its final stage. It won't be long before oerjan degenerates into a non-sentient pile of fleshy finger trees.)
2011-10-18.txt:23:44:08: <oerjan> `log elliot[t]> .*finger tree.*http
2011-10-18.txt:23:44:40: <HackEgo> 2011-05-13.txt:06:20:31: <elliott> i drew a finger tree http://i.imgur.com/sRyCi.png
2011-11-07.txt:23:59:33: <Sgeo|web> I should attempt to understand finger trees, I think
2011-11-08.txt:00:00:01: <elliott> Sgeo|web: http://apfelmus.nfshost.com/articles/monoid-fingertree.html
2011-11-08.txt:22:54:07: <elliott> ais523: in @, the obvious implementation is a 2,3 finger tree of short vectors
2011-11-08.txt:22:54:16: <elliott> because 2,3 finger trees are literally every data structure
2011-11-08.txt:22:55:02: <elliott> ais523: it's just that 2,3 finger trees are unreasonably good at everything
2011-11-16.txt:00:16:39: <CakeProphet> as in use a 2-3 finger tree to store a sequence of cursors, which point to two sub Seqs.
2011-11-16.txt:00:30:52: <CakeProphet> zippered finger trees.
2011-11-16.txt:00:31:07: <elliott> CakeProphet: Seq /is/ a finger tree
2011-11-16.txt:20:30:23: <elliott> oerjan: yes, I didn't feel like implementing my own finger trees :P
2011-11-17.txt:04:04:29: <elliott> oerjan: the list version is easy ofc, it's doing it with a finger tree that's hard
2012-02-25.txt:23:54:15: <elliott> there's 2,3 finger trees (aka Seq)
2012-03-04.txt:03:44:46: <kallisti> guards, dynamically dispatch this putrid finger tree!
2012-03-06.txt:19:24:39: <elliott> @tell oerjan [2007] <oerjan> by using the FingerTree module which implements lazily concatenated sequences
2012-03-07.txt:03:12:09: <lambdabot> elliott said 7h 47m 25s ago: [2007] <oerjan> by using the FingerTree module which implements lazily concatenated sequences
2012-06-23.txt:18:32:53: <Taneb> A Finger Tree, I think, is an example of what I've been asking about
2012-08-19.txt:20:48:50: <kmc> good math bad math already ran a completely wrong article about finger trees
2012-09-04.txt:21:52:52: <oerjan> (haskell's Data.Sequence uses "finger trees" for that)
2012-09-04.txt:21:54:35: <oerjan> unless you want to reverse the entire data structure when wrapping around, then you can use the tape trick modified.  finger trees have less latency or something.
2012-09-04.txt:22:02:35: <oerjan> a deque definitely needs something like two-way (or finger trees)
2012-09-20.txt:19:42:09: <oerjan> fingertrees are supposed to have O(1) push and pop.  i'm not sure if that's just average, though.
2013-01-13.txt:02:48:22: <kmc> you should check out edwardk's finger trees talk: http://comonad.com/reader/2010/finger-trees/
2013-01-13.txt:02:48:47: <oerjan> ah yes finger trees use such a trick as well
2013-02-07.txt:01:36:36: <kmc> what's the internal structure of text, again? finger tree? rope?
2013-02-07.txt:01:37:20: <kmc> it seems like a good data structure would be a finger tree of ~few-kB UTF-8 chunks
2013-02-07.txt:01:37:38: <elliott> edwardk has a UTF-8 finger-tree string implementation on Hackage (in several different packages).
2013-02-07.txt:01:41:50: <elliott> Hmm, I guess you can define (Rope w a) as a w-annotated FingerTree of vectors of a.
2013-04-05.txt:13:33:03: <kmc> ThatOtherPerson: edwardk has this 'finger tree' data structure library which keeps an annotation at each layer of the tree
2013-04-05.txt:19:58:30: <oerjan> <kmc> ThatOtherPerson: edwardk has this 'finger tree' data structure library which keeps an annotation at each layer of the tree <-- afaict edwardk is neither the inventor nor maintainer of the fingertree package
2013-04-05.txt:20:01:15: <oerjan> (actually finger trees are probably not category based enough for that)
2013-04-05.txt:20:02:43: <Taneb> ThatOtherPerson, finger trees are a cool kind of tree
2013-04-05.txt:20:02:48: <elliott> did monqy see the finger tree
2013-04-05.txt:20:03:46: <ThatOtherPerson> Oh, thank you for that image, now I know exactly what a finger tree looks like!
2013-04-05.txt:20:04:58: <Taneb> http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
2013-04-05.txt:20:05:58: <ThatOtherPerson> Taneb: I do not believe that is truly what a finger tree is; it is much to boring; I am sticking with elliott's interpretation
2013-04-15.txt:02:09:40: <oerjan> FreeFull: the finger tree used for immutable (de)que(ues) in Data.Sequence are quite insanely clever, much more complicated than a list.  but i've read they're still quite efficient.
2013-04-15.txt:02:09:58: <FreeFull> Finger trees are crazy
2013-04-15.txt:02:10:01: <kmc> edwardk has a good talk about finger trees
2013-04-15.txt:02:10:39: <elliott> i think the problem with finger trees is that they are boring
2013-04-15.txt:02:11:49: <kmc> finger tree sequences of big unboxed chunks of text, annotated with source positions and what not
2013-04-15.txt:02:13:36: <oerjan> elliott: i was surprised to read that finger trees are more efficient than that pair of lists thing
2013-04-15.txt:02:17:10: <Sgeo> I should learn what finger trees are
2013-04-15.txt:02:17:59: <elliott> Sgeo: http://apfelmus.nfshost.com/articles/monoid-fingertree.html
2014-01-19.txt:01:10:23: <oerjan> `log finger.*tree.*jp.?g
2014-01-19.txt:01:11:16: <oerjan> `pastelogs finger.*tree