3

The OCaml standard library provides the function String.concat

https://caml.inria.fr/pub/docs/manual-ocaml/libref/String.html

val concat : string -> string list -> string

String.concat sep sl concatenates the list of strings sl, inserting the separator string sep between each.

Presumably this function exists to make easier to concatenate many strings together in time/space linear in the length of the strings.

Does similar functionality exist for arrays? In particular, is there a way to efficiently concatenate an array of strings together without either 1) writing a C extension and building a tricky intermediate structure or 2) effectively calling String.concat "" (Array.to_list arr)).

Improve this question

2 Answers 2

Reset to default
5

The best is to write your own concat function imitating String.concat. If you want something shorter, use a buffer to accumulate the result of your result (Array.iter (Buffer.add_string b) arr) — do not do repeated concatenations which will generate too many allocations.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Could you expand on the "too many allocations" comment? When compiled to JavaScript (and run on V8), concatenation is still faster than Buffer.add_string (see the updated benchmark link in my answer). This doesn't necessarily translate to OCaml of course, but it makes it non-obvious to me that "too many allocations" is a problem. Especially since OCaml's GC ought to be tuned for many allocations due to its emphasis on immutability.
Say that the strings in your array have lengths n₁, n₂,..., nₖ. Concatenating recursively will create a string of length n₁+n₂, then n₁+n₂+n₃, n₁+n₂+n₃+n₄,... That depends on the string representation in the language of course — if represented using, say, ropes then concatenation is really fast (O(1)). Javascript seems to be using "dependent strings" which seems to be another name for ropes. stackoverflow.com/questions/6551918/… (There is a Rope module for OCaml BTW.)
4

I'm sure there are more efficient ways of doing it, like the unsafe_blit approach String.concat is using, but a simple fold is at least an improvement over option 2:

Array.fold_left (fun acc s -> acc ^ s) "" arr

Reason/BuckleScript benchmark

Improve this answer

1 Comment

Err ... in this case the efficiency of String.concat is what I'm trying to duplicate. The blit functionality is Bytes is certainly useful though ... and you might be able to cobble together an efficient implementation for arrays of strings ...

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.