From: Jesse G. <je...@wi...> - 2004-08-20 15:52:03
|
Hello, Would extlib be interested in a doubly linked list module (Author: Dustin Sallings, License: BSD)? http://bleu.west.spy.net/~dustin/projects/ocaml/doc/Linkedlist.html And perhaps an Ordered Hashtbl module (to be written, probably by me)? -- 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: Richard J. <ri...@an...> - 2004-08-20 16:00:59
|
I think this has been discussed before, but I'd like to see a structure which lets you build a normal list, element at a time, and then "freeze" it to create a real list. Normally to do this one has to build the list backwards and then call List.rev as the final step. This is unnecessarily inefficient. _However_, if one abuses Obj.magic, then it should be possible to keep a pointer to the last element of the list as one is building it up, then mutate the (normally immutable) last element to append to the list. This would obviously have to be hidden behind an abstract type for safety. Finally the "freeze" operation would return the actual list and cause the abstract type to be forgotten. Rich. -- Richard Jones. http://www.annexia.org/ http://www.j-london.com/ Merjis Ltd. http://www.merjis.com/ - improving website return on investment 'There is a joke about American engineers and French engineers. The American team brings a prototype to the French team. The French team's response is: "Well, it works fine in practice; but how will it hold up in theory?"' |
From: Brian H. <bh...@sp...> - 2004-08-20 16:23:26
|
On Fri, 20 Aug 2004, Richard Jones wrote: > I think this has been discussed before, but I'd like to see a > structure which lets you build a normal list, element at a time, and > then "freeze" it to create a real list. > > Normally to do this one has to build the list backwards and then call > List.rev as the final step. This is unnecessarily inefficient. > > _However_, if one abuses Obj.magic, then it should be possible to keep > a pointer to the last element of the list as one is building it up, > then mutate the (normally immutable) last element to append to the > list. This would obviously have to be hidden behind an abstract type > for safety. Finally the "freeze" operation would return the actual > list and cause the abstract type to be forgotten. > > Rich. > > If I understand you correctly, you're basically talking about taking the trick we use in the ExtLib List module and exporting it so that anyone can use it. I think this is a bad idea. The core reason I think it's a bad idea is that immutability is often an advantage. Being able to share the tails of lists can often create efficiencies that mutable lists can't provide. An example of this: I was playing with some code recently that was doing a breadth-first graph traversal, and I wanted to keep track of my path through the graph. So I simply kept a list of what nodes I had visited in a list. Whenever I followed an edge of the graph, I prepended the new node onto the list. I ended up with a large set of lists, most of which shared tailed. The ExtLib List module mutates lists, but it's careful to only mutate lists it knows no one else can see. The solution isn't to make lists semi-mutable, it's to think differently. Instead of looking for the solution with the mutating list, look for the solution with the immutable list. Note that having a different data structure which is a mutable doubly linked list is a completely different case. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |
From: Richard J. <ri...@an...> - 2004-08-20 23:36:03
|
On Fri, Aug 20, 2004 at 11:31:28AM -0500, Brian Hurt wrote: > If I understand you correctly, you're basically talking about taking the > trick we use in the ExtLib List module and exporting it so that anyone can > use it. I think this is a bad idea. [...] Perhaps ExtList already does this then? The interface for my list type would be something like: type 'a t val new_list : unit -> 'a t val append : 'a t -> 'a -> unit val append_list : 'a t -> 'a list -> unit val freeze : 'a t -> 'a list So you shouldn't be able to "see" the mutable list until it's frozen. Rich. -- Richard Jones. http://www.annexia.org/ http://www.j-london.com/ Merjis Ltd. http://www.merjis.com/ - improving website return on investment http://www.winwinsales.co.uk/ - CRM improvement consultancy |
From: Brian H. <bh...@sp...> - 2004-08-21 15:25:30
|
On Fri, 20 Aug 2004, Richard Jones wrote: > On Fri, Aug 20, 2004 at 11:31:28AM -0500, Brian Hurt wrote: > > If I understand you correctly, you're basically talking about taking the > > trick we use in the ExtLib List module and exporting it so that anyone can > > use it. I think this is a bad idea. > [...] > > Perhaps ExtList already does this then? Internally, yes- but it doesn't export the capability for anyone else to use it. > > The interface for my list type would be something like: > > type 'a t > > val new_list : unit -> 'a t > val append : 'a t -> 'a -> unit > val append_list : 'a t -> 'a list -> unit > val freeze : 'a t -> 'a list > > So you shouldn't be able to "see" the mutable list until it's frozen. Consider the following code: let res = let t = new_list () in append t 1; append t 2; append t 3; let s = freeze t in (* s is not [1;2;3] *) append t 4; s ;; What value does res get? [1;2;3], or [1;2;3;4]? If freeze copies the data out of the mutable list, it's not going to be any more efficient than reversing the list at the end of the algorithm. If it doesn't, you have the potential for modifying supposedly immutable lists. A third possibility I see, that might work, would be for freeze to empty out it's list. You would have code something like: (* We take the definition of 'a mut_list, inj, and dummy_node * from extList.ml *) type 'a t = { mutable head: 'a list; mutable tail: 'a mut_list; };; let newlist () = { head = []; tail = dummy_node; } let append mutlst elem = let newnode = { hd = elem; tl = [] } in match mutlst.head with | [] -> mutlst.head <- inj newnode; mutlst.tail <- newnode | _ -> mutlst.tail.tl <- inj newnode; mutlst.tail <- newnode ;; let freeze mutlst = let rval = mutlst.head in mutlst.head = []; mutlst.tail = dummy_node; rval ;; Note that freeze "empties out" the mutable list. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |
From: Nicolas C. <war...@fr...> - 2004-08-21 16:57:52
|
> Consider the following code: > let res = > let t = new_list () in > append t 1; > append t 2; > append t 3; > let s = freeze t in (* s is not [1;2;3] *) > append t 4; > s > ;; > > What value does res get? [1;2;3], or [1;2;3;4]? [1;2;3] according the implementation I proposed, that's the only way of correctly doing things. Returning the list using "freeze" empty the built list so it can be built again. Nicolas |
From: Brian H. <bh...@sp...> - 2004-08-21 17:02:24
|
On Sat, 21 Aug 2004, Nicolas Cannasse wrote: > > Consider the following code: > > let res = > > let t = new_list () in > > append t 1; > > append t 2; > > append t 3; > > let s = freeze t in (* s is not [1;2;3] *) > > append t 4; > > s > > ;; > > > > What value does res get? [1;2;3], or [1;2;3;4]? > > [1;2;3] according the implementation I proposed, that's the only way of > correctly doing things. > Returning the list using "freeze" empty the built list so it can be built > again. Ah. So, given the following code: let rval1, rval2 = let t = new_list () in append t 1; append t 2; append t 3; let s1 = freeze t in (* s1 is [1;2;3] *) append t 4; let s2 = freeze t in s1, s2 ;; Sets rval1 to [1;2;3] and rval2 to [4]. This is what the code snippet I just posted does. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |
From: Richard J. <ri...@an...> - 2004-08-21 17:06:08
|
On Sat, Aug 21, 2004 at 12:10:36PM -0500, Brian Hurt wrote: > Ah. So, given the following code: > > let rval1, rval2 = > let t = new_list () in > append t 1; > append t 2; > append t 3; > let s1 = freeze t in (* s1 is [1;2;3] *) > append t 4; > let s2 = freeze t in > s1, s2 > ;; > > Sets rval1 to [1;2;3] and rval2 to [4]. > > This is what the code snippet I just posted does. It's be nicer, perhaps, if the fourth "illegal" append statement could somehow generate an error. However, I think generating runtime errors is definitely the wrong thing to do, and at the same time I can't see how to structure the API to generate a compile time error ... Rich. -- Richard Jones. http://www.annexia.org/ http://www.j-london.com/ Merjis Ltd. http://www.merjis.com/ - improving website return on investment Learning Objective CAML for C, C++, Perl and Java programmers: http://www.merjis.com/richj/computers/ocaml/tutorial/ |
From: Nicolas C. <war...@fr...> - 2004-08-20 17:59:34
|
> I think this has been discussed before, but I'd like to see a > structure which lets you build a normal list, element at a time, and > then "freeze" it to create a real list. > > Normally to do this one has to build the list backwards and then call > List.rev as the final step. This is unnecessarily inefficient. > > _However_, if one abuses Obj.magic, then it should be possible to keep > a pointer to the last element of the list as one is building it up, > then mutate the (normally immutable) last element to append to the > list. This would obviously have to be hidden behind an abstract type > for safety. Finally the "freeze" operation would return the actual > list and cause the abstract type to be forgotten. > > Rich. Well somethink like that should work : type 'a mut_list = { elt : 'a; mutable next : 'a list; } external inj : 'a mut_list -> 'a list = "%identity" type 'a t = { mutable hd : 'a list; mutable tl : 'a mut_list; } let make() = let q = { elt = Obj.magic(); next = [] } in { hd = inj q; tl = q; } let add t x = let q = { elt = x; next = [] } in t.tl.next <- inj q; t.tl <- q let get t = let l = (match t.hd with [] -> assert false | _ :: l -> l) in let q = { elt = Obj.magic(); next = [] } in t.hd <- inj q; t.tl <- q; l However, I'm not sure it's efficient enough compared to a recursive building + rev, since OCaml allocation is so cheap. Play with it and test. Nicolas |
From: skaller <sk...@us...> - 2004-08-21 01:48:18
|
On Sat, 2004-08-21 at 04:00, Nicolas Cannasse wrote: > Well somethink like that should work : > > type 'a mut_list = { > elt : 'a; > mutable next : 'a list; > } > > external inj : 'a mut_list -> 'a list = "%identity" I'm really suspcious that this interface is unsound. Basically -- suppose you are half way through making a mut_list and you call 'inj' to cast it to an ordinary list .. and then you add some more elements to the end of the mut_list .. WOA your ordinary list got changed behind your back! It wasn't immutable at all!! So exposing the internals is dangerous -- you must obey the protocol that calling inj is final, and precludes further mutation -- in other words 'add' function is also 'magic' but it isn't spelled 'Obj.magic', its spelled 'ordinary safe ocaml function' which it isn't. Further -- what the heck happens if you call 'add' from two threads? I suspect Extlib's magical map implementation is sound -- but I'd have doubts about fold, since it reuses its own result which might be shared between threads. Once that sharing exists -- all bets are off at hiding the magic. [I can't think how this could occur off hand but I think it is good to be suspicious of magic :] -- 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: Nicolas C. <war...@fr...> - 2004-08-21 10:06:26
|
> > Well somethink like that should work : > > > > type 'a mut_list = { > > elt : 'a; > > mutable next : 'a list; > > } > > > > external inj : 'a mut_list -> 'a list = "%identity" > > I'm really suspcious that this interface is unsound. > Basically -- suppose you are half way through making > a mut_list and you call 'inj' to cast it to an ordinary > list .. and then you add some more elements to the > end of the mut_list .. WOA your ordinary list got > changed behind your back! It wasn't immutable at all!! This is sound since for the user 't' is abstract. The only way he can retreive the built list is through the "get" function that will reset the internal state of the type. This way the list returned to the user cannot be muted anymore. Please have a look at the implementation provided. Nicolas |
From: Dustin S. <du...@sp...> - 2004-08-20 16:39:43
|
On Aug 20, 2004, at 8:51, Jesse Guardiani wrote: > Would extlib be interested in a doubly linked list > module (Author: Dustin Sallings, License: BSD)? > http://bleu.west.spy.net/~dustin/projects/ocaml/doc/Linkedlist.html That one's really not very well done. It was enough for me to implement the LRU I needed. In particular, you can't create an empty one (IIRC). -- Dustin Sallings |
From: Brian H. <bh...@sp...> - 2004-08-20 16:58:25
|
On Fri, 20 Aug 2004, Dustin Sallings wrote: > > On Aug 20, 2004, at 8:51, Jesse Guardiani wrote: > > > Would extlib be interested in a doubly linked list > > module (Author: Dustin Sallings, License: BSD)? > > http://bleu.west.spy.net/~dustin/projects/ocaml/doc/Linkedlist.html > > That one's really not very well done. It was enough for me to > implement the LRU I needed. In particular, you can't create an empty > one (IIRC). I'm slapping together a quicky implementation that will solve that problem, have a more complete interface, and won't have licensing issues. Except something in a couple of hours. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |
From: Jesse G. <je...@wi...> - 2004-08-20 17:23:56
|
Brian Hurt wrote: > On Fri, 20 Aug 2004, Dustin Sallings wrote: > >> >> On Aug 20, 2004, at 8:51, Jesse Guardiani wrote: >> >> > Would extlib be interested in a doubly linked list >> > module (Author: Dustin Sallings, License: BSD)? >> > http://bleu.west.spy.net/~dustin/projects/ocaml/doc/Linkedlist.html >> >> That one's really not very well done. It was enough for me to >> implement the LRU I needed. In particular, you can't create an empty >> one (IIRC). > > I'm slapping together a quicky implementation that will solve that > problem, have a more complete interface, and won't have licensing issues. > Except something in a couple of hours. Do you want me to slap together an OrdHashtbl module? Or do you want to finish it off yourself based on the work you posted to the beginners list earlier today? I'm headed to lunch right now, but I plan to complete your work once I get back in an hour or so if you haven't claimed it by then. However, I realize I'm probably the worst OCaml programmer here, so I understand if you'd prefer to tackle it yourself. -- 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: Brian H. <bh...@sp...> - 2004-08-20 18:09:01
|
On Fri, 20 Aug 2004, Jesse Guardiani wrote: > Do you want me to slap together an OrdHashtbl module? Or do you want to > finish it off yourself based on the work you posted to the beginners list > earlier today? IMHO, the ordered hashtable idea is too specialized for inclusion in the standard library. Generally, depending upon what order internally a hashtable stores it's entries is a bad idea. I have everything except the enum and of_enum functions written. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |
From: Jesse G. <je...@wi...> - 2004-08-20 18:50:27
|
Brian Hurt wrote: > On Fri, 20 Aug 2004, Jesse Guardiani wrote: > >> Do you want me to slap together an OrdHashtbl module? Or do you want to >> finish it off yourself based on the work you posted to the beginners list >> earlier today? > > IMHO, the ordered hashtable idea is too specialized for inclusion in the > standard library. Generally, depending upon what order internally a > hashtable stores it's entries is a bad idea. Why is it a bad idea? I need to create a Hashtbl based on a file. I'd like to be able to write the file back out to disk in the same order I read it in. What's wrong with that? I'm sure there are other applications as well. I'm perfectly fine with it not being included in extlib, but I still think it needs to be written. -- 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: Nicolas C. <war...@fr...> - 2004-08-20 19:27:59
|
> >> Do you want me to slap together an OrdHashtbl module? Or do you want to > >> finish it off yourself based on the work you posted to the beginners list > >> earlier today? > > > > IMHO, the ordered hashtable idea is too specialized for inclusion in the > > standard library. Generally, depending upon what order internally a > > hashtable stores it's entries is a bad idea. > > Why is it a bad idea? > > I need to create a Hashtbl based on a file. I'd like to be able to write > the file back out to disk in the same order I read it in. What's wrong > with that? I'm sure there are other applications as well. What you need then is not an ordered Hashtbl since your keys will not keep your file ordered. If I were you I would store the pair (keys,values) in an DynArray and build an Hashtbl so I can retreive the index of the value in the array using only the key. Only a list or an array can keep correctly the order you want. Nicolas |
From: Dustin S. <du...@sp...> - 2004-08-20 19:38:19
|
On Aug 20, 2004, at 12:28, Nicolas Cannasse wrote: > What you need then is not an ordered Hashtbl since your keys will not > keep > your file ordered. > If I were you I would store the pair (keys,values) in an DynArray and > build > an Hashtbl so I can retreive the index of the value in the array using > only > the key. Only a list or an array can keep correctly the order you want. Right. Or in java, you'd just use LinkedHashMap, which is both a hash table and a linked list at the same time. -- Dustin Sallings |
From: Brian H. <bh...@sp...> - 2004-08-20 19:49:33
|
On Fri, 20 Aug 2004, Dustin Sallings wrote: > > On Aug 20, 2004, at 12:28, Nicolas Cannasse wrote: > > > What you need then is not an ordered Hashtbl since your keys will not > > keep > > your file ordered. > > If I were you I would store the pair (keys,values) in an DynArray and > > build > > an Hashtbl so I can retreive the index of the value in the array using > > only > > the key. Only a list or an array can keep correctly the order you want. > > Right. Or in java, you'd just use LinkedHashMap, which is both a hash > table and a linked list at the same time. It's a combination data structure- linkled list + hash table. The hash table doesn't keep stuff in order, the linked list does. I'm starting to wonder if my priority search queue code doesn't have a market after all. As it's playing in the same sort of space, but has the advantage of being applicative. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |
From: Dustin S. <du...@sp...> - 2004-08-20 19:55:57
|
On Aug 20, 2004, at 12:57, Brian Hurt wrote: > It's a combination data structure- linkled list + hash table. The hash > table doesn't keep stuff in order, the linked list does. Oh, I understand what it does. The point is that there are now two problems that have come up on the list that this type of structure helps solve: The key/value pair type file that you want to open up, access, and write back out in the same order. LRU caches where you want both O(1) access and inserts as well as O(1) aging removal of the LRU item. > I'm starting to wonder if my priority search queue code doesn't have a > market after all. As it's playing in the same sort of space, but has > the > advantage of being applicative. That sounds interesting. So I take it you'd insert any new item as the highest priority, and then a subsequent item as an even higher priority? (Thinking of LRU again). -- Dustin Sallings |
From: Jesse G. <je...@wi...> - 2004-08-20 20:08:46
|
Nicolas Cannasse wrote: >> >> Do you want me to slap together an OrdHashtbl module? Or do you want >> >> to finish it off yourself based on the work you posted to the >> >> beginners > list >> >> earlier today? >> > >> > IMHO, the ordered hashtable idea is too specialized for inclusion in >> > the >> > standard library. Generally, depending upon what order internally a >> > hashtable stores it's entries is a bad idea. >> >> Why is it a bad idea? >> >> I need to create a Hashtbl based on a file. I'd like to be able to write >> the file back out to disk in the same order I read it in. What's wrong >> with that? I'm sure there are other applications as well. > > What you need then is not an ordered Hashtbl since your keys will not keep > your file ordered. > If I were you I would store the pair (keys,values) in an DynArray and > build an Hashtbl so I can retreive the index of the value in the array > using only the key. Only a list or an array can keep correctly the order > you want. I get it now. :) I made up the term 'ordered hashtbl' to describe the data structure I needed without knowing if the name I made up was already widely used to describe something else. Apparently something like that has already been branded in people's minds that does something similar to what I need, but not exactly identical. When I say "ordered hashtbl", I mean a hashtbl where the iter function iterates over the elements in exactly the order in which they were inserted. The data structure I need has nothing to do with ordering the keys. I guess LinkedHashtbl is the correct name then? Anyway, I think a LinkedHashtbl would be a nice addition to extlib, but if nobody agrees then I guess I'll just package my own module. -- 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: Richard J. <ri...@an...> - 2004-08-21 09:04:32
|
Could use an assoc-list, no? Rich. -- Richard Jones. http://www.annexia.org/ http://www.j-london.com/ Merjis Ltd. http://www.merjis.com/ - improving website return on investment Perl4Caml lets you use any Perl library in your type-safe Objective CAML programs. http://www.merjis.com/developers/perl4caml/ |
From: Jesse G. <je...@wi...> - 2004-08-21 17:29:09
|
Richard Jones wrote: > Could use an assoc-list, no? But would it be as efficient as a linked hashtbl for random access? -- 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: Richard J. <ri...@an...> - 2004-08-21 17:32:39
|
On Sat, Aug 21, 2004 at 01:28:49PM -0400, Jesse Guardiani wrote: > Richard Jones wrote: > > > Could use an assoc-list, no? > > But would it be as efficient as a linked hashtbl for random access? Depends how big the dataset is likely to be. If it's sufficiently small (say, order of 10-50 elements), then the assoc-list will probably be the most efficient way to do it. Rich. -- Richard Jones. http://www.annexia.org/ http://www.j-london.com/ Merjis Ltd. http://www.merjis.com/ - improving website return on investment http://www.YouUnlimited.co.uk/ - management courses |
From: Jesse G. <je...@wi...> - 2004-08-21 17:44:45
|
Richard Jones wrote: > On Sat, Aug 21, 2004 at 01:28:49PM -0400, Jesse Guardiani wrote: >> Richard Jones wrote: >> >> > Could use an assoc-list, no? >> >> But would it be as efficient as a linked hashtbl for random access? > > Depends how big the dataset is likely to be. If it's sufficiently > small (say, order of 10-50 elements), then the assoc-list will > probably be the most efficient way to do it. Exactly, but I expect somewhere between 500 and 1000 elements or more in this particular case. BTW, just in case you didn't catch my announcement of the beginners list (where this whole discussion started), I've drafted a Linked Hashtbl. You can view the code here under the docs section: http://www.wingnet.net/~jesse/ocaml/linkedhashtbl/index.html It's untested as I'm currently using Dustin Sallings Linkedlist module that doesn't allow empty lists, and I'm waiting for a solidified interface to Brian Hurt's dllist before I switch. But the interface is fairly complete (just need to add ExtHashtbl like functions), and it compiles. -- 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 |