From: Nicolas C. <war...@fr...> - 2004-08-28 18:52:13
|
> > %Jesse: > > Back to the subject I have thought a little by myself and I think now that > > DLList could be added to ExtLib, if it replaces the RefList module. I think > > OptParse uses RefList. YAMTD Yet Another Modification To Do :) Nicolas |
From: Bardur A. <oca...@sc...> - 2004-08-28 19:00:26
|
On Sat, Aug 28, 2004 at 08:53:01PM +0200, Nicolas Cannasse wrote: > > > %Jesse: > > > Back to the subject I have thought a little by myself and I think now > that > > > DLList could be added to ExtLib, if it replaces the RefList module. I > think > > > > OptParse uses RefList. > > YAMTD > > Yet Another Modification To Do :) > Well, maybe... I was just pointing out that it might be a bad idea to remove RefList *now*. -- Bardur Arantsson <ba...@im...> <ba...@sc...> - All humans are vermin in the eyes of Morbo! Morbo | Futurama |
From: Jesse D. G. <je...@wi...> - 2004-08-29 15:58:35
|
Nicolas Cannasse wrote: >>>type opcode >>>type code = >>> | Op of opcode >>> | Array of code array >>>type key = array * int (* pointer in the tree *) >>> >>> >>Yeah I've thought of that, but: >> >>The problem is it makes pattern detection hard. >>For example to detect the sequence A B with a slist >>you just recursively seek >> >>A :: (B :: _ ) as tail -> .. >> >> > >That's true. You might want to keep some parts of your geneate code flat but >that's something you can anticipate. First apply as much as possible of >rewriting rules, then flatten, then loop using you reach a fixpoint. You can >also minimize the number of allocations by implementing a two-steps flatten >algorithm : first recursivly calculate the size of the array needed then >alloc it and recursively fill it. > >%Jesse: >Back to the subject I have thought a little by myself and I think now that >DLList could be added to ExtLib, if it replaces the RefList module. I think >almost nobody use it, so why not replace the ref-list by a mutable list, and >why not a double linked list, that is my thinking. Which of Jesse or Brian >will take over the DLList maintenance in ExtLib ? If Brian then you can >commit it (as well as IndexedTree as discussed before) , if Jesse then >please send me your SF account so I can add you to the developers list. > > Well, Brian, do you want it? I don't mind either way. I *would* like to discuss implementation details a bit before we commit the code though. You can download the source and view the current docs here for reference: http://www.wingnet.net/~jesse/ocaml/dllist/ Things that I think warrant discussion: 1.) I probably need to write the following functions: rev_iter rev_map rev_to_list rev_of_list Is everyone OK with so many rev_ functions? The advantage is that they're identical to the normal functions as far as performance is concerned, they just work in the opposite direction. Can anyone think of a better way to do it? Perhaps a boolean options argument? i.e. ?(rev=false) This adds overhead to each function though, as we'd need to use the next and prev functions internally instead of node.next and node.prev. 2.) Someone needs to rework the currently commented out enum code. If someone can explain to me the general idea behind enums then maybe I can tackle this, but Brian is probably better suited. 3.) I'd like some comments on the drop and rev_drop functions. Do we need the remove function? Is drop a good name? etc.... 4.) Does everyone like the merge function? It serves a dual purpose: a.) O(1) node/list concatenation if used on two nodes from discrete lists b.) O(1) multi-node removal (creating two discrete lists from one) if used on two nodes in the same list. I can't decide if the dual nature of the merge function is an advantage or a liability. It makes it possible to apply nodes from two discrete lists by accident when you intended to apply nodes from the same list, thus introducing bugs. The problem is that there is no way to determine at compile time which list a given node is attached to, otherwise we could break this function into two functions: merge and cut 5.) Can anyone think of other useful functions? Thanks! -- Jesse Guardiani, Systems Administrator WingNET Internet Services, P.O. Box 2605 // Cleveland, TN 37320-2605 423-559-LINK (v) 423-559-5145 (f) http://www.wingnet.net |
From: Bardur A. <oca...@sc...> - 2004-08-29 16:11:25
|
On Sun, Aug 29, 2004 at 11:58:25AM -0400, Jesse D. Guardiani wrote: [--snip--] > Well, Brian, do you want it? I don't mind either way. > > I *would* like to discuss implementation details a bit before we commit > the code though. You can > download the source and view the current docs here for reference: > http://www.wingnet.net/~jesse/ocaml/dllist/ > > Things that I think warrant discussion: > > 1.) I probably need to write the following functions: > > rev_iter > rev_map > rev_to_list > rev_of_list > > Is everyone OK with so many rev_ functions? The > advantage is that they're identical to the normal > functions as far as performance is concerned, they just > work in the opposite direction. Can anyone think of a > better way to do it? Perhaps a boolean options argument? > i.e. ?(rev=false) This adds overhead to each function > though, as we'd need to use the next and prev functions > internally instead of node.next and node.prev. I think ?(direction=[`Forward | `Reverse]) looks slightly nicer, albeit more verbose... Anyway, I hardly think the overhead of unified traversal algorithms is going to kill anyone's performance. -- Bardur Arantsson <ba...@im...> <ba...@sc...> I only posted as Anonymous Coward because I knew I was going to be offtopic and rude. I got very scared, the name Coward seemed suitable. Anonymous Coward | http://slashdot.org |
From: Nicolas C. <war...@fr...> - 2004-08-29 16:15:05
|
> 1.) I probably need to write the following functions: > > rev_iter > rev_map > rev_to_list > rev_of_list That's exactly what enums are good for, you should provide only one : val rev_enum : 'a t -> 'a Enum.t and then everybody can apply iter, map, fold, to_list, to_array..... (all functional operations). Nicolas |
From: Jesse G. <je...@wi...> - 2004-08-30 13:40:39
|
Nicolas Cannasse wrote: >> 1.) I probably need to write the following functions: >> >> rev_iter >> rev_map >> rev_to_list >> rev_of_list > > That's exactly what enums are good for, you should provide only one : > > val rev_enum : 'a t -> 'a Enum.t > > and then everybody can apply iter, map, fold, to_list, to_array..... (all > functional operations). It's not as efficient as distinct special purpose functions, but it should prove to be just as scalable, right? O(1) rev_enum + O(N) Enum.iter Are there any major objections to this? -- Jesse Guardiani, Systems Administrator WingNET Internet Services, P.O. Box 2605 // Cleveland, TN 37320-2605 423-559-LINK (v) 423-559-5145 (f) http://www.wingnet.net |
From: skaller <sk...@us...> - 2004-08-29 16:53:05
|
On Mon, 2004-08-30 at 01:58, Jesse D. Guardiani wrote: > 1.) I probably need to write the following functions: > > rev_iter > rev_map > rev_to_list > rev_of_list > > Is everyone OK with so many rev_ functions? Yes. Don't use a flag. The distinction in direction with the rev_ functions is static as it should be. -- John Skaller, mailto:sk...@us... voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net |
From: Bardur A. <oca...@sc...> - 2004-08-29 18:40:19
|
On Sun, Aug 29, 2004 at 11:58:25AM -0400, Jesse D. Guardiani wrote: [--snip--]> > I *would* like to discuss implementation details a bit before we commit > the code though. You can > download the source and view the current docs here for reference: > http://www.wingnet.net/~jesse/ocaml/dllist/ > > Things that I think warrant discussion: [--snip--] > 3.) I'd like some comments on the drop and rev_drop functions. Do we > need the remove function? Is > drop a good name? etc.... Just a couple of tiny suggestions regarding naming: - "skip" might be a more appropriate name for "jump". - I'm not so crazy about the name "merge" since it's one of those quite overloaded terms... How about "splice" to distinguish it from a regular list merge (which is usually not the same as list concatenation)? -- Bardur Arantsson <ba...@im...> <ba...@sc...> - Baldrick, belive me, eternity in the company of Beelzebub, and all his helish instruments of death, would be a picnic compared with five minutes with me and this pencil. Edmund Blackadder | Blackadder III |
From: Jesse G. <je...@wi...> - 2004-08-30 13:31:54
|
Bardur Arantsson wrote: > On Sun, Aug 29, 2004 at 11:58:25AM -0400, Jesse D. Guardiani wrote: > > [--snip--]> >> I *would* like to discuss implementation details a bit before we commit >> the code though. You can >> download the source and view the current docs here for reference: >> http://www.wingnet.net/~jesse/ocaml/dllist/ >> >> Things that I think warrant discussion: > [--snip--] > >> 3.) I'd like some comments on the drop and rev_drop functions. Do we >> need the remove function? Is >> drop a good name? etc.... > > Just a couple of tiny suggestions regarding naming: > > - "skip" might be a more appropriate name for "jump". > > - I'm not so crazy about the name "merge" since it's one > of those quite overloaded terms... How about "splice" to > distinguish it from a regular list merge (which is usually > not the same as list concatenation)? So jump becomes skip and merge becomes splice. Is everyone in agreement here? -- Jesse Guardiani, Systems Administrator WingNET Internet Services, P.O. Box 2605 // Cleveland, TN 37320-2605 423-559-LINK (v) 423-559-5145 (f) http://www.wingnet.net |
From: Alan P. <ap...@re...> - 2004-08-27 03:04:52
|
In article <cglscs$q72$1...@se...>, Jesse Guardiani wrote: > > let length node = > let rec loop cnt n = > if n = node then > cnt > else > loop (cnt + 1) n.next > in > loop 1 node.next Should this be n == node ? |
From: Jesse G. <je...@wi...> - 2004-08-27 14:00:47
|
Alan Post wrote: > In article <cglscs$q72$1...@se...>, Jesse Guardiani wrote: >> >> let length node = >> let rec loop cnt n = >> if n = node then >> cnt >> else >> loop (cnt + 1) n.next >> in >> loop 1 node.next > > Should this be n == node ? Err, yes. I must have missread the purpose of the == operator. I'll change it. Thanks! -- Jesse Guardiani, Systems Administrator WingNET Internet Services, P.O. Box 2605 // Cleveland, TN 37320-2605 423-559-LINK (v) 423-559-5145 (f) http://www.wingnet.net |