Programming Praxis

The key to this exercise is the minus function that removes from a list of characters xs all the characters in a list of characters ys, or returns #f if there is a character in ys that is not in xs in sufficient multiplicity:

(define (minus xs ys)
  (let loop ((xs xs) (ys ys) (zs (list)))
    (cond ((null? ys) (append (reverse zs) xs))
          ((null? xs) #f)
          ((char<? (car xs) (car ys))
            (loop (cdr xs) ys (cons (car xs) zs)))
          ((char<? (car ys) (car xs)) #f)
          (else (loop (cdr xs) (cdr ys) zs)))))

With that, we can write a program that repeatedly subtracts candidate words from the diminishing target list until the target list is empty. Instead of backtracking, we use Wadler's "list of successes" technique which appends a new solution, if one is found, or appends a null list, which is ignored in the final output, if a path leads to no solution:

(define (anagrams str words)
  (let* ((cs (sort charlist str)))))
         (ws (relevant cs words)))
    (map (lambda (ws) (sort string<? ws)) (reverse
      (let anagrams ((cs cs) (ws ws))
        (define (cons-x x) (lambda (xs) (cons x xs)))
        (cond ((null? cs) (list (list)))
              ((null? ws) #f)
              ((equal? cs (cdar ws))
                (list (list (caar ws))))
              (else (append
                (let ((tss (anagrams cs (cdr ws))))
                  (if tss tss (list)))
                (let ((ts (minus cs (cdar ws))))
                  (if ts (let ((tss (anagrams ts (cdr ws))))
                           (if tss (map (cons-x (caar ws)) tss) (list)))
                      (list)))))))))))

The fun happens in the named-let anagrams. The first three cond clauses handle the recursive bases. The else clause appends the anagrams that include the current word (the second let clause, which has to handle specially the case where there are no anagrams) to the anagrams that exclude the current word (the first let clause).

This program incorporates an optimization: The original dictionary is condensed to only those relevant words that have all their letters in the target phrase. This optimization is significant because the list of relevant words is frequently dozens of times smaller than the original word list. The function relevant computes the condensed list:

(define (relevant cs words)
  (filter (lambda (w) (minus cs (cdr w))) words))

The dictionary consists of a list of entries of the form ("word" #\d #\o #\r #\w) containing the string form of a word in its car and the individual letters of the word, sorted in ascending order, in its car. We use map-input, filter-input and read-line from the Standard Prelude to generate the list of words:

(define (read-words dict)
  (define (valid? word)
    (and (< 2 (string-length word))
         (all? (and char-alphabetic? char-lower-case?)
               (string->list word))))
  (define (proc word)
    (cons word (sort char<? (string->list word))))
  (map-input (filter-input read-line valid?) proc dict))

We use the Moby list of common English words:

> (define words (read-words "moby.common"))

Here’s an example:

> (anagrams "Programming Praxis" words)
("aga" "grim" "nix" "prop" "rms")
... 10997 lines elided ...
("primp" "ragman" "rig" "sox"")

You can run the program at http://programmingpraxis.codepad.org/CBWq8vut.

Pages: 1 2