Re: [Ocaml-lib-devel] Enum.has_next (was : More thoughts on Enum)

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

On Mon, 2 Jun 2003, Nicolas Cannasse wrote:

> But we can't rewrite fold/iter using has_next because, has you mentionned,
> the default has_next will test count > 0 and the default count will force
> the enumeration of the data structure, resulting the building of an
> intermediate list, which is what we actually don't want to do.

Actually, we could have the default do a lookahead, like:
    let default_has_next next count =
        let lookahead = ref None in
        let has_next' () =
            match lookahead with
                Some x -> true
                | None -> try
                    lookahead := Some (next ());
                    true
                    with No_more_elements -> false
        and next' () =
            match lookahead with
                Some x ->
                    lookahead := None;
                    x
                | None ->
                    next()
        and count' () ->
            match lookahead with
                Some _ -> 1 + (count ())
                | None -> count()
        in
        Enum.make ~has_next:has_next' ~next:next' ~count:count'

And then override it when count is O(1).  Note that a map always gets the 
count and has_next functions, so we only ever allocate a single Some 
block (note that next doesn't allocate a some block).

> Of course we could add the has_next function as a parameter to make but :
> - when we call make, we usually have a good count , so testing count > 0 is
> not so costly

I agree that this is the default case- a fast count.  Which is why I was 
making it the default case.  On the other hand, handling the case when 
count is expensive is more complex code, so maybe the library should be 
supplying that.

> - as the next function is returning a 'a option (and I still think that's
> the best way of doing it) the user will not need an has_next to loop.

No.  I was thinking of doing it for the library.

Another question I have: how often are we going to get "deep maps" (i.e.  
more than 1 layer deep)?  I expect the vast majority of cases are going to
be either:
1) no maps at all (converting from one data structure to another), or
2) exactly one map (doing a single conversion).

So that, on average, we have less than 1 map we're going through.  Now, I 
want to encourage deep maps, as it's a form of wavefront processing and 
thus more efficient in general.  But I don't think they will be common.  
In optimizing, you optimize for the common case.

Brian