ocaml-lib-devel

 [Ocaml-lib-devel] New module: fifo From: Brian Hurt - 2004-07-21 19:07:02 Attachments: fifo.mli fifo.ml ```Attached is some code to implement a FIFO queue- appending elements, prepending elements, and removing elements from the head of queue are all O(1) (amoritized) operations. The structures is purely applicative, however (unlike the Queue standard library). The trick is that I do lazy appending. I keep two lists- one the front of the queue, which is in order. The other is the back of the queue, which is reversed. Appending an element to the queue is then just prepending said element to the back of the queue. When I remove the last element of the front of the queue list, I reverse the back of the queue list and it becomes my new front (my new back is then emptied). So as every element passes through the queue, it is touched at most three times- once when it is prepended to the back of the queue, once when it is moved from the back list to the front list, and once when it is removed from the front list. The core code looks like this: type 'a t = ('a list) * ('a list) let add x = function | [], [] -> [x], [] | [], _ -> assert false | q, w -> q, (x :: w) let pop = function | [], [] -> raise Empty | [], _ -> assert false | (h :: []), w -> h, ((List.rev w), []) | (h :: t), w -> h, (t, w) The only other iteresting thing of note is iter_fast, fold_fast, and map_fast. The question is: how important is the ordering in the comprehensions? I can make a very fast fold if I can screw up the ordering: let fold f init (q, w) -> List.fold_left f (List.fold_left f init q) w However, the back half of the queue is traversed in reverse order. For a lot of applications, this isn't a problem. The alternative is to reverse the back half before feeding it to fold: let fold f init (q, w) -> List.fold_left f (List.fold_left f init q) (List.rev w) But this takes an extra O(N) memory to hold the reverse of the list. My basic theory here is that people may be switching code over from the Queue library to my new Fifo library and forget (or not know) they depend upon ordering. New code being written to use Fifo should know, and can choose. So I went with correctness over speed as the default. The default behavior is to traverse in order, even if that means using more memory, but the functions have _fast versions which violate the order assumptions for less memory utilizations. Opinions on wether this is the right thing to do or not are welcome. Another possibility- declare the base function to be unordered, and then provide _left and _right (because it's a horse apeice to go backwards as it is forwards) versions with defined ordering. What do people think is the best way to handle this? -- "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 ```
 [Ocaml-lib-devel] New module: fifo From: Falk Hueffner - 2004-07-24 22:01:53 ```Hi, I think this would be a nice addition, I was looking for something like this just a few days ago. However, this is really a deque and should be called so. I'm wondering why the "add" function takes the new element first and the 't second. It seemed to me to be some kind of convention that functions in modules implementing some abstract data type 't the 't is always the first argument. This is ususally also the most useful for currying. I know it is similar in the standard Queue, but it already irritated me there :-) I'd also get rid of the synonyms, there's not much point for them in new code. As for the iterating functions, I'd prefer default ordering to be unspecified and provide additional _left and _right functions. About the implementation, are you sure there is no weird sequence of operations that would have O(n) complexity because of frequent reversing? I've not looked closely, though... -- Falk ```
 Re: [Ocaml-lib-devel] New module: fifo From: Richard Jones - 2004-07-24 22:45:59 ```On Sun, Jul 25, 2004 at 12:01:31AM +0200, Falk Hueffner wrote: > About the implementation, are you sure there is no weird sequence of > operations that would have O(n) complexity because of frequent > reversing? I've not looked closely, though... Yes, I think there is. One of the two books I just read, either "ML for the working programmer" or the Oosaki book mentioned this. I don't have them to hand right now, but can look them up later if you want. Rich. -- Richard Jones. http://www.annexia.org/ http://www.j-london.com/ Merjis Ltd. http://www.merjis.com/ - improving website return on investment "One serious obstacle to the adoption of good programming languages is the notion that everything has to be sacrificed for speed. In computer languages as in life, speed kills." -- Mike Vanier ```
 Re: [Ocaml-lib-devel] New module: fifo From: Diego Olivier Fernandez Pons - 2004-07-26 07:10:34 ``` Bonjour, Richard Jones wrote : > Yes, I think there is. One of the two books I just read, either "ML > for the working programmer" or the Oosaki book mentioned this. I > don't have them to hand right now, but can look them up later if you > want. I don't have Paulson's book (ML for the working programmer) at hand but what is sure is that this subject is deeply discussed in Okasaki's book. Actually, it is the subject of Okasaki's thesis on which the book is based. http://www.cs.cmu.edu/afs/cs.cmu.edu/project/fox/mosaic/papers/cokasaki-thesis.ps The book provides working SML code (also some code on Okasaki's home pages) for strict/lazy purely functional deques. It has been ported to Caml by Markus Mottl and included in many Caml data structures libraries. Brian Hurt wrote : > 2) Because it never needs to reverse a list, the imperitive version > may be marginally faster than my version. I haven't measured this, > so your mileage may vary. In my branch-and-bound code using LDS (limited discrepancy search), the functional version (two lists with inversion expanded in the code) was faster than the imperative one. I really don't know why. Diego Olivier ```
 Re: [Ocaml-lib-devel] New module: fifo From: Brian Hurt - 2004-07-25 00:41:19 ```On Sun, 25 Jul 2004, Falk Hueffner wrote: > Hi, > > I think this would be a nice addition, I was looking for something > like this just a few days ago. However, this is really a deque and > should be called so. I don't mind the name change. For the rest of this message I'll just assume it happened. > > I'm wondering why the "add" function takes the new element first and > the 't second. It seemed to me to be some kind of convention that > functions in modules implementing some abstract data type 't the 't is > always the first argument. This is ususally also the most useful for > currying. I know it is similar in the standard Queue, but it already > irritated me there :-) I'd also get rid of the synonyms, there's not > much point for them in new code. The signature for Queue.add is: val add : 'a -> 'a t -> unit As I was sort of trying for a Queue replacement, I kept the order of the arguments the same (obviously, the unit got turned into a 'a t). Also, I'm not sure about which is more usefull for partial function application. Not that applying a value, the add function can become 'a -> 'a, a more usefull signature than 'a -> 'a Deque.t. Of course, how often are you going to be adding the same element to an entire set of Deques? I don't really have strong opinions one way or the other. I was just following Queue. > About the implementation, are you sure there is no weird sequence of > operations that would have O(n) complexity because of frequent > reversing? I've not looked closely, though... If you used the immutability to "back up", you could repeatedly remove the same element. If that element was the one that hit the O(N) complexity step of reversing the list, you could hit a problem. The following code demonstrates how this might work: let myqueue = (* make a queue of 1001 ints *) let rec loop idx q = let q = Deque.add idx q in if (idx < 1000) then loop (idx+1) q else q in loop 0 (Deque.empty) ;; let expensive () = let rec loop idx q = (* Remove an element from the Deque- this is always an O(N) operation! *) let q' = Deque.remove q in if (idx < max_int) then (* Note that by passing in q and not q' we "undo" the Deque.remove! *) loop (idx+1) q else () in loop 0 myqueue ;; We're basically using the immutability to "replay" the same O(N) removal over and over. Now, this is valid code, but I don't think it's reasonable code, if you see the difference. Perhaps documenting this behavior is called for (maybe), but I don't think it's worthwhile trying to avoid it. For this behavior to be signifigant, you'd need all of the following things to be true: 1) You'd have to be using immutability to force replays of the same removal (or small number of removals) over and over. 2) You'd need a large number of items in the queue (reversing a list of 3 items isn't that expensive). 3) You'd need to be replaying the same removal many times (reversing even a long list once or twice unnecessarily isn't that painfull) 4) The removal you are replaying needs to be the O(N) one. If any of these factors aren't the case, it's not a problem. And I'd argue that all of them are exceptional- that in the common case, replays are rare to non-existant, the queue only holds a small number of items at any given time, that in the case where replays do happen, they happen to a "safe" (O(1)) removal, and that only a finite number of replays (1-2) will happen. There are tricks to speed up the rare case. Basically you keep the first O(log N) and last O(log N) elements in lists, and the rest of the elements in a tree. You can then lazily add and remove O(log N) elements at a shot from the tree (which you can finesse to only take O(log N) time to handle all O(log N) elements), meaning that instead of O(N) worst case cost, it's O(log N). However, this approach signifigantly slows down the common case. Are we willing to slow down the common case to speed up the exceedingly rare 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 ```
 Re: [Ocaml-lib-devel] New module: fifo From: skaller - 2004-07-25 03:57:36 ```On Sun, 2004-07-25 at 10:48, Brian Hurt wrote: > We're basically using the immutability to "replay" the same O(N) removal > over and over. >Are we willing to slow down the common case to speed up the exceedingly > rare case? Is it so rare? Consider backtracking parser for say, C++, and a token generator 'tokenise a line' which feeds a Deque, so the parser can just 'get next token' by 'if Deque empty, run generator: now fetch next token'. Now, the backtrack point for C++ is almost always going to be at the start of a line, since most programmers write each statement on a new line most of the time ... So we're certain in certain states, to go thru the list of possible grammar productions, backtracking after each one that fails, and each time we backtrack have to reload the Deque with a new line of tokens in reverse order .. and then reverse them. That this situation arises is no accident -- it isn't random bad luck. It occurs by design, because it happens that the simplest lexer lines up with the critical point of the backtracking mechanism, most of the time, because you decided to do the obvious thing tokenising a line .. precisely because you're a programmer that writes each declaration on new line. The differencer is that the human reader buffers the line in their head, and when rescanning, uses the same mental buffer, but by a quirk the technical design is one token out of phase .. and regenerates the line of tokens every time we rescan a line in the parser. [I can easily prove it mentally -- you just try to read the *correct* and logical layout of C code in which the ';' is written at the beginning of the line where it logically should be -- ; int i = 1 ; long j = expr if you find yourself mentally doing 'double takes' then you've just hit the mental equivalent of this problem] Clearly, you can fix the problem by tokenising a new line whenever the Deque empties instead of when you need the first token on the line -- but that may be hard to organise in a purely functional parser. Anyhow .. my argument is that it isn't always going to be 'ramdom bad luck', and that is the condition required to ensure that the 'amortised' performance is the actual performance. BUT -- back to your question: >Are we willing to slow down the common case to speed up > the exceedingly rare case? This is the WRONG question anyhow. The question is: is the dual list data structure a nice data structure?? The answer is YES! Don't complicate it. It may be the wrong data structure to use for a particular application, but so what is new? As it happens, re-reversing the list is going to happen more often than you think precisely because you're *going* to use the persistence property of the data structure -- there'd be no point chosing a functional data structure if you didn't :) -- John Skaller, mailto:skaller@... voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net ```
 Re: [Ocaml-lib-devel] New module: fifo From: skaller - 2004-07-25 04:18:18 ```On Sun, 2004-07-25 at 13:57, skaller wrote: > On Sun, 2004-07-25 at 10:48, Brian Hurt wrote: > > >Are we willing to slow down the common case to speed up > > the exceedingly rare case? > > This is the WRONG question anyhow. > > The question is: is the dual list data structure a nice > data structure?? > > The answer is YES! One more point. How about encoding the data structure without full abstraction? Expose the implementation read-only to enable pattern matching on the lists using the new 'private' keyword? Did you realise this data structure isn't just a deque? It has at least one other significant use: a purely functional bidirectional stream editor. Just change 'List.reverse' to 'move one element'. Now you have two lists of characters representing an edit buffer, the cursor sits between the lists. I invented the modern PC text editor many years ago, a mutble version of this design was used, called a 'split buffer'. Borland copied (or reinvented) the design some year later. A purely functional version is very exciting -- it makes the 'undo' function very simple :) -- John Skaller, mailto:skaller@... voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net ```
 Re: [Ocaml-lib-devel] New module: fifo From: Brian Hurt - 2004-07-25 16:41:33 ```On 25 Jul 2004, skaller wrote: > One more point. How about encoding the data structure > without full abstraction? Expose the implementation > read-only to enable pattern matching on the lists > using the new 'private' keyword? The problem with this is that if we did change the implementation (say to having a tree-based middle), this would break everyone using the library. Another thing to remember is that the internal data state can be complicated. Imagine an int deque with three elements- 1, 2, and 3 (in that order). The internal representation could be any of: ([1;2;3], []) ([1;2], [3]) ([1], [3; 2]) The representation: ([], [3;2;1]) isn't allowed in the current implementation, but Ocaml can't prove this. An alternative possibility would be to provide a peek_n and remove_n functions, which would remove up to n elements in one operation, returning the elements in a list. > > Did you realise this data structure isn't just a deque? > It has at least one other significant use: a purely > functional bidirectional stream editor. Um, the data structure you're thinking of here is subtly different. I'm making the radical ends of the list- the front and back- accessible, at the cost of making the middle of the list inaccessible. You want to make the middle of the list accessible at the cost of making the ends inaccessible. With my code, moving one element from the back list to the front list would remove the last element of the back list and append it to the front list. So if you had an int queue with the elements [1;2;3;4;5;6] (in that order, so '1' is the head of the queue), and the break point was in the middle, I would be storing the list as: ([1;2;3], [6;5;4]) Moving one element would be moving the 4- which would require the duplication of *both* arrays. What you want for your stream editor is the other way around- the front list is reversed and the back list is forwards, like: ([3;2;1], [4;5;6]) Now, moving the element 4 from the "future" list to the "past" list is an O(1) operation. Do you see the difference? Yours is an interesting data structure too, just a very different use. -- "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 ```
 Re: [Ocaml-lib-devel] New module: fifo From: skaller - 2004-07-25 20:39:43 ```On Mon, 2004-07-26 at 02:49, Brian Hurt wrote: > On 25 Jul 2004, skaller wrote: > > > One more point. How about encoding the data structure > > without full abstraction? Expose the implementation > > read-only to enable pattern matching on the lists > > using the new 'private' keyword? > > The problem with this is that if we did change the implementation (say to > having a tree-based middle), this would break everyone using the library. Ok, so do both! Provide the basic double list with operations, and them use it with a functor to build the Deque. > > Did you realise this data structure isn't just a deque? > > It has at least one other significant use: a purely > > functional bidirectional stream editor. > > Um, the data structure you're thinking of here is subtly different. > Do you see the difference? Yeah: both use double lists, but you have different operations. -- John Skaller, mailto:skaller@... voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net ```
 Re: [Ocaml-lib-devel] New module: fifo From: Diego Olivier Fernandez Pons - 2004-07-26 07:32:51 ``` Bonjour, > > Did you realise this data structure isn't just a deque? It has at > > least one other significant use: a purely functional bidirectional > > stream editor. This is called a Zipper and was invented by Gerard Huet. It works for all pointer based purely functional data structures (trees, lists, ...). http://www.nist.gov/dads/HTML/zipper.html Diego Olivier ```
 Re: [Ocaml-lib-devel] New module: fifo From: skaller - 2004-07-26 18:32:03 ```On Mon, 2004-07-26 at 17:31, Diego Olivier Fernandez Pons wrote: > Bonjour, >=20 > > > Did you realise this data structure isn't just a deque? It has at > > > least one other significant use: a purely functional bidirectional > > > stream editor. >=20 > This is called a Zipper and was invented by Gerard Huet. It works for > all pointer based purely functional data structures (trees, lists, > ...). >=20 > http://www.nist.gov/dads/HTML/zipper.html "G=C3=A9rard Huet, The Zipper, Journal of Functional Programming, 7(5):549-554, 1997." My version wasn't functional, nor generalised, but the design predates that paper by almost 20 years :) --=20 John Skaller, mailto:skaller@... voice: 061-2-9660-0850,=20 snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net ```
 Re: [Ocaml-lib-devel] New module: fifo From: Nicolas Cannasse - 2004-07-26 19:13:41 ```> Bonjour, > > > > Did you realise this data structure isn't just a deque? It has at > > > least one other significant use: a purely functional bidirectional > > > stream editor. > > This is called a Zipper and was invented by Gerard Huet. It works for > all pointer based purely functional data structures (trees, lists, > ...). > > http://www.nist.gov/dads/HTML/zipper.html > > Diego Olivier I didn't got time to study zippers but I heard they have interesting properties. Maybe interesting for ExtLib ? Regards, Nicolas Cannasse ```
 Re: [Ocaml-lib-devel] New module: fifo From: Diego Olivier Fernandez Pons - 2004-07-27 07:04:49 ``` Bonjour, > I didn't got time to study zippers but I heard they have interesting > properties. Maybe interesting for ExtLib ? They have enough interesting properties to be used in several medium to large sized codes. I gave the following examples in the cited message and they may be more : - Zen (G=E9rard Huet, Caml) uses zippers to handle acyclic automata minimization - SML/NJ Standard library (John Reppy) uses zippers to handle deletion in red-black trees - MetaPRL (Caml) uses zippers to handle insertion and deletion in splay and red-black trees - Grammatical Framework (Aarne Ranta, Haskell) uses zippers to navigate through n-ary trees. Diego Olivier ```
 Re: [Ocaml-lib-devel] New module: fifo From: Brian Hurt - 2004-07-25 15:57:50 ```On 25 Jul 2004, skaller wrote: > Is it so rare? Consider backtracking parser for say, C++, I'd come up with more or less the same example. Note that there are two ways to push back tokens. One is to 'undo' the remove operations by going back to an older version of the data structure. The other way is to just use the prepend operation to push the previously popped elements back onto the front of the queue- this operation is O(1) strict. We could make this faster by offering a "concat" operation, which concatenates two queues into one: val concat: 'a t -> 'a t -> 'a t let concat (afront, aback) (bfront, bback) = (List.append afront (List.rev_append aback bfront)), bback Given this operation, you could "cache" the tokens you pull out of the main queue into a temporary queue. Then, instead of replaying the remove, you just mass-prepend the temporary queue. This sidesteps the O(N) problem. Also, in this case several other constraints don't apply. You're not going to have a lot of tokens on a single line, so N is going to be small. You generally don't back up and reparse the line repeatedly- once, maybe twice, yeah, but not 18 gazillion times. > The question is: is the dual list data structure a nice > data structure?? You're right. I like this question better. -- "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 ```
 [Ocaml-lib-devel] Functional vr.s Imperitive Data Structures, was Re: New module: fifo From: Brian Hurt - 2004-07-25 16:18:31 ```On a completely different topic: On 25 Jul 2004, skaller wrote: > As it happens, re-reversing the list is going to happen > more often than you think precisely because you're > *going* to use the persistence property of the data > structure -- there'd be no point chosing a functional > data structure if you didn't :) > The main attraction applicative data structures have to me is correctness, in that they reduce coupling. I've been bitten way too often by subroutines suddenly starting to modify data structures (or stopping modifying data structures- in many ways that's worse) you've passed in to them. No changes can be made to the data structures I depend upon with my approval. This is one of the reasons I would prefer applicative semantics for enums over the current imperitive semantics. I value correctness over performance. -- "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 ```
 Re: [Ocaml-lib-devel] Functional vr.s Imperitive Data Structures, was Re: New module: fifo From: skaller - 2004-07-25 20:18:52 ```On Mon, 2004-07-26 at 02:26, Brian Hurt wrote: > On a completely different topic: > > On 25 Jul 2004, skaller wrote: > > > As it happens, re-reversing the list is going to happen > > more often than you think precisely because you're > > *going* to use the persistence property of the data > > structure -- there'd be no point chosing a functional > > data structure if you didn't :) > > > > The main attraction applicative data structures have to me is correctness, > in that they reduce coupling. Ah, my turn to backstep and agree. You're right. > This is one of the reasons I would prefer applicative semantics for enums > over the current imperitive semantics. I value correctness over > performance. Wrong answers are bad .. but ones you can't compute are just as bad :) There is a balance. When you say 'correctness' you don't mean 'the program is correct'. What you *actually* mean by correctness is 'I know the program is correct*. That is: you value the ability to reason about the value of the result. And that ability to reason also applies to performance -- you want to be able to reason the program is efficient as well, because if it isn't, it won't actually produce a correct answer. -- John Skaller, mailto:skaller@... voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net ```
 Re: [Ocaml-lib-devel] New module: fifo From: Falk Hueffner - 2004-07-25 16:53:12 ```Brian Hurt writes: > Are we willing to slow down the common case to speed up the > exceedingly rare case? This is an interesting question; in my opinion, for a library that strives to set something like a standard: Yes. Absolutely. Because: 1. Experience has taught us that usage patterns that seem weird occur more often than we think. 2. Worst cases which have much worse run times (e. g., O(log n) -> O(n)) can be used for denial of service attacks. 3. If you're really desperate for performance, you're going to implement your own data structure for your special case anyway. However, in most cases, it doesn't really matter that much. -- Falk ```
 Re: [Ocaml-lib-devel] New module: fifo From: Brian Hurt - 2004-07-25 17:49:37 ```On Sun, 25 Jul 2004, Falk Hueffner wrote: > Brian Hurt writes: > > > Are we willing to slow down the common case to speed up the > > exceedingly rare case? > > This is an interesting question; in my opinion, for a library that > strives to set something like a standard: Yes. Absolutely. Because: > > 1. Experience has taught us that usage patterns that seem weird occur > more often than we think. > 2. Worst cases which have much worse run times (e. g., O(log n) -> > O(n)) can be used for denial of service attacks. Note that hash tables and quick sorts have the same problem- "degenerate" cases where performance degrades signfigantly. The question should have been "how valid is this usage pattern"? Lists have the same problem- if my algorithm depends upon successively appending elements onto a list, I'm going to be hurting. The question is especially relevent because there is an alternative usage of the data structure which avoids the problem- unget the elements. -- "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 ```
 [Ocaml-lib-devel] Re: New module: fifo From: Alan Post - 2004-07-25 06:40:51 ```In article <87hdrxm5dw.fsf@...>, Falk Hueffner wrote: > > However, this is really a deque and should be called so. My impression is that the commonly accepted definition of "fifo" is a "queue": a black box where things go in, then come out the same order. I think "fifo" is a fine name that makes it clear that the queue is not any kind of fancy "priority queue" or what not, but simply a regular queue. According to wikipedia (which we know to be divinely inspired, and thus infallible), a deque is defined to support pushing or popping at either end of the queue. Hence, "double-ended queue" -> "deque". http://en.wikipedia.org/wiki/Deque And note that implementing an efficient side-effect free deque is a much more complex problem. Hooray for bike sheds. ```
 [Ocaml-lib-devel] Re: New module: fifo From: Alan Post - 2004-07-21 19:59:03 ```In article , Brian Hurt wrote: > > Attached is some code to implement a FIFO queue- appending elements, > prepending elements, and removing elements from the head of queue are all > O(1) (amoritized) operations. The structures is purely applicative, > however (unlike the Queue standard library). You may also be interested in James Woodyatt's deque implementation: http://www.wetware.com/jhw/src/pagoda/doc/Cf_deque.html ```
 Re: [Ocaml-lib-devel] New module: fifo From: Nicolas Cannasse - 2004-07-23 20:57:54 ```> Attached is some code to implement a FIFO queue- appending elements, > prepending elements, and removing elements from the head of queue are all > O(1) (amoritized) operations. The structures is purely applicative, > however (unlike the Queue standard library). > > The trick is that I do lazy appending. I keep two lists- one the front of [...] This looks nice ! > My basic theory here is that people may be switching code over from the > Queue library to my new Fifo library and forget (or not know) they depend > upon ordering. New code being written to use Fifo should know, and can > choose. So I went with correctness over speed as the default. The > default behavior is to traverse in order, even if that means using more > memory, but the functions have _fast versions which violate the order > assumptions for less memory utilizations. I agree with this choice. Having the "commonly excepted" behavior by default is good common sense. Now comes the topic of adding applicate FIFO to ExtLib. I'm not against, I think FIFO are generaly useful enough, but I'm a bit concerned about why the OCaml team - defenders of the applicative style among alls - choose to implement it as a mutable data structure in the stdlib. Any insights ? Regards, Nicolas Cannasse ```
 Re: [Ocaml-lib-devel] New module: fifo From: Brian Hurt - 2004-07-23 21:16:36 ```On Fri, 23 Jul 2004, Nicolas Cannasse wrote: > I'm not against, I think FIFO are generaly useful enough, but I'm a bit > concerned about why the OCaml team - defenders of the applicative style > among alls - choose to implement it as a mutable data structure in the > stdlib. Any insights ? I have no special insight into why the core team's thoughts. I have some possibilities, however: 1) The standard Queue lib is based on top of a imperitive linked list. This makes it O(1) worst case. My implementation is only O(1) ammoritized, i.e. "on average". Imagine the following scenario: 1000 elements are added to an empty queue, creating a 1 element "front" list and a 999 element "back" list. Then two elements are removed. The second element has the cost of reversing a 999 element list. Note that you can the remove another 998 elements without a list operation- but that operation is expensive. 2) Because it never needs to reverse a list, the imperitive version may be marginally faster than my version. I haven't measured this, so your mileage may vary. 3) Most likely IMHO- it's an example of an imperitive data structure other than arrays and strings. Number three brings up an interesting point. I learned a lot of Ocaml reading the source to the List module. I'd shudder to think of somebody doing that with ExtLib's List module. To what extent does a standard library need to be a demonstration of the language? My opinion, if it hasn't been stated explicitly yet, is almost not at all. But other people may have other opinions. -- "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 ```
 Re: [Ocaml-lib-devel] New module: fifo From: skaller - 2004-07-23 22:23:07 ```On Sat, 2004-07-24 at 07:24, Brian Hurt wrote: > To what extent does a standard > library need to be a demonstration of the language? My opinion, if it > hasn't been stated explicitly yet, is almost not at all. A 'standard' library implementation not only doesn't have to demonstrate good coding style, it often cannot be implemented in the language. In ISO Standards terms, a programming language's 'standard' library is NOT a library, but rather a part of the language itself which can be *described* partly in terms of the core language. Even if the library is implemented in the core language, it can and usually does contain all sorts of quirks related to the known performance properties of the compiler it is designed for. OTOH the *interface* should be beautiful -- John Skaller, mailto:skaller@... voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net ```
 Re: [Ocaml-lib-devel] New module: fifo From: Nicolas Cannasse - 2004-07-24 08:26:39 ```> > To what extent does a standard > > library need to be a demonstration of the language? My opinion, if it > > hasn't been stated explicitly yet, is almost not at all. > > A 'standard' library implementation not only doesn't have to > demonstrate good coding style, it often cannot > be implemented in the language. > > In ISO Standards terms, a programming language's > 'standard' library is NOT a library, but rather > a part of the language itself which can be *described* > partly in terms of the core language. > > Even if the library is implemented in the core language, > it can and usually does contain all sorts of quirks > related to the known performance properties of the > compiler it is designed for. > > OTOH the *interface* should be beautiful I entirely agree with this point My hacks in ExtLib are not ugly, they are useful :) NC ```