[Haskell-beginners] Longest common subsequence
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
--
LinkedIn Profile: http://www.linkedin.com/in/polzer
Xing Profile: https://www.xing.com/profile/LeslieP_Polzer
Blog: http://blog.viridian-project.de/
More information about the Beginners
mailing list