Recursion over lists

[Bas van Dijk]

2008/2/18 TOPE KAREM <topekarem at gmail.com>:
> 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