[Haskell-beginners] 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/