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 VAA10560; Thu, 5 Dec 2002 21:24:25 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id VAA10717 for ; Thu, 5 Dec 2002 21:24:24 +0100 (MET) Received: from rome.ucdavis.edu (rome.ucdavis.edu [169.237.104.165]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id gB5KON105864 for ; Thu, 5 Dec 2002 21:24:23 +0100 (MET) Received: from boson.localdomain.fake (postfix@[128.120.141.218]) by rome.ucdavis.edu (8.11.6/8.11.0/virus-scan-4.0.1) with ESMTP id gB5KOJ803403 for ; Thu, 5 Dec 2002 12:24:19 -0800 (PST) Received: by boson.localdomain.fake (Postfix, from userid 1000) id 343B5A00C9; Thu, 5 Dec 2002 12:24:49 -0800 (PST) Date: Thu, 5 Dec 2002 12:24:49 -0800 From: Issac Trotts To: OCaml Mailing List Subject: Re: [Caml-list] function Message-ID: <20021205202448.GB524@boson.ucdavis.edu> References: <20021203232211.GC22545@beech> <200212051000.LAA22469@pauillac.inria.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200212051000.LAA22469@pauillac.inria.fr> User-Agent: Mutt/1.3.28i Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Pierre Weis wrote: > > On Mon, Dec 02, 2002 at 04:55:06PM +0100, altavillasalvatore@libero.it wrote: > > > Hi all, > > > I would want to know if a function exists that allows me to make this: > > > > > > ["123";"45";"678"] -> [1;2;3;4;5;6;7;8;]. > > > > let f l = > > let ret = ref [] in > > String.iter > > (fun c -> ret := ((int_of_char c) - (int_of_char '0')) :: !ret) > > (List.fold_left (^) "" l); > > List.rev !ret;; > > > > f ["123";"45";"678"];; > > > > Cheers, > > Issac Trotts > > If you like puzzles, here is an additional exercise: > > 00) List which parens are useless in this code, according to which > rules given in the simple guide-lines and syntactic conventions of > http://pauillac.inria.fr/caml/FAQ/qrg-eng.html#parens and > http://pauillac.inria.fr/caml/FAQ/pgl-eng.html#parens. I see. It should have been (fun c -> ret := int_of_char c - int_of_char '0' :: !ret) > 0) Rewrite this code to a more suitable form for a beginner, > i.e. in a purely functional style with no side effect. > 1) Try to avoid the useless List.rev at the end. let f2 strs = let to_ord c = int_of_char c - int_of_char '0' in let rec to_list s k n = if k = n then [] else to_ord s.[k] :: to_list s (k + 1) n in let s = String.concat "" strs in to_list s 0 (String.length s);; As PKE points out, this still creates a possibly huge intermediate string s. Here's a way that doesn't: let f3 strs = let to_ord c = int_of_char c - int_of_char '0' in let rec to_list s k n = if k = n then [] else to_ord s.[k] :: to_list s (k + 1) n in let to_list2 s = to_list s 0 (String.length s) in List.concat (List.map to_list2 strs);; > 2) What is the complexity of your function f ? The new ones have linear time complexity w.r.t. the number of characters. The old one has quadratic time complexity. > 3) Explain why the List.fold_left application is not only over > complex but also runtime over consuming. At each step in the fold_left application, we create a new string of greater size and needlessly copy all the old data from the smaller string storing the accumulated result. This is what makes it run in quadratic time. String.concat runs in linear time in the number of characters contained in the input string list. Thanks for the tips. Issac ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners