[Haskell-beginners] Longest common subsequence
Daniel Seidel
seideld at tcs.inf.tu-dresden.de
Fri Mar 13 08:00:17 EDT 2009
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.
More information about the Beginners
mailing list