## Re: "ocaml_beginners"::[] Working with arrays and lists

Expand Messages
• ... You have to copy all these string fragments. To concatenate a list of N strings of length M, List.fold_right ( ^ ) copies a total of 2M + 3M + ... + NM =
Message 1 of 11 , Aug 5 11:36 AM
• 0 Attachment
Karl Zilles wrote:
>
> Martin Jambon wrote:
> > List.fold_right ( ^ ) l "" is not reasonable since it runs in O(n^2).
>
> Where do you get n^2?
>
> Looks like O(n) to me, with a high constant due to allocating a new
> string on every concatination.

You have to copy all these string fragments.
To concatenate a list of N strings of length M, List.fold_right ( ^ )
copies a total of

2M + 3M + ... + NM = O(N^2 M)

characters.

For n = NM, that's O(n^2) : consider the case where all fragments
are small so that M is bounded.

It's O(n) if there are only a few fragments (N bounded)
but clearly the constant is bigger than it should be,
for N > 2 at least.

Frédéric.
• ... String.concat is the way to go in this case as others already wrote, though should you want to program it yourself in a functional style than this one
Message 2 of 11 , Aug 7 3:32 AM
• 0 Attachment
On Thu, Aug 05, 2004 at 01:02:52PM +0200, Guido Kollerie wrote:

> Many operations on list can be expressed succinctly by using
> List.fold_left or List.fold_right:
>
> let a = [ "qwe" ; "asd" ; "zxc" ];;
>
> let comma_concat l r =
> match l with
> | "" -> r
> | _ -> if r = "" then l else l ^ ", " ^ r;;
>
> List.fold_left comma_concat "" a;;
>
>
> Yes, comma_concat is kind of ugly but it's List_fold_left that I
> wanted to demonstrate.

String.concat is the way to go in this case as others already
wrote, though should you want to program it yourself in a
functional style than this one improves upon what I wrote
earlier:

let a = [ "qwe" ; "asd" ; "zxc" ];;
let f a = List.fold_left (fun l r -> l ^ ", " ^ r) (List.hd a) (List.tl a);;

--
Guido

[Non-text portions of this message have been removed]
Your message has been successfully submitted and would be delivered to recipients shortly.