Introduction to Programming
		   Assignment 8, 22 Nov, 2004
		      Due Fri 03 Dec, 2004

		   Memoization (Edit Distance)


You are given a pair of strings s and t.  The aim is to "edit" s
to make it equal to t.  A single edit step consists of one of
the following:

1. Insert a letter in s.
2. Delete a letter from s.
3. Modify a letter in s.

For instance, if s = "rate" and t = "tact", one possible sequence
of edit steps is the following

  (rate,tact) -> (rat,tact)   : delete e 
              -> (ract,tact)  : insert c
              -> (tact,tact)  : modify r to t

In this case, it took 3 steps.  The "edit distance" of s and t is
the length of the shortest sequence of steps required to
transform s into t.

Write a Haskell function  

      editdistance :: String -> String -> Int

that computes the edit distance of its inputs using memoization.
You can use the naive Memo module provided below.  An example of
how to use this module to compute the length of the least common
subsequence is also provided.
    
======================================================================

module Memo(Table,emptytable,memofind,memolookup,memoupdate) where

data (Ord a) => Table a b = T [(a,b)]
  deriving (Eq,Show)

emptytable :: (Ord a)=>(Table a b)
emptytable = T []

memofind ::  (Ord a) => (Table a b) -> a-> Bool
memofind (T []) _ = False
memofind (T ((y,m):l)) x
  | x == y    = True
  | otherwise = memofind (T l) x

memolookup :: (Ord a) => (Table a b) -> a -> b
memolookup (T ((y,m):l)) x
  | x == y    = m
  | otherwise = memolookup (T l) x

memoupdate :: (Ord a) => (Table a b) -> (a,b) -> (Table a b)
memoupdate (T l) (x,n) =  T ((x,n):l)

======================================================================

import Memo

lcs :: String -> String -> (Int, (Table (String,String) Int))
lcs x y = lcsaux x y emptytable

lcsaux :: String -> String -> (Table (String,String) Int) -> (Int, (Table (String,String) Int))

lcsaux [] y a
  | memofind a ([],y) = (memolookup a ([],y),a)
  | otherwise         = (0,memoupdate a (([],y),0))

lcsaux x [] a
  | memofind a (x,[]) = (memolookup a (x,[]),a)
  | otherwise         = (0,memoupdate a ((x,[]),0))

lcsaux (x:xs) (y:ys) a
  | memofind a ((x:xs),(y:ys))
                = (memolookup a ((x:xs),(y:ys)),a)
  | x == y      = (1+valb, memoupdate b (((x:xs),(y:ys)),1+valb))
  | otherwise   = (maxval, memoupdate d (((x:xs),(y:ys)),maxval))
  where
  (valb,b) = (lcsaux xs ys a)
  (valc,c) = (lcsaux (x:xs) ys a)
  (vald,d) = (lcsaux xs (y:ys) c)
  maxval = max valc vald

======================================================================