On 28 May 2004, skaller wrote:
> On Fri, 2004-05-28 at 11:56, Brian Hurt wrote:
> > > (1) Move 'count()' up with the iterators.
> > > Count is specified to consume the enumeration.
> > > It doesn't actually have to.
> > > The current implementation is unchanged.
> > This is totally worthless. "this is how many items I just threw
> > away".
> Yes, that's what it does, but it isn't worthless.
> If the enumeration is forward, you can use a copy
> of it, which has not been consumed.
> If the enumeration is input, it makes no difference
> whether it is worthless or not because there is no
> other way to count such an enumeration than
> permanently consume it.
> Counting the number of lines in a file isn't
> entirely worthless .. unix wc does it :)
OK, I'll backtrack on "totally useless". But "less usefull than it could
be" definately applies.
My current #1 gripe with enums is their imperitive behavior. Which, as
near as I can tell, buys us nothing but trouble- take a long hard look at
Enum.force and Enum.clone for what I mean.
> > Try these semantics on for size: instead of fast_count, you get a
> > has_count, which returns true if the enumeration has a count, false
> > otherwise. If the enumeration does not have a count, it returns -1. In
> > any case, count is gaurenteed to be no worse than O(n) cost.
> > It is gaurenteed that Enum.to_list works without a count, so if you
> > absolutely need a count and can not do without it (like Enum.to_array),
> > you first convert the the enum to a list, and then get the count on the
> > list and go from there. If you do not absolutely need a count but can
> > find one usefull (like dynarray or extMap), then the function can exhibit
> > different behavior if a count exists or not- for example, a function can
> > be O(n) if a count exists, or O(n log n) if it doesn't.
> What I'd like to do is eliminate dynamic behaviour.
> I hate fast_count for that reason. I'd like to move
> more of the semantics into the static typing.
We have three choices:
1) We can have dynamic behavior- the same function is O(n) for some enums,
O(n log n) for others, and have some way to tell which to do.
2) We can lose count, and take O(n log n) hits when we could do the same
job in O(n)
3) We can lose "destructive" enums like reading in a file. If you want an
enum of the lines of file, read them into an in-memory list, and create an
enum on the list.
I will comment that the biggest argument I've heard against a
class-based implementation of enums is performance- calling a function on
and object is slower (by some small, constant, number of clock cycles)
than calling a function directly. Using an O(n log n) algorithm when we
might have been able to use an O(n) algorithm is going to be a much bigger
Notice that the current algorithm is choice 3 (as I understand things)- if
you try to do a count on a destructive enum, it calls Enum.force, which
basically loads the enum into a list and then changes the enum to be an
enum of that list. Notice that this means we have an imperitive semantic
(enums) layered on top of an applicative semantic (lists) layered on top
of an imperitive semantic (files).
> C++ has no problem with this, although the type check
> doesn't happen until link time which is a pain.
C++ uses overloading to deal with this. The if is still there, it's just
> True, we should not copy the C++ technique for doing it.
> But anyhow my goal is to try and build a more static
> model of the forward/input iterator distinction.
One needs to fake the other, IMHO. Either can fake being the other.
Choosing choice 2 (no count) means we assume all enumerations are
imperitive and destructive. Choosing choice 3 (applicative) means we
assume all enumerations have not-slow counts (no worse than O(n) time and
O(log n) stack/memory to return a count of n), and we don't need a clone.
Choosing choice 1 means we've choosen not to choose (which is always a
choice), and expect everyone to deal with both types of enumerator.
"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