From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA07623; Thu, 15 Nov 2001 17:58:38 +0100 (MET) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA07262 for ; Thu, 15 Nov 2001 17:58:36 +0100 (MET) Received: from uni-sb.de (uni-sb.de [134.96.252.33]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id fAFGwaj12174 for ; Thu, 15 Nov 2001 17:58:36 +0100 (MET) Received: from cs.uni-sb.de (cs.uni-sb.de [134.96.252.31]) by uni-sb.de (8.11.6/2001082200) with ESMTP id fAFGwZP14180 for ; Thu, 15 Nov 2001 17:58:35 +0100 (CET) Received: from mail.cs.uni-sb.de (IDENT:E//wX8HreTtStAOj0T8kSShjfGSXzhQh@mail.cs.uni-sb.de [134.96.254.200]) by cs.uni-sb.de (8.12.1/2001100800) with ESMTP id fAFGwYN15597 for ; Thu, 15 Nov 2001 17:58:35 +0100 (CET) Received: from ps.uni-sb.de (grizzly.ps.uni-sb.de [134.96.186.68]) by mail.cs.uni-sb.de (8.12.1/2001110800) with ESMTP id fAFGwXD28182 for ; Thu, 15 Nov 2001 17:58:33 +0100 (CET) X-Authentication-Warning: email: Host grizzly.ps.uni-sb.de [134.96.186.68] claimed to be ps.uni-sb.de Received: from ps.uni-sb.de (zoidberg.ps.uni-sb.de [134.96.186.121]) by ps.uni-sb.de (8.11.2/8.11.0) with ESMTP id fAFGwWb12996; Thu, 15 Nov 2001 17:58:32 +0100 Message-ID: <3BF3F438.E1F484C0@ps.uni-sb.de> Date: Thu, 15 Nov 2001 17:58:32 +0100 From: Andreas Rossberg Organization: =?iso-8859-1?Q?Universit=E4t?= des Saarlandes X-Mailer: Mozilla 4.77 [en] (X11; U; Linux 2.4.3-12 i686) X-Accept-Language: de, en MIME-Version: 1.0 To: caml-list@inria.fr Subject: Re: [Caml-list] queasiness about Exit References: <20011115093845.A26661@rootless> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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