edit_distance.scm

(define (change c) '(Change c))
(define (insert c) '(Insert c))
(define copy '(Copy))
(define delete '(Delete))
(define kill '(Kill))

(define (cost x)
  (length (filter (lambda (z) (not (eq? (car z) 'Copy))) x)))

(define (best edits)
  (cond ((= 1 (length edits)) (car edits))
        (else
          (let ((x (car edits)) (b (best (cdr edits))))
            (cond ((<= (cost x) (cost b)) x)
                  (else b))))))

(define (transform xs ys)
  (cond ((and (null? xs) (null? ys)) (list))
        ((null? ys) (list kill))
        ((null? xs) (map insert ys))
        (else
          (let ((x (car xs)) (y (car ys)))
            (cond ((eq? x y) (cons copy (transform (cdr xs) (cdr ys))))
                  (else (best (list (cons delete (transform (cdr xs) ys))
                               (cons (insert y) (transform xs (cdr ys)))
                               (cons (change y) (transform (cdr xs) (cdr ys)))))))))))