[Jprogramming] Splitting string on other string Was: Thanks & Comments to...

[Arved Sandstrom]

Hi, Roger

Your stuff quoted below (I am getting the digest).

Agreed - splitting a string on even a simple string (no RE's) is a
non-trivial problem. Or in other words, if you think it's trivial, you
missed a bunch of special cases.

My J proficiency isn't quite there yet to achieve the economy of expression
that you have. However, after a quick glance (more study to follow later) it
does appear that in general outlines we more or less did similar stuff. I
hadn't treated the overlapping substring case, however.

Wrt the Haskell, many of the special/end cases get treated quite naturally.
I approached the problem there by setting up an initial function, of form

split pat str

that the user calls, with type String->String->[String]. This function
itself calls a helper function, say split', with additional initial
arguments plus the original arguments; not an uncommon idiom in Haskell.

Whether handled by the first "user" function, or by the helper, cases like
empty pattern or empty string get handled by Haskell function pattern
matching very naturally. All you're looking for is [] for either the
pattern, or the searched string, or both. You have to handle this anyway for
reaching the end of the string. So in its basic form you may end up with

split' [] str {other args} = {do something}
split' pat [] {other args} = {do something else}
split' pat@(p:pp) str@(s:ss) {other args} | test1 = {do A}
                                          | test2 = {do B}
                                          | otherwise = {do C}

where any of A, B or C may entail more calls to split' with modified
arguments.

As you probably intuited, the "other args" are auxiliary string
buffers...other lists. That's where the built-up curent next split substring
is accumulated, and where characters can be stored for recovery in case of a
mismatch halfway through matching the split pattern.

In broad strokes that's it, and I suspect it's more or less how even a
Haskell guru would have set it up. Many of the special cases you listed are
handled right away by just setting up the basic solution. After that it's
buffer book-keeping. :-) Incorporating Boyer-Moore jump tables doesn't even
change the general description above; that's lower-level, obviously.

Arved

**************************
Roger Hui wrote, on or about 02 Jan 2007:

The "split" problem is actually quite difficult
to get correct in all situations.  The following
are my solutions:

   split=: #@[ }.&.> [ (E. <;.1 ]) ,

   'da' split 'adam dazlious daddy'
+-+--+-------+---+
|a|m |zlious |ddy|
+-+--+-------+---+
   'da' split 'does not contain the substring'
+------------------------------+
|does not contain the substring|
+------------------------------+
   'da' split 'da'
+++
|||
+++
   'da' split ''
++
||
++
   '' split 'dazlious'
+-+-+-+-+-+-+-+-+
|d|a|z|l|i|o|u|s|
+-+-+-+-+-+-+-+-+
   '' split ''


Some cases to watch out for are:
- the prefix before the first occurrence of the substring
- the suffix after the last occurrence
- the prefix is empty
- the suffix is empty
- the substring does not occur at all
- the substring and the right argument are the same
- the substring is the empty string
- the right argument is the empty string
- the substring and the right argument are both
  the empty string
- the right argument consists of catenations
  of the substring

There is one more case that you may care about:
are substring occurrences allowed to overlap?
If they should not overlap, then the solution
above gives wrong answers in such cases:

   'dada' split 'zero dadada one dadada two'
+-----++-----++----+
|zero || one || two|
+-----++-----++----+

A correct solution obtains by replacing E. in
split by nos from
http://www.jsoftware.com/jwiki/Essays/Non-Overlapping_Substrings

nos=: 4 : 0
 s=. x I. at E. y
 i=. s I. s+#x
 (i.#y) e. (s,_1) {~ {&(i,_1)^:a: 0
)

   split1=: #@[ }.&.> [ (nos <;.1 ]) ,

   'dada' split1 'zero dadada one dadada two'
+-----+-------+------+
|zero |da one |da two|
+-----+-------+------+

I am curious about how this compares to a Haskell
solution.  As you can see, a J solution can be very
short, even if substrings are required to be
non-overlapping.