2008/2/18 TOPE KAREM :

However, I need to write a recursive function over two lists.

( Note that functions which use explicit recursion are usually harder to understand then functions which abstract over the recursion using higher order functions. See: http://haskell.org/haskellwiki/Things_to_avoid#Avoid_explicit_recursion )

The function must check the elements in the two lists and return an element that is common to both lists if there is any.

Lets call the function you want to define: 'common'. You should always start with the design. Designing in Haskell means defining the type of your function. According to your specification, 'common' takes two lists of which the elements should be compared for equality: common :: Eq a => [a] -> [a] -> ... 'common' should return a value that indicates that there are no common elements in both lists or a value that indicates which element is common to both lists. The 'Prelude' [2] already contains a data type that we can use for this. It's called 'Maybe' and it's parameterized by the value that can possibly be returned. It's defined as follows: data Maybe a = Nothing | Just a So the final type of 'common' is: common :: Eq a => [a] -> [a] -> Maybe a Before you immediately start programming let's first think about some properties of 'common'. The nice thing about properties is that they give you a formal specification instead of the informal one you've given above. What's truly nice is that you can define these properties in Haskell itself! And later use these properties to automatically _test_ your function using a tool called 'QuickCheck' [3]. The most obvious property of 'common' that comes to my mind is that for all lists 'xs' and 'ys' if 'common xs ys' equals 'Nothing' then each element of 'ys' should not be an element of 'xs'. And if 'common xs ys' equals 'Just z' then 'z' should be an element of both 'xs' and 'ys'. This can be defined in Haskell as follows: prop_common :: [Int] -> [Int] -> Bool prop_common xs ys = case common xs ys of Nothing -> all (`notElem` xs) ys Just z -> z `elem` xs && z `elem` ys Note that I've fixed the type of the lists to [Int]. This is useful when testing the function later on with QuickCheck. Now, I'm not going to give the definition of 'common xs ys', that wouldn't be fun! But I good give you some pointers. First you could try filtering all the elements of 'ys' that are elements of 'xs'. Then use a auxiliary functions which transforms the filtered list into a 'Maybe' value. Tip use Hoogle [1] to search for existing functions (like 'filter'). Finally, if you have defined your function you should test it against the specification (prop_common). You can do this with QuickCheck. Just 'import Test.QuickCheck' and run 'test prop_common'. This will automatically generate random test cases and apply 'prop_common' to them. If your definition passes the test you can be quite sure it's correct. regards, Bas [1] http://www.haskell.org/hoogle [2] The Prelude is a library containing lots of useful functions, data types, classes and instances that is always loaded automatically in each of your modules. Just 'hoogle' [1] for 'Prelude': [3] QuickCheck is a tool for testing Haskell programs automatically. Just 'hoogle' [1] for 'QuickCheck': P.S. It's better to ask such questions on the haskell-cafe mailinglist. See: http://haskell.org/haskellwiki/Mailing_lists