[plt-scheme] critique of some code

From: Shriram Krishnamurthi (sk at cs.brown.edu)
Date: Sun Dec 6 23:05:50 EST 2009

Here's my version.

Zero, I assume you want the naive version, not something like the KMP
or BM algorithms.

First, I changed your contract to return false instead of -1, because
that's what a Schemer would have done.

Second, I converted to lists, because that's also what a Schemer would
do (unless you were concerned about long strings, in which case anyway
you'd use KMP/BM above some threshold).

Third, here's both the and/or version and the cond version.

Fourth, it's in TS.


#lang typed-scheme

(require scheme/list)
(require scheme/bool)

(: string-index-of (String String -> (U Number Boolean)))

(define (string-index-of in for)
  (sio/list (string->list in) (string->list for) 0))

(define: (sio/list [check-in : (Listof Char)]
                   [check-for : (Listof Char)]
                   [index : Number]) : (U Number Boolean)
  (and (not (empty? check-in))
       (or (and (prefix-of? check-for check-in) index)
           (sio/list (rest check-in) check-for (add1 index)))))
    [(empty? check-in) false]
    [else (if (prefix-of? check-for check-in)
              (sio/list (rest check-in) check-for (add1 index)))]))

(define: (prefix-of? [pre : (Listof Char)]
                     [big : (Listof Char)]) : Boolean
  (or (empty? pre)
      (and (not (empty? big))
           (char=? (first pre) (first big))
           (prefix-of? (rest pre) (rest big)))))
    [(empty? pre) true]
    [(empty? big) false]
    [else (and (char=? (first pre) (first big))
               (prefix-of? (rest pre) (rest big)))]))

(define check-expect equal?)
(check-expect (string-index-of "abcd" "a") 0)
(check-expect (string-index-of "abc" "bc") 1)
(check-expect (string-index-of "abcd" "d") 3)
(check-expect (string-index-of "abcd" "de") false)
(check-expect (string-index-of "abcd" "abcde") false)

Posted on the users mailing list.