Longest common subsequence

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Longest common subsequence

Leslie P. Polzer

Hi,

after the factorial function I tried to write my second Haskell
program, tackling the longest common subsequence algorithm:

lcsList :: [a] -> [a] -> [a]
lcsList [] _ = []
lcsList _ [] = []
lcsList (x:xs) (y:ys) = if x == y
                           then lcsList xs ys
                           else
                             let lcs1 = lcsList x:xs ys
                                 lcs2 = lcsList xs y:ys
                             in if (length lcs1) > (length lcs2)
                                   then lcs1
                                   else lcs2

main = do
  putStrLn("Result: " show lcsList [1,2,3] [1,3])

GHC has several problems with it:

lcs.hs:4:27:
    Could not deduce (Eq a) from the context ()
      arising from a use of `==' at lcs.hs:4:27-32
    Possible fix:
      add (Eq a) to the context of the type signature for `lcsList'

I understand that I need to specify that type 'a' needs to
be a derived type of something that can be compared, but
how do I specify this in the code?

On a related note, how can I make the function more flexible,
to discern between case-sensitive and case-insensitive string
comparison, for example?

In Lisp I would just write this lambda list:

(defun lcs-list (list1 list2 &key (test #'eql))
  ...)

and it would allow me to specify the test but use some sensible
default if I don't.


And two other errors which I don't quite get:

lcs.hs:7:50:
    Couldn't match expected type `[a] -> [[a1] -> [a1]]'
           against inferred type `[a]'
    In the second argument of `(:)', namely `xs ys'
    In the expression: lcsList x : xs ys
    In the definition of `lcs1': lcs1 = lcsList x : xs ys

lcs.hs:8:33:
    Occurs check: cannot construct the infinite type: a = [a]
    When generalising the type(s) for `lcs2'
    In the expression:
        let
          lcs1 = lcsList x : xs ys
          lcs2 = lcsList xs y : ys
        in if (length lcs1) > (length lcs2) then lcs1 else lcs2

            in if (length lcs1) > (length lcs2) then lcs1 else lcs2

Can you help me with that?

  Thanks,

    Leslie

--
LinkedIn Profile: http://www.linkedin.com/in/polzer
Xing Profile: https://www.xing.com/profile/LeslieP_Polzer
Blog: http://blog.viridian-project.de/

Reply | Threaded
Open this post in threaded view
|

Longest common subsequence

Brent Yorgey-2
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