[Haskell-beginners] Longest common subsequence

[Brent Yorgey]

On Fri, Mar 13, 2009 at 11:58:17AM +0100, Leslie P. Polzer wrote:
> 
> On a related note, how can I make the function more flexible,
> to discern between case-sensitive and case-insensitive string
> comparison, for example?

One way you could do this by making a newtype wrapper around Char and
creating a new Eq instance for it, like so:

  import Data.Char (toLower)

  newtype CaseInsensitive = CI Char

  instance Eq CaseInsensitive where
    (CI c1) == (CI c2)  =  toLower c1 == toLower c2

  toCI :: String -> [CaseInsensitive]
  toCI = map CI

  fromCI :: [CaseInsensitive] -> String
  fromCI = map (\(CI c) -> c)

  -- now to do a case-insensitive LCS search you can just say something like
  fromCI (lcsList (toCI "BriCK") (toCI "bARk"))

Of course, you could also write another version of lcsList which takes
an explicit equality predicate, like the lisp version you described,
but there's no way to have 'optional arguments' in Haskell.  But this
actually isn't too bad:

  -- a generic version
  lcsListGen :: (a -> a -> Bool) -> [a] -> [a] -> [a]
  lcsListGen eq xs ys = ... LCS algorithm here, using eq for comparison ...

  -- the less general version using an Eq constraint can just be
  -- implemented in terms of the above, passing in (==) for the equality test.
  lcsList :: (Eq a) => [a] -> [a] -> [a]
  lcsList = lcsListGen (==)


-Brent