Joining some strings in a list of strings

So, say I have a list of strings, representing lines in a file, like so:

PillsytestLines =
{"foo",
"bar\\",
"baz\\",
"quux",
"wongle\\ bongle",
"wingle",
"pringle\\",
"prongle",
"blort"};


These use the (common?) convention that if a line ends with a backslash, it should be appended to the following line, giving a result like this:

PillsytestResult =
{"foo", "barbazquux", "wongle\\ bongle", "wingle", "pringleprongle", "blort"};


Now, the naïve way to accomplish this is to use pattern matching, but the performance is likely to be really awful if you've got a lot of lines:

PillsynaiveCatenateContinuedLines[lines : {___String}] :=
lines //.
{before___, line1_, line2_, after___} /;
StringMatchQ[line1, ___ ~~ "\\" ~~ EndOfString] :>
{before, StringDrop[line1, -1] <> line2, after};


You've got two potential performance hits, one with repeated breaking of the list into BlankNullSequences, and the other with repeated StringJoins (I'm actually not 100% sure that the last is avoidable, but it's certainly possible that StringJoining many strings at once is efficient, and that would explain why StringJoin has the Flat attribute).

I ended up doing what any functional programmer does when confronted with a problem they don't know how to solve: I used Fold to accumulate a linked list. This solution works, and seems like it could be efficient (in part by exploiting the Flatness of StringJoin), but I haven't done actual performance testing. EDIT: Now I have a file to test with (linked below), and this solution runs in about 4 milliseconds. The naive solution takes about 25 milliseconds, and scales quadratically with length.

