[Haskell-beginners] Longest common subsequence

[Daniel Seidel]

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.