Leslie P. Polzer sky at viridian-project.de
Fri Mar 13 06:58:17 EDT 2009

```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

--