Re: About iterators and enums

On Wed, 28 Apr 2004, Nicolas Cannasse wrote:

> [...]
> > I was happy to play with this... However I am not convinced about
> > the usefulness of iterators in OCaml.
> > I think that it could be an interesting approach in some cases, like the
> > example about graphs that was posted: for recording the current position
> > in the iteration. This requires some memory allocation.
> >
> > Efficiency matters, and this is why higher order functions seem
> > preferable in most cases.
>
> I am personaly quite convinced with Enums as forwards iterators. I am not
> about bidirectional ones.
> The nice thing about enums is that :
> - you can apply all functional ops (map/fold/iter...) to any kind of
> container without distinction

I don't really see when it is more useful or more efficient than
using directly "My_container.map f my_container".


> - you can clone at any point of the enumeration in order to enumerate again

Yes, I would like to see convincing examples.


> - you can stack several enums (for example stack several map and filters) in
> a lazy fashion
>
> > Some additional remarks:
> >
> > 1) Hashtbl.enum works in O(n), is this allowed?
> >
> > 2) The implementation of Hashtbl.keys is terribly inefficient:
> >
> >   let keys h = Enum.map (fun (k,_) -> k) (enum h)
> >
> > Why not:
> >
> >   let list_keys h = fold (fun key data accu -> key :: accu) h []
> >   let enum_keys h = List.enum (list_keys h)
>
> One of the requirement of enums is that they're O(1) constructs.

Hey, I want to get the keys, not build an enum.

> Here you need to build first a list of keys, that's really ineficient.
> But wait... I just noticed that  Hashtbl.enum looks broken.
> I'll fix this now. Thanks for the report !

Euh, you just delayed the Array.copy step. I thought that an iteration
step also needed to be executed in constant time.
I don't see how this could be done without modifying the internal
representation of hash tables.

Martin




-------------------------------------------------------
This SF.Net email is sponsored by: Oracle 10g
Get certified on the hottest thing ever to hit the market... Oracle 10g. 
Take an Oracle 10g class now, and we'll give you the exam FREE.
http://ads.osdn.com/?ad_id=3149&alloc_id=8166&op=click