|
4356
|
1 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.
|
|
|
2 2007-03-17.txt:01:54:52: <bsmntbombdood> FingerTree!
|
|
|
3 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)
|
|
|
4 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...
|
|
|
5 2007-04-22.txt:00:54:45: <oerjan> by using the FingerTree module which implements lazily concatenated sequences
|
|
|
6 2007-04-22.txt:01:17:14: <oerjan> you must recurse in any case unless you use the very clever FingerTree stuff
|
|
|
7 2007-04-28.txt:06:13:03: <oerjan> Haskell uses finger trees.
|
|
|
8 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
|
|
|
9 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).
|
|
|
10 2009-05-28.txt:02:47:54: * oerjan thinks this ties into the recent finger tree post on good math, bad math
|
|
|
11 2011-02-08.txt:21:05:47: <oerjan> elliott_: Seq is a slightly restricted finger tree structure, constant whatchamacallit time appending at both ends
|
|
|
12 2011-02-08.txt:21:06:24: <oerjan> (it doesn't support FingerTree's general Monoid indexing
|
|
|
13 2011-02-08.txt:21:23:49: <oerjan> but fingertrees are probably pretty heavyweight
|
|
|
14 2011-02-08.txt:21:24:21: <elliott_> "the Yi text editor specializes finger trees to finger strings for efficient storage of buffer text"
|
|
|
15 2011-02-08.txt:21:24:53: <elliott_> data FingerTree a
|
|
|
16 2011-02-08.txt:21:24:54: <elliott_> | Deep {-# UNPACK #-} !Int !(Digit a) (FingerTree (Node a)) !(Digit a)
|
|
|
17 2011-02-08.txt:21:41:22: <elliott_> oerjan: do I even need finger trees at that point? :P
|
|
|
18 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
|
|
|
19 2011-02-10.txt:20:52:01: <oerjan> elliott: fingertrees are very good for precisely that kind of query i think
|
|
|
20 2011-02-10.txt:20:52:12: <elliott> oerjan: O(log n) is good in my book... I'll try finger trees later
|
|
|
21 2011-05-13.txt:06:16:23: <elliott> Finger tree: http://i.imgur.com/sRyCi.png
|
|
|
22 2011-05-13.txt:06:18:25: <elliott> I kind of wish my hand was a finger tree now.
|
|
|
23 2011-05-13.txt:06:20:31: <elliott> i drew a finger tree http://i.imgur.com/sRyCi.png
|
|
|
24 2011-05-13.txt:06:21:15: <elliott> a finger tree, say
|
|
|
25 2011-05-13.txt:07:32:51: <elliott> oerjan: have you seen my picture of a finger tree
|
|
|
26 2011-05-13.txt:08:15:39: <oerjan> Sgeo: i suggest applying elliott's finger tree
|
|
|
27 2011-05-13.txt:08:15:54: <elliott> can never have enough fingers on the tree
|
|
|
28 2011-06-23.txt:18:49:40: <newsham> looks a little like a finger tree
|
|
|
29 2011-06-23.txt:18:49:49: <elliott_> newsham: Seq is based on finger trees, so...
|
|
|
30 2011-07-04.txt:00:25:16: <elliott_> oerjan: hmm, looks like finger trees are actually pretty close to this
|
|
|
31 2011-07-04.txt:00:25:43: <elliott_> oerjan: finger trees have O(n) indexing, right?
|
|
|
32 2011-07-04.txt:00:26:56: <oerjan> elliott_: finger trees have O(1) indexing at the end, is the major difference i think
|
|
|
33 2011-08-14.txt:20:28:25: <oerjan> fingerprinting should be done with finger trees, obviously
|
|
|
34 2011-09-05.txt:14:36:23: <elliott> Well, it's a finger tree, they're good at everything
|
|
|
35 2011-09-10.txt:03:48:42: <oerjan> even more superiorer: finger trees
|
|
|
36 2011-09-14.txt:01:34:12: <elliott> (Or, well, "finger tree of small vectors of codepoints" if you want to be precise.)
|
|
|
37 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
|
|
|
38 2011-09-16.txt:19:31:25: <Deewiant> I want FingerTree to use it, actually
|
|
|
39 2011-09-16.txt:19:31:39: <elliott> Deewiant: Which FingerTree
|
|
|
40 2011-09-16.txt:19:31:58: <Deewiant> He uses Data.FingerTree in trifecta
|
|
|
41 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
|
|
|
42 2011-09-19.txt:04:27:05: <elliott> wow, 2-3 finger trees were only invented in 2006?
|
|
|
43 2011-09-26.txt:11:56:35: <elliott> They're two-three finger trees and they're literally the best functional tree structure ever.
|
|
|
44 2011-09-26.txt:11:58:41: <CakeProphet> finger trees?
|
|
|
45 2011-09-26.txt:11:58:45: <elliott> http://en.wikipedia.org/wiki/Finger_tree
|
|
|
46 2011-09-26.txt:11:59:18: <elliott> apfelmus.nfshost.com/articles/monoid-fingertree.html
|
|
|
47 2011-10-07.txt:03:39:03: <elliott> auuugh return of the finger tree
|
|
|
48 2011-10-07.txt:03:41:27: <elliott> monqy: oh did you never see my finger tree
|
|
|
49 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
|
|
|
50 2011-10-07.txt:04:32:43: <CakeProphet> you probably want a finger tree of priority queues.
|
|
|
51 2011-10-13.txt:21:28:33: <elliott> oerjan: Hey, tell me why Data.Sequence doesn't export its finger tree implementation.
|
|
|
52 2011-10-13.txt:21:31:56: <oerjan> so it's more of a use case than a general finger tree
|
|
|
53 2011-10-13.txt:21:35:59: <oerjan> i recall i tried genuine Data.FingerTree for http://oerjan.nvg.org/esoteric/Dupdog.hs
|
|
|
54 2011-10-13.txt:21:39:13: <oerjan> i'm not convinced that haskell file could possibly compile, i'm using FingerTree unqualified...
|
|
|
55 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
|
|
|
56 2011-10-13.txt:21:52:31: <elliott> oerjan: are you sure that FingerTree isn't the one I linked to?
|
|
|
57 2011-10-13.txt:21:54:19: <elliott> oerjan: maybe I should just write my own finger trees
|
|
|
58 2011-10-13.txt:21:55:58: <oerjan> Sgeo|web: yes, finger trees
|
|
|
59 2011-10-13.txt:21:56:00: <elliott> Sgeo|web: yes, finger trees
|
|
|
60 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
|
|
|
61 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
|
|
|
62 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)
|
|
|
63 2011-10-13.txt:22:14:47: <copumpkin> for fingertrees?
|
|
|
64 2011-10-13.txt:22:15:02: <copumpkin> read the fingertree paper
|
|
|
65 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.)
|
|
|
66 2011-10-18.txt:23:44:08: <oerjan> `log elliot[t]> .*finger tree.*http
|
|
|
67 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
|
|
|
68 2011-11-07.txt:23:59:33: <Sgeo|web> I should attempt to understand finger trees, I think
|
|
|
69 2011-11-08.txt:00:00:01: <elliott> Sgeo|web: http://apfelmus.nfshost.com/articles/monoid-fingertree.html
|
|
|
70 2011-11-08.txt:22:54:07: <elliott> ais523: in @, the obvious implementation is a 2,3 finger tree of short vectors
|
|
|
71 2011-11-08.txt:22:54:16: <elliott> because 2,3 finger trees are literally every data structure
|
|
|
72 2011-11-08.txt:22:55:02: <elliott> ais523: it's just that 2,3 finger trees are unreasonably good at everything
|
|
|
73 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.
|
|
|
74 2011-11-16.txt:00:30:52: <CakeProphet> zippered finger trees.
|
|
|
75 2011-11-16.txt:00:31:07: <elliott> CakeProphet: Seq /is/ a finger tree
|
|
|
76 2011-11-16.txt:20:30:23: <elliott> oerjan: yes, I didn't feel like implementing my own finger trees :P
|
|
|
77 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
|
|
|
78 2012-02-25.txt:23:54:15: <elliott> there's 2,3 finger trees (aka Seq)
|
|
|
79 2012-03-04.txt:03:44:46: <kallisti> guards, dynamically dispatch this putrid finger tree!
|
|
|
80 2012-03-06.txt:19:24:39: <elliott> @tell oerjan [2007] <oerjan> by using the FingerTree module which implements lazily concatenated sequences
|
|
|
81 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
|
|
|
82 2012-06-23.txt:18:32:53: <Taneb> A Finger Tree, I think, is an example of what I've been asking about
|
|
|
83 2012-08-19.txt:20:48:50: <kmc> good math bad math already ran a completely wrong article about finger trees
|
|
|
84 2012-09-04.txt:21:52:52: <oerjan> (haskell's Data.Sequence uses "finger trees" for that)
|
|
|
85 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.
|
|
|
86 2012-09-04.txt:22:02:35: <oerjan> a deque definitely needs something like two-way (or finger trees)
|
|
|
87 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.
|
|
|
88 2013-01-13.txt:02:48:22: <kmc> you should check out edwardk's finger trees talk: http://comonad.com/reader/2010/finger-trees/
|
|
|
89 2013-01-13.txt:02:48:47: <oerjan> ah yes finger trees use such a trick as well
|
|
|
90 2013-02-07.txt:01:36:36: <kmc> what's the internal structure of text, again? finger tree? rope?
|
|
|
91 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
|
|
|
92 2013-02-07.txt:01:37:38: <elliott> edwardk has a UTF-8 finger-tree string implementation on Hackage (in several different packages).
|
|
|
93 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.
|
|
|
94 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
|
|
|
95 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
|
|
|
96 2013-04-05.txt:20:01:15: <oerjan> (actually finger trees are probably not category based enough for that)
|
|
|
97 2013-04-05.txt:20:02:43: <Taneb> ThatOtherPerson, finger trees are a cool kind of tree
|
|
|
98 2013-04-05.txt:20:02:48: <elliott> did monqy see the finger tree
|
|
|
99 2013-04-05.txt:20:03:46: <ThatOtherPerson> Oh, thank you for that image, now I know exactly what a finger tree looks like!
|
|
|
100 2013-04-05.txt:20:04:58: <Taneb> http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
|
|
|
101 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
|
|
|
102 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.
|
|
|
103 2013-04-15.txt:02:09:58: <FreeFull> Finger trees are crazy
|
|
|
104 2013-04-15.txt:02:10:01: <kmc> edwardk has a good talk about finger trees
|
|
|
105 2013-04-15.txt:02:10:39: <elliott> i think the problem with finger trees is that they are boring
|
|
|
106 2013-04-15.txt:02:11:49: <kmc> finger tree sequences of big unboxed chunks of text, annotated with source positions and what not
|
|
|
107 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
|
|
|
108 2013-04-15.txt:02:17:10: <Sgeo> I should learn what finger trees are
|
|
|
109 2013-04-15.txt:02:17:59: <elliott> Sgeo: http://apfelmus.nfshost.com/articles/monoid-fingertree.html
|
|
|
110 2014-01-19.txt:01:10:23: <oerjan> `log finger.*tree.*jp.?g
|
|
|
111 2014-01-19.txt:01:11:16: <oerjan> `pastelogs finger.*tree
|
