Re: [Ocaml-lib-devel] Enum inconsistent

[Brian H. <bri...@ql...>]

On Sat, 21 Jun 2003, John Skaller wrote:

> 
> That isn't really acceptable, since the enumeration
> is conceptually a model of a mutable object:
> even though the enum module itself is functional,
> it is being used to contruct mutator functions
> which operate on a stateful object.

I toyed with the idea of a applicative enumeration, and then realized
something: while you can always wrap an applicative behavior with an
imperitive behavior (using a reference if nothing else), you can not wrap
an imperitive behavior with an applicative behavior.

The idea I had was basically to make Enum.next look like:

val next: 'a Enum.t -> 'a option * 'a Enum.t

I.e. return the next object and the enumeration of the rest.  Then I 
considered how would I write an enumeration of the lines of a file?

> 
> The fast_count function must be elided:
> it is a symptom of the designer not being
> able to make up his mind exactly what
> the model is.
> 
> This is non-trivial. The only way to count
> a filtered enumeration is eagerly,
> on the other hand next can be applied lazily.

I think part of the problem is that enumeration is becoming a victim of 
it's own success.  We're starting to want to apply it in ways not 
originally conceived of.  It's a great way to "glue together" parts of a 
program.  But this is putting stress on the original model, as we keep 
going "well, this situation is almost exactly like an enumeration, 
except we need to be able to do this...".

There are time we *need* a count, almost no matter how expensive it is.  
An example of this is ExtArray.of_enum.  We need to count to know how
large to make the array.  In other situations, a count is usefull but not
necessary.  For example, if you're inserting an enumeration into the
middle of a Dynarray, having a count is usefull- this way I only have to
resize and move elements once.  However, I can fake it without too much 
heartache if I don't have a count.  I'll have to move things approximately 
log N times, but that's not too horrible.

Maybe a way to help clear the air a little bit would be to list those 
places we might like to use enumerations, and the problems/demands those 
uses place on the enumeration interface.  To get us started, here's my 
list:

- enumerating a list.  Counts are O(N)

- reading file as an enumeration of strings (one per line).  Don't know in
advance how many lines are going to be read, imperitive semantics (next
changes the state of the io channel).  Clone is interesting.

- creating an array from the enumeration.  Count is necessary, alternative 
is creating a linked list.

- insert an enumeration into the middle of a dynarray.  Count helpful, 
alternatives not too bad.

- creating tree data structures.  Need an exported next, with a count I 
can build a balanced tree in O(N), without it's O(N log N).

- filtering an enum- makes even easy O(1) counts (like arrays) into 
unknown counts.

More?


> The [from] function is the biggest hassle,
> I'd consider removing it. The client can
> always use
> 
> 	init f limit
> 
> which also might turn accidental infinite loops
> into merely very long ones :-)


All the places where I can see from being usefull, init as defined above 
is just as usefull.  I don't have a problem with this.  But I'm not sure 
it solves the basic problems.

Brian