Re: [Caml-list] function

[Issac Trotts <ijtrotts@ucdavis.edu>]

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