Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Frederic van der Plancke
    ... 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.
    • Guido Kollerie
      ... 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.