Mercurial > repo
view paste/paste.31614 @ 6894:1041408d241c
<oerjan> le/rn soviet union/In ancient history, the Soviet Union used to be the THEM. They believed in absurd principles like "Better Red than Dead". Then Ronald Reagan invented Star Wars to destroy it, after which there seemed to be no the THEM for a while.
author | HackBot |
---|---|
date | Tue, 16 Feb 2016 21:39:22 +0000 |
parents | 8a22ba8a273e |
children |
line wrap: on
line source
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