title: LCS(longest common subsequence) in Scheme
body: <p>I try to use Scheme to implement LCS algorithm, but there is a bug.</p>
  
  <p>(define X
    (list #\A #\B #\C #\B #\D #\A #\B))</p>
  
  <p>(define Y
    (list #\B #\D #\C #\A #\B #\A))</p>
  
  <p>(define prefix
    (lambda (i s)
      (if (= i 0)
        '()
        (cons (car s)
              (prefix (- i 1)
                      (cdr s))))))</p>
  
  <p>(define (pick ith s)
    (if (= ith 1)
      (car s)
      (pick (- ith 1)
            (cdr s))))</p>
  
  <p>(define (LCS x y)
    (define (optimal i j)
      (cond ((or (= i 0)
                 (= j 0))
             0)
            ((eq? (pick i x)
                  (pick j y))
             (+ 1
                (optimal (- i 1)
                         (- j 1))))
            (else (max (LCS (prefix (- i 1) x) y)
                       (LCS x (prefix (- j 1) y))))))
    (optimal (length x)
             (length y)))</p>
  
  <blockquote>
    <p>1 ]=> (load "lcs.scm")</p>
    
    <p>;Loading "lcs.scm"... done
    ;Value: lcs</p>
    
    <p>1 ]=> (lcs X Y)</p>
    
    <p>;Value: 5</p>
  </blockquote>
  
  <p>The result should be 4, I do not know where is the bug.</p>