Lazy Dynamic-Programming can be Eager

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

^up^

paper
λ-calc'
Bioinformatics

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. 

Also available in [Haskell98].
window on the wide world:

Computer Science Education Week

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Wednesday, 22-Apr-2015 09:21:38 EST.