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/polzerXing Profile:

https://www.xing.com/profile/LeslieP_PolzerBlog:

http://blog.viridian-project.de/