Lazy Dynamic-Programming can be Eager

See: L. Allison. Lazy Dynamic-Programming can be Eager. Inf. Proc. Lett., 43(4), pp207-212, Sept' 1992 [HTML]

In LML:

let takeDNA  ('>'.title) =
    let rec
        skipline 1 ('\n'.dna) = getDNA dna ||
        skipline N ('\n'.dna) = skipline (N-1) dna ||
        skipline N (a.b) = skipline N b

    and getDNA (Ch.dna)&(mem Ch ['\n'; ' ']) = getDNA dna ||
        getDNA (Base.dna)&(mem Base ['a';'c';'g';'t';'A';'C';'G';'T']) =
           let Bases,rest = getDNA dna
           in  (Base.Bases),rest       ||
        getDNA x = [],x

    in  skipline 2 title


and

D A B =
    let rec
        MainDiag = OneDiag  A B (hd Uppers) ( -1 . (hd Lowers))

    and Uppers   = EachDiag A B (MainDiag.Uppers)

    and Lowers   = EachDiag B A (MainDiag.Lowers)

    and OneDiag A B diagAbove diagBelow =
           let rec
               DoDiag [] B NW N W = [] ||
               DoDiag A [] NW N W = [] ||
               DoDiag (A.As) (B.Bs) NW N W =
                  let me = if A=B then NW
                           else 1+min3 (hd W) NW (hd N)
                  in  me.(DoDiag As Bs me (tl N) (tl W))

           and firstelt = 1+(hd diagBelow)
           and thisdiag =
                 firstelt.(DoDiag A B firstelt diagAbove (tl diagBelow))

           in thisdiag

    and min3 X Y Z =
           -- min X (min Y Z)             -- makes it O(|A|*|B|)
           if X < Y then X else min Y Z   -- makes it O(|A|*D(A,B))

    and EachDiag A [] Diags = [] ||
        EachDiag A (B.Bs) (LastDiag.Diags) =
           let NextDiag = hd(tl Diags)
           in  (OneDiag A Bs NextDiag LastDiag).(EachDiag A Bs Diags)

    and LAB = (length A)-(length B)

    in last( if      LAB = 0 then MainDiag
             else if LAB > 0 then select   LAB  Lowers
             else                 select (-LAB) Uppers )



in let rec
    L = choplist takeDNA input
and A = hd L
and B = hd(tl L)

in "D A[" @ (itos(length A)) @ "] B[" @ (itos(length B)) @ "] = "
  @ (itos(
     D A B
    ))
  @ "\n"


-- O(|A|*D(A,B)) Edit Distance.