3
\$\begingroup\$

A split-string function seems to be missing in R7RS.

I came up with the following implementation today:

(define (split-string delim str)
  (let ((add (lambda (current output)
               (cons (list->string (reverse current)) output))))
    (let loop ((input (string->list str))
               (output #f)
               (current #f))
      (if (null? input)
          (if output
              (reverse (if current 
                           (add current output)
                           output))
              '())
          (let ((char (car input))
                (input (cdr input)))
            (if (char=? char delim)
                (loop input (add current output) '())
                (loop input output (cons char current))))))))

Is there anything which can be optimized due to run time or memory usage?

This test case I have used:

(import (scheme write))

(define-syntax test
  (syntax-rules ()
    ((test function index (predicate (argument ...) result))
     (let ((value (function argument ...)))
       (let ((test-result (predicate value result)))
         (display 'function)
         (if index
             (begin
               (display " ")
               (display index)))
         (display ": ")
         (if test-result
             (display "ok")
             (begin
               (display "FAILURE")
               (newline)
               (display "  Expression: ")
               (write '(function argument ...))
               (newline)
               (display "  returns: ")
               (display value)
               (newline)
               (display "  expecting: ")
               (write result)))
         (newline)
         test-result)))
    ((test function index ((argument ...) result))
     (test function index (equal? (argument ...) result)))
    ((test function (predicate (argument ...) result))
     (test function #f (predicate (argument ...) result)))
    ((test function ((argument ...) result))
     (test function #f (equal? (argument ...) result)))))

(define-syntax test*
  (syntax-rules ()
    ((test* function definition ...)
     (let ((counter (let ((value 1))
                      (lambda ()
                        (let ((this value))
                          (set! value (+ value 1))
                          this)))))
       (and (let ((index (counter)))
              (test function index definition))
            ...)))))

(test* split-string
       ((#\space "abc def") '("abc" "def"))
       ((#\space " ") '("" ""))
       ((#\space "") '())
       ((#\space " a") '("" "a"))
       ((#\space "a ") '("a" ""))
       ((#\space "  ") '("" "" "")))
\$\endgroup\$
4
\$\begingroup\$

Converting strings into lists of characters, then reassembling strings, is quite wasteful of memory. The usual implementation technique for this function should be to scan for the character you're looking for, and then use substring to extract the substring.

However, as the OP correctly points out, in R7RS, string-ref should be avoided because it's O(n). The only sensible fast solutions involve string cursors (which are not portable) and string ports. The below implementation uses the latter:

(define (string-split str delim)
  (define in (open-input-string str))
  (let recur ((out (open-output-string)))
    (define c (read-char in))
    (cond ((eof-object? c)
           (list (get-output-string out)))
          ((char=? c delim)
           (cons (get-output-string out)
                 (recur (open-output-string))))
          (else
           (write-char c out)
           (recur out)))))

That's a left-unfolding (non-tail-recursive) solution. It's easy enough to adapt to a right-unfolding solution using an accumulator:

(define (string-split str delim)
  (define in (open-input-string str))
  (let loop ((rv '()) (out (open-output-string)))
    (define c (read-char in))
    (cond ((eof-object? c)
           (reverse (cons (get-output-string out) rv)))
          ((char=? c delim)
           (loop (cons (get-output-string out) rv)
                 (open-output-string)))
          (else
           (write-char c out)
           (loop rv out)))))

For reference, here's the "ideal" solution using Chibi's string cursor interface:

(import (chibi string))
(define (string-split str delim)
  (define start (string-cursor-start str))
  (let loop ((rv '())
             (cur (string-cursor-end str))
             (last (string-cursor-end str)))
    (if (string-cursor=? cur start)
        (cons (substring-cursor str cur last) rv)
        (let ((prev (string-cursor-prev str cur)))
          (if (char=? (string-cursor-ref str prev) delim)
              (loop (cons (substring-cursor str cur last) rv) prev prev)
              (loop rv prev last))))))

Notice that I iterate through the string backwards so that I can use a right-unfolding implementation (tail-recursive) that does not require reversing at the end. This is the ideal no-compromises implementation, but of course it's Chibi-specific.

\$\endgroup\$
  • \$\begingroup\$ 1.) Both solutions use string-ref. But R7RS specifies: "There is no requirement for this procedure to execute in constant time". This is the case, if the implementation uses the UTF-8 encoding for strings in memory. So the solution uses less memory but more run time? 2.) What intention did you have not returning an empty list, if the delimiter can not be found in the string? \$\endgroup\$ – ceving Dec 30 '14 at 10:38
  • 1
    \$\begingroup\$ 1. Thank you for the reminder. See, this is why having to be portable sucks. There are no efficient portable solutions. In Chibi, there's a string cursor API, that is efficient but not portable. That section also talks about the possibility of using string ports, which is probably the best we can do here (and I'll update my answer to use that). 2. How would you consider the case where the string is not empty but still delimiterless? Why should an empty string be any different? \$\endgroup\$ – Chris Jester-Young Dec 30 '14 at 13:41
  • \$\begingroup\$ If it sucks to be portable, it is obviously a problem of the standard. A few weeks ago it was possible to change the standard. Now R7RS has been passed. \$\endgroup\$ – ceving Jan 1 '15 at 13:33
  • \$\begingroup\$ No, R7RS-small has been passed over a year ago (in November 2013). Also, I think most people in the R7RS committee would agree that a string cursor interface is more the domain of R7RS-large rather than R7RS-small. Things are as they should be in R7RS-small, in my opinion, even if it doesn't provide for optimal performance for string manipulation. \$\endgroup\$ – Chris Jester-Young Jan 1 '15 at 16:53
  • \$\begingroup\$ I do not agree. The small part of the language must contain those features, which can not be implemented efficiently in the language itself. And the libraries should contain only the voluntary extra tasks, which can be implemented in a portable way. It would be a big win for the Scheme community, if most libraries would be portable. \$\endgroup\$ – ceving Jan 1 '15 at 18:25
0
\$\begingroup\$

R7RS introduces the new string-for-each procedure. It is not documented in the "Strings" section but the "Control features" section on page 52. The function simplifies the iteration of strings. My preferred implementation is now this.

(define (split-string delimiter? string)
  (let ((result (list))
        (output (open-output-string)))
    (string-for-each
     (lambda (char)
       (if (delimiter? char)
           (begin
             (set! result (cons (get-output-string output) result))
             (set! output (open-output-string)))
           (write-char char output)))
     string)
    (reverse (cons (get-output-string output) result))))

The performance depends now on the performance of the string-port implementation. I also changed the character delimiter argument to a predicate argument.

\$\endgroup\$
  • \$\begingroup\$ The downside to using string-for-each is that you ended up having to use set!, which is frowned-upon by many "purists". If you're going to use string ports, you may as well go whole-hog and use my string port solution, which does not require the use of set!. :-) \$\endgroup\$ – Chris Jester-Young Jan 13 '15 at 4:43
  • \$\begingroup\$ It's too bad that R7RS does not have string-fold (from SRFI 13, which was where string-for-each and string-map also came from). With that, you could do a solution very similar to what you had, but without set!. \$\endgroup\$ – Chris Jester-Young Jan 13 '15 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.