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/
On Fri, Mar 13, 2009 at 11:58:17AM +0100, Leslie P. Polzer wrote:
On a related note, how can I make the function more flexible, to discern between case-sensitive and case-insensitive string comparison, for example?
One way you could do this by making a newtype wrapper around Char and creating a new Eq instance for it, like so: import Data.Char (toLower) newtype CaseInsensitive = CI Char instance Eq CaseInsensitive where (CI c1) == (CI c2) = toLower c1 == toLower c2 toCI :: String -> [CaseInsensitive] toCI = map CI fromCI :: [CaseInsensitive] -> String fromCI = map (\(CI c) -> c) -- now to do a case-insensitive LCS search you can just say something like fromCI (lcsList (toCI "BriCK") (toCI "bARk")) Of course, you could also write another version of lcsList which takes an explicit equality predicate, like the lisp version you described, but there's no way to have 'optional arguments' in Haskell. But this actually isn't too bad: -- a generic version lcsListGen :: (a -> a -> Bool) -> [a] -> [a] -> [a] lcsListGen eq xs ys = ... LCS algorithm here, using eq for comparison ... -- the less general version using an Eq constraint can just be -- implemented in terms of the above, passing in (==) for the equality test. lcsList :: (Eq a) => [a] -> [a] -> [a] lcsList = lcsListGen (==) -Brent
participants (2)
-
Brent Yorgey -
Leslie P. Polzer