用于R7RS的拆分字符串

Question

split-string函数似乎在R7RS中缺失。

我今天提出了以下实现：

(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))))))))

由于运行时或内存的使用，有什么可以优化的吗？

我使用过的这个测试用例：

(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 "  ") '("" "" "")))

Answer 1

将字符串转换为字符列表，然后重新组装字符串，是非常浪费内存的。此函数的通常实现技术应该是扫描要查找的字符，然后使用substring提取子字符串。

但是，正如OP正确指出的那样，在R7RS中，应该避免使用string-ref，因为它是O(n)。唯一明智的快速解决方案包括字符串游标(不是可移植的)和字符串端口。以下实现使用后一种方法：

(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)))))

这是一个左展开(非尾递归)解决方案。使用累加器很容易适应正确展开的解决方案：

(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)))))

作为参考，下面是使用Chibi的string游标接口的“理想”解决方案：

(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))))))

请注意，我向后迭代字符串，这样我就可以使用不需要在末尾反转的右展开实现(尾递归)。这是理想的不妥协的实现，但当然是特定于Chibi的。

Answer 2

R7RS引入了新的string-for-each过程。它没有记录在“字符串”部分，而是在第52页的“控制功能”部分。该函数简化了字符串的迭代。我喜欢的实现现在是这样的。

(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))))

性能现在取决于字符串端口实现的性能。我还将字符分隔符参数更改为谓词参数。