Re: [Haskell-beginners] Longest common subsequence

13 Mar 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.

Re: [Haskell-beginners] Longest common subsequence

Daniel Seidel