Re: [Caml-list] queasiness about Exit

[Andreas Rossberg <rossberg@ps.uni-sb.de>]

William Harold Newman wrote:
> 
> What if I'm searching for something in a complex data structure, using
> a mapping function where, in STL or in a more object-oriented system,
> I'd use an iterator? I could do something like
>   let exists_in_complex_datastructure predicate complex_data_structure
>     try
>       map_for_effect_on_complex_data_structure
>         (fun element -> if predicate element then raise Exit)
>         complex_data_structure;
>       false
>     with Exit -> true

As an aside: As you only want to "map for effect" you better use
iteration, i.e. an "iter" function.

Also note that searching actually is neither mapping nor iteration, but
a fold operation. For example, you could define exists for arrays as
follows:

	let exists p = Array.fold_left (fun b x -> b || p x) true

But it always walks the whole array.

> But I'm having trouble convincing myself that this won't get me into
> trouble with obscure bugs later as things get complicated and
> "predicate" or "map_for_effect_on_complex_data_structure" might themselves
> be implemented in terms of "try .. raise Exit .. with Exit -> .."
> constructs.

Yes, I don't like that idiom either - although I use it myself
sometimes.

> (Of course, if I'm just searching for something in a complex data
> structure, probably the right way is to implement
> exists_in_complex_data_structure or a better search function as part
> of the interface to the data structure, instead of trying to improvise
> one as part of the map-over-all-elements function. In fact, I'm really
> not so much concerned with pure searching as with other operations
> which have a possibility of terminating early.)

For real mapping (as opposed to iteration) terminating early makes
little sense. For iteration and folds it does. It is not too difficult
to provide variations of iter and folds for your data structures that
allow early breaks. For example, consider:

	iter' : ('a -> bool) -> 'a array -> unit

Unlike the standard version of iter, the argument function returns a
boolean saying whether iteration should continue. Similarly for folds:

	fold_left' : ('a -> 'b -> 'a * bool) -> 'a -> 'b array -> 'a

With this version, you could do linear search efficiently:

	let exists p = fold_left' (fun b x -> let b' = b || p x in (b', not
b')) true

The somewhat redundant pair is a bit annoying in this particular case,
but should not really matter.

BTW, this is one of the few problems where lazy evaluation can play out
its strengths: in a lazy language you do not need variations of
iteration with early termination - you will always "terminate early"
automatically.

Hope this helps,

	- Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids; I mean if Pac Man affected us
 as kids, we would all be running around in darkened rooms, munching
 magic pills, and listening to repetitive electronic music."
 - Kristian Wilson, Nintendo Inc.
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr