Abdulaziz Ghuloum scripsit: > I must've missed it somewhere, so let me ask the stupid question. > What's the problem with the current draft that prohibits implementing > string-find portably and efficiently?
Well, let's look at the simpler case of string-index (find the index of a given character in a given string). The flatfooted implementation is "Look at each character in turn using string-ref, and if it's right, bail out, returning the current index." Unfortunately, if string-ref is O(N), then this obvious algorithm is O(N^2), nor is there any simple way to do better given only the R5.92RS primitives. However, we can obviously do much better if we have a string-for-each procedure that is O(N). Unfortunately, we have no portable way to write this procedure without string-ref. Therefore, if we accept that string-ref might not be O(1), we need some sort of iterator or iterator/constructor that will have an amortized O(N) cost for sequential access to each location. String-for-each is probably technically sufficient, but providing a few others like string-map, string-fold(-right), and string-unfold(-right) will make programmers' lives easier. (Note that both UTF-8 and UTF-16 can be traversed right-to-left at O(1) cost, though this is not true for character encodings in general.) -- When I'm stuck in something boring John Cowan where reading would be impossible or (who loves Asimov too) rude, I often set up math problems for [EMAIL PROTECTED] myself and solve them as a way to pass http://www.ccil.org/~cowan the time. --John Jenkins _______________________________________________ r6rs-discuss mailing list [email protected] http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
