Simple Mispelling Problem —

Simple Mispelling Problem

by Joshua Branson — November 22, 2022

I had this simple coding problem that I wanted to solve. Here's the problem:

Suppose you are writing an guix service (like I happen to be), and you are sanitizing user input for various records. Suppose your user mispells an option. Wouldn't it be nice to include a nice helpful hint on what he probably did wrong?

(opensmtpd-option (option "forany"))

error: (option "forany") is invalid.
hint: Try "for rcpt-to", "for domain", "for local", "for any", or "for".

Using string-prefix-length-ci, I was able to construct a fairly naive prococedure that tries to guess what the user meant to type. Here's what I came up with:

;; if strings is (list "auth" "for any" "from local")
;; Then this will return "Try \"auth\", \"for any\", or \"from local\"."
(define (try-string strings)
  (string-append "Try "
                 (let loop ((strings strings))
                   (cond ((= 1 (length strings))
                           "or \"" (car strings) "\".\n"))
                           "\"" (car strings) "\", "
                           (loop (cdr strings))))))))

;; suppose string is "for anys"
;; and strings is (list "for any" "for local" "for domain")
;; then hint-string will return "Did you mean "for any"?"
(define* (hint-string string strings
                      #:key (fieldname #f))
  (if (not (string? string))
      (try-string strings)
      (let loop ((current-max 1)
                 (loop-strings strings)
                 (hint-strings '()))
        (if (null? loop-strings)
            (cond ((= 1 (length hint-strings)) ;; only one worthwhile match
                   (if fieldname
                       (string-append "Did you mean (" fieldname " \""
                                      (car hint-strings) "\") ?\n")
                       (string-append "Did you mean \"" (car hint-strings)
                  (else (if (null? hint-strings)
                            (try-string strings)
                            (try-string hint-strings))))
            (let* ((element-string (car loop-strings))
                    (string-prefix-length-ci element-string string)))
              (cond ((> element-max current-max)
                     (loop element-max (cdr loop-strings)
                           (list element-string)))
                    ((= element-max current-max)
                     (loop current-max (cdr loop-strings)
                           (cons element-string hint-strings)))
                    (else (loop current-max
                                (cdr loop-strings) hint-strings))))))))

It won't recognize that "or any" or "bor any" should match "for any", but for most mispellings, it should be half decent, provided the user got the first character right.

What do you all think? How would you write such a procedure?