## Re: [Ocaml-lib-devel] Enum semantics

 Re: [Ocaml-lib-devel] Enum semantics From: Brian Hurt - 2004-05-28 20:56:34 ```On Fri, 28 May 2004, Nicolas Cannasse wrote: > The problem is, what can do the people that want to count an input > iterator? There are three sorts of algorithms I can think of that use iterators: 1) Algorithms which don't need count, and wouldn't use it even if it existed. The canonical example here is ExtList.of_enum. 2) Algorithms which can use count, but don't need it. The canonical example here is building a balanced tree- I can build a balanced tree in O(n) if I know in advance how many elements I'm working with. Otherwise, it takes me O(n log n). 3) Algorithms which absolutely require a count, and can't be implemented without one. The canonical example here is Enum.to_array. Type 3 algorithms clash with "indefinate" enums (that don't have counts). So we have two choices- we either "fix" the indefinate enums so they have counts, or we "fix" the algorithms so they don't need a count from the enum. Interestingly enough, the basic strategy is exactly the same- convert the enum into a linked list (reading the entire enum into memory), and then count the elements in the linked list. The only question is which particular peice of code is responsible for doing the conversion? Personally, I think it's cleaner to solve the problem in Enum.to_array. Using the current imperitive semantics, to_array would look like: let rec to_array e = if has_count e then (* Normal, count-based implementation *) let c = count e in if c = 0 then [| |] else let init = next e in let retval = Array.make c init in for i = 1 to (c-1) do retval.(i) <- next e done; retval else (* convert the enum to a list, and then enumerate the list. *) to_array (ExtList.enum (ExtList.of_enum e)) ;; > Specifying an O(n) count function is not nice, you should rely on Enum > to do the work for you, and then treat your data as an input enumerator. I said "at most". If you can do a count in O(log n), or even O(1), then bully for you. But there are a number of times when I'll quite happily take an O(n) count, and still have it speed me up. Note that in the general case you should never have to call count more than once per enum- whoever is walking the enum can call count precisely once, just before starting to walk the enum, and then just keep a running count of how many items are left. The problem is that requiring an O(1) count (which is doable) can turn creating the enum from an O(1) algorithm to an O(n) algorithm. And then you might never use the count- there are a lot of uses for an enum which don't need a count. Don't take the O(n) hit unless you have to. -- "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 ```