[Caml-list] function

[Caml-list] function

[Jeremy Fincher]

I prefer this:

(* Why in the world aren't these included in the standard library? *)
let string_foldr f init s =
  let rec aux i x =
    if i < 0 then
       x
    else
       aux (i-1) (f (String.get s i) x)
  in
    aux (String.length s - 1) init

let explode = string_foldr (fun c acc -> c :: acc) []
(* End "Why in the world?" comment *)

let digitToInt c =
  match c with
    | '0' -> 0
    | '1' -> 1
    | '2' -> 2
    | '3' -> 3
    | '4' -> 4
    | '5' -> 5
    | '6' -> 6
    | '7' -> 7
    | '8' -> 8
    | '9' -> 9
    | _   -> failwith "invalid digit"

let f l = List.map digitToInt (List.flatten (List.map explode l))

(* Or, to be more efficient, without constructing the intermediate lists via 
explode. *)
let f' l = List.fold_right (fun s l1 -> string_foldr (fun c l2 -> digitToInt 
c :: l2) l1 s) l []
(* Out of curiosity, why does fold_right take the initial value after the 
list it operates on? *)

I don't think users would be as tempted to write imperative, possibly 
inefficient code working with strings if the String module included better 
iterators such a fold_right and fold_left (and maybe even map, since strings 
are mutable in O'Caml and it could thus be done efficiently).

Jeremy

_________________________________________________________________
Protect your PC - get McAfee.com VirusScan Online 
http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963
-------------------
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

[Caml-list] function

[altavillasalvatore]

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;].

you excuse me for the banal demand!!

 I still attend to enter in the ocaml-beginners.

Regards



-------------------
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

Re: [Caml-list] function

[sebastien FURIC]

"altavillasalvatore@libero.it" a écrit :
> 
> 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;].
> 

 You could split the problem into several simple ones:

 - Given a strings, return the list of its characters:
  explode : string -> char list
 - Given a list of chars, return a list of ints using List.map:
  chars_to_ints : char list -> int list
 - And then, given a list of strings, apply a composition of the
previous functions to it (and collect the results) using List.fold_right
for instance...

 Regards,

 Sebastien.
-------------------
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

Re: [Caml-list] function

[Oleg]

On Monday 02 December 2002 10:55 am, 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;].
> 

Yes, it most certainly does.

Oleg
-------------------
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

Re: [Caml-list] function

[Issac Trotts]

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

-------------------
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

Re: [Caml-list] function

[Pierre Weis]

> 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.
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.
2)  What is the complexity of your function f ?
3)  Explain why the List.fold_left application is not only over
    complex but also runtime over consuming.

Hope this helps.

Cheers,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
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

Re: [Caml-list] function

[Issac Trotts]

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

Re: [Caml-list] function

[Oleg]

On Thursday 05 December 2002 03:24 pm, Issac Trotts wrote:
>   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.

Issac

I haven't analyzed your whole functions, but List.flatten'ing alone is 
O(S*L^2), so while it may be linear WRT the number of characters in one 
string, it's not necessarily linear WRT the total number of characters. See 
my version of f for O(L*S) time.

Cheers
Oleg
-------------------
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

Re: [Caml-list] function

[Issac Trotts]

Oleg wrote:
> On Thursday 05 December 2002 03:24 pm, Issac Trotts wrote:
> >   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.
> 
> Issac
> 
> I haven't analyzed your whole functions, but List.flatten'ing alone is 
> O(S*L^2), so while it may be linear WRT the number of characters in one 
> string, it's not necessarily linear WRT the total number of characters. See 
> my version of f for O(L*S) time.
> 
> Cheers
> Oleg

Thanks for pointing this out.

Here's flatten, from list.ml:

  let rec flatten = function
      [] -> []
    | l::r -> l @ flatten r

  let concat = flatten

Here's (@), from pervasives.ml : 

  let rec (@) l1 l2 =
    match l1 with
      [] -> l2
    | hd :: tl -> hd :: (tl @ l2)

If the given list has L elements, each with S items, then flatten should 
O((L*S)*L) = O(S*L^2) time, since you have to keep on churning through
every single element in the ever-expanding l at every recursive flatten 
call.  That's too bad.

Here's an experiment I tried:

$ cat ftime.ml 

  let rec make_list_of_lists = function 
    | 0 -> []
    | n -> [1;2;3;4;5;6;7;8] :: make_list_of_lists(n-1)

  let _ = 
    let n = int_of_string(Sys.argv.(1)) in
    let lol = make_list_of_lists n in
    ignore(List.flatten(lol))
  ;;

$ ocamlopt -o ftime ftime.ml
$ for (( i=0; $i<100; i++ )) 
  do 
    /usr/bin/time -o data -a -f "%U" ./ftime "$i"000  
  done 
$ gnuplot
  > plot 'data'

I guess it looks linear because of the small input size.
This gives me the impression that List.flatten is practical,
at least for small data sets.

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

Re: [Caml-list] function

[Xavier Leroy]

> If the given list has L elements, each with S items, then flatten should 
> O((L*S)*L) = O(S*L^2) time, since you have to keep on churning through
> every single element in the ever-expanding l at every recursive flatten 
> call.  That's too bad.
> Here's an experiment I tried:
> [...]
> I guess it looks linear because of the small input size.

It's always a good idea to do experimental measurements to confirm a
complexity analysis, just to make sure you haven't goofed.  But when
the measurements disagree with the analysis, you're supposed to go
back to the analysis and find the flaw in it, not discard the
experiment :-)

More seriously: l1 @ l2 takes time O(length(l1)); the length of l2
doesn't matter since l2 isn't copied.  This gives List.flatten a
complexity of O(S*L) in your example (list of length L, each list
element being of length S).  This is optimal for immutable,
singly-linked lists.

- Xavier Leroy
-------------------
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

Re: [Caml-list] function

[Oleg]

On Saturday 07 December 2002 05:28 am, Xavier Leroy wrote:
> > If the given list has L elements, each with S items, then flatten should
> > O((L*S)*L) = O(S*L^2) time, since you have to keep on churning through
> > every single element in the ever-expanding l at every recursive flatten
> > call.  That's too bad.
> > Here's an experiment I tried:
> > [...]
> > I guess it looks linear because of the small input size.
>
> It's always a good idea to do experimental measurements to confirm a
> complexity analysis, just to make sure you haven't goofed.  But when
> the measurements disagree with the analysis, you're supposed to go
> back to the analysis and find the flaw in it, not discard the
> experiment :-)
>
> More seriously: l1 @ l2 takes time O(length(l1)); the length of l2
> doesn't matter since l2 isn't copied.  This gives List.flatten a
> complexity of O(S*L) in your example (list of length L, each list
> element being of length S).  

You are right. I had the incorrect mental picture of (@) being called with the 
increasingly large first argument: S + 2*S +... + (L-1)*S = O(S*L^2). 

Cheers
Oleg

> This is optimal for immutable,
> singly-linked lists.
>
> - Xavier Leroy

-------------------
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

Re: [Caml-list] function

[Oleg]

On Thursday 05 December 2002 05:00 am, 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;].

[...]

To help the original poster earn extra credit, I'll write the function in the 
three languages I [sort of] know:

typedef std::list<char*> LS;
typedef std::list<int> LI;

void f(LS& input, LI& output) {
    for(LS::iterator i = input.begin(); i != input.end(); ++i)
        for(char* p = *i; *p != '\0'; ++p)
            output.push_back(int(*p) - int('0'));
}


(defun f (list)
  (loop for i in list nconcing
        (loop for j across i
              collect (- (char-int j) (char-int #\0)))))


let digit c = int_of_char c - int_of_char '0'

let rec f_aux lst i acc =
    match lst with
    | [] -> acc
    | x :: y when i = String.length x -> f_aux y 0 acc
    | x :: y -> f_aux lst (i + 1) (digit x.[i] :: acc)

let f lst = List.rev (f_aux lst 0 [])

If the input is a list of L strings of length S, then the complexity of all 
versions is O(L*S), assuming that "nconcing" caches the last element and
String.length is O(1).

Cheers
Oleg
-------------------
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

Re: [Caml-list] function

[Pal-Kristian Engstad]

On Thursday 05 December 2002 12:46 pm, Oleg wrote:
> To help the original poster earn extra credit, I'll write the function in
> the three languages I [sort of] know:
>
> typedef std::list<char*> LS;
> typedef std::list<int> LI;
>
> void f(LS& input, LI& output) {
>     for(LS::iterator i = input.begin(); i != input.end(); ++i)
>         for(char* p = *i; *p != '\0'; ++p)
>             output.push_back(int(*p) - int('0'));
> }

Isn't there a foreach() algorithm in STL?

> let rec f_aux lst i acc =
>     match lst with
>
>     | [] -> acc
>     | x :: y when i = String.length x -> f_aux y 0 acc
>     | x :: y -> f_aux lst (i + 1) (digit x.[i] :: acc)
>
> let f lst = List.rev (f_aux lst 0 [])

Ah, the use of List.rev... :-) Of course, without it, it is hard. Here's my two 
attempts:

let f4 strs = 
  let to_ord c = int_of_char c - int_of_char '0' in
  let rec strings_to_list = function
    | [] -> []
    | str :: strs ->
	let rec to_list s k n = 
	  if k = n then strings_to_list strs else to_ord s.[k] :: to_list s (k + 1) n
	in
	  to_list str 0 (String.length str) 
  in
    strings_to_list strs

This one is unfortunately not tail recursive, but it is neat in the sense that it doesn't
use any library function except int_of_char.

let f5 strs = 
  let to_ord c = int_of_char c - int_of_char '0' in
  let rec strings_to_list acc = function
    | [] -> acc
    | str :: strs ->
	let rec to_list acc s k n =
	  if k = n then strings_to_list acc strs else to_list (to_ord s.[k] :: acc) s (k + 1) n
	in
	  to_list acc str 0 (String.length str)
  in
    List.rev(strings_to_list [] strs)

Equivalent to Oleg's I believe?

PKE.
-- 
  _       
  \`.       Pål-Kristian Engstad, Senior Software Engineer,
   \ `|     Naughty Dog, Inc., 1315 3rd Street Promenade, 
  __\ |`.   Santa Monica, CA 90046, USA. (310) 752-1000 x799. 
    /  /o   mailto:engstad@naughtydog.com http://www.naughtydog.com
   /  '~    mailto:mrengstad@yahoo.com    http://www.engstad.com
  / ,'      Hang-gliding Rulez!
  ~'

-------------------
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