PillsycatenateContinuedLines[lines : {___String}] :=
Module[{catenating},
Attributes[catenating] = {HoldAllComplete};

Flatten@Fold[
Function[{acc, line},
With[{
(* This allows me to avoid repeating myself, but is a bit nuts. *)
thunk =
If[
0 < StringLength@line && StringTake[line, -1] == "\\",
With[{dropped = StringDrop[line, -1]},
catenating@StringJoin[#, dropped] &],
StringJoin[#, line] &]
},
acc /. {
{init_, catenating[arg_]} :> {init, thunk[Unevaluated@arg]},
_ -> {acc, thunk[""]}
}]],
{},
lines]]


I checked briefly to see if there was an option for Import[file, {"Text", "Lines"}] that would allow you to specify a line continuation character, but nothing jumped out at me. I have a solution, but it seems needlessly convoluted.

EDIT to add: I have a semi-realistic test file that's long enough that I can do some timing, but unfortunately can't make it public.

EDIT again to add: OK, I munged any identifying information in the file beyond all recognition, so if you want something for test timings, you can find it here.

-

new one

This seems to be quite fast (didn't test with yours)

sc[{n_String}] := n;
sc[s_] := StringJoin[StringDrop[Most[s], -1]] <> Last[s]

sc /@ Split[testLines, StringMatchQ[#, "*\\"] &]


old one

StringJoin @@@ (
Split[testLines, StringMatchQ[#, "*\\"] &] /. s : {Repeated[_String, {2, ∞}]} :>
StringReplace[s, "\\" -> ""])

{"foo", "barbazquux", "wongle\\ bongle", "wingle", "pringleprongle", "blort"}


Notice that this is Split not SplitBy. Important difference because from adjacent elements we only test former one.

-
That is considerably faster than my Sow/Reap solution (I have a test file I'm working on that I unfortunately can't make public); I like the trick of using a one-argument predicate with Split. – Pillsy Mar 25 '14 at 19:21
@Pillsy I have to thank you, this will help me with the task I was thinking about today :P – Kuba Mar 25 '14 at 19:29
Using the munged test file above, your solution runs in about 0.5 milliseconds vs 1.5 milliseconds for my best attempt, Sow/Reap. – Pillsy Mar 25 '14 at 19:36
@Kuba: New one appears to get wrong result, e.g. I get "babaquux" instead of "barbazquux:... – ciao Mar 25 '14 at 22:08
@rasher o my, good catch. fixed. – Kuba Mar 25 '14 at 22:10

This solution requires that you know some character that does not occur in your string, in this example "|"

jacob[strList_] :=
StringSplit[
StringReplace[StringJoin[Riffle[strList, "|"]], "\\|" -> ""], "|"]


Maybe it will be fast because there are few function calls.

sc[{n_String}] := n;
sc[s_] := StringJoin[StringDrop[Most[s], -1]] <> Last[s]

kuba[strList_] :=
sc /@ Split[strList, StringMatchQ[#, "*\\"] &]

kubaOld[strList_] :=
StringJoin @@@ (Split[strList, StringMatchQ[#, "*\\"] &] /.
s : {Repeated[_String, {2, \[Infinity]}]} :>
StringReplace[s, "\\" -> ""])

(*the solution by aky took more than 10 seconds*)
(*the solution in Pillsy's answer also took more than 10 seconds *)


Timing comparison

(jacobRes = jacob[words]) // Timing // First
(kubaRes = kuba[words]) // Timing // First
(kubaOldRes = kubaOld[words]) // Timing // First
(rmrfRes = joinWords[words]) // Timing // First
jacobRes === kubaRes === kubaOldRes == rmrfRes


gives

0.449849
1.694213
2.215579
4.350092
True

-
you can use "LONGMARKER", highly unlikely to interfere :P – Kuba Mar 25 '14 at 22:34
@Kuba haha yeah. I didn't realise the second argument of StringSpit could be a pattern as well. But yeah that would be slow :P – Jacob Akkerboom Mar 25 '14 at 22:36
@Kuba thank you :). Yeah your old answer seems similar, I see you used a short version of "LONGMARKER" ;) – Jacob Akkerboom Mar 25 '14 at 22:54
:p also, Riffle is my favorite function, I hate that you've used it with success not me ;P – Kuba Mar 25 '14 at 22:57
+1, very elegant. – ciao Mar 25 '14 at 23:00

This is similar to Kuba's solution, but uses the listability of ToCharacterCode/FromCharacterCode instead of string patterns. Sometimes, this can be a bit faster than string manipulations:

joinWords[list_] := Join @@@ (Split[ToCharacterCode@list, Last[#] == 92 &] /.
{h__, 92} :> {h}) // FromCharacterCode

joinWords@PillsytestLines
(* {"foo", "barbazquux", "wongle\\ bongle", "wingle", "pringleprongle", "blort"} *)

-
This one is considerably slower than Kuba's solution; 2.5 ms vs 0.5 ms. – Pillsy Mar 25 '14 at 20:31

One alternative solution, that seems faster, but isn't really that much less horrible, uses Sow/Reap and increments a counter to use as a tag:

PillsyreapCatenateContinuedLines[lines : {___String}] :=
Module[{counter = 0},
StringJoin @@@ Last@Reap[
Scan[
If[StringMatchQ[#, ___ ~~ "\\"],
Sow[StringDrop[#, -1], counter],
Sow[#, counter++]] &,
lines]]];

-

Haven't really evaluated this in terms of speed, but throwing it into the mix anyway:

f[] := Sequence[]
f[first_String, rest___String] :=
If[StringTake[first, -1] == "\\",
f[StringDrop[first, -1] <> First@{rest},
Sequence @@ Rest@{rest}], {first, f[rest]}]

Flatten[f @@ PillsytestLines]
(* {"foo", "barbazquux", "wongle\\ bongle", "wingle", "pringleprongle", "blort"} *)

-
This is going to have performance problems similar to the ones with PillsynaiveCatenateContinuedLines; when I tried it with twice as many lines of input, it took about 4 times as long. The common functional programming idiom of recursively breaking a list into a head and a tail doesn't really work with Mathematica's pattern matching. – Pillsy Mar 25 '14 at 20:39
I would've expected that - because of the (head: tail) pattern match - this would be faster, at least compared to matching in the middle of a list, as you do in your naiveCatenateContinuedLines. I tried my function on a list 10 times the size of your test lines (basically generated by doing Flatten[ConstantArray[PillsytestLines, 10]] ) and Timing showed that it was 10 times slower compared to the original. A 100 times larger list came out to be 200-300 times slower compared to the original. (But yeah, doesn't hold a candle to Kuba's solution.) – Aky Mar 25 '14 at 21:08