Leslie P. Polzer wrote:

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

Hi, there are some mistakes inside. a compiling version (not sure, if it does what you expect) is lcsList :: Eq a => [a] -> [a] -> [a] lcsList [] _ = [] lcsList _ [] = [] lcsList (x:xs) (y:ys) = if x == y then x : 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])) There were some common mistakes in your version: 1. type signature needs the type class Eq a, to ensure that you can compare the elements (function (==) is present) 2. function application binds stronger than cons (:), therefore lcsList x:xs ys means (lcsList x): (xs ys) NOT lcsList (x:xs) ys 3. in the main function concatination of strings (++) and braces around the argument of show where missing, which leds to parsing: "Result" as a function with show, lcsList, [1,2,3] and [1,3] as arguments. Greetings, Daniel.