Comparing two lists in Haskell

A while ago I wrote a blog post titled C# used for comparing two lists. It is high time that I did that in Haskell as well. Now, I plan to do away with file IO in this blog post and instead focus on the list processing ability of the language (Haskell). I am not doing that to cheat; I honestly want to focus on that! So here we go.

Like on my blog post mentioned above, we have two lists and we want to find the elements of the second list that are not on the first list. Specifically, let us call the first list as and the second list bs. We want to find the elements of bs that do not exist in as and put those elements in a third list called cs.

What we ask is straightforward and fair, but how are we to go about and do it? Remember, Haskell, being a functional language, does not favor iteration. We have to think recursively.

OK, we will need a function that we are going to call recursively, once for each element of the second list. To this function we will be passing the second list as n:ns, and we will lookup the first element n in the fist list. Then we will call the same function recursively with the remainder of the second list (ns). But we do not want to lose the result of each lookup (and we do one lookup in each recursion, once for each element of the second list). So, we need to call the recursive function passing it, not only the whole first list and the remainder of the second list, but also another list (outList) that holds the elements of the second list that have so far being found on the first list.

Let us call the function that we will cal from the main program as
list_Of_Elements_In_Second_List_But_Not_In_First_List. The logical thing to do is for this function to take only two arguments: the first list as and the second list bs. And it will return the list cs that contains the elements that are in bs but not in as. But we also need a function that we are going to call recursively and that would keep the the results.

So we will create another function named list_Of_Elements_In_Second_List_But_Not_In_First_List’ (note the single quote at the end; it denotes the function’s difference from the original function, exactly as we use this symbol in variables’ names in Mathematics). This function is going to be recursive and take three arguments: i) the whole initial first list, ii) the remainder of the second list in the form n:ns, so the function can operate on the first element and be called recursively for the rest, and iii) outList, which keeps the result so far. Initially, we will call this function with the whole first list, the whole second list and the empty list [] as outList, since initially we have no results.

module Main where

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      let as = [1,2,3,100]
      let bs = [5,4,1,6,2,3,4]
      let cs = list_Of_Elements_In_Second_List_But_Not_In_First_List as bs
      print cs
      putStrLn "Program ends."

list_Of_Elements_In_Second_List_But_Not_In_First_List      :: Eq a => [a] -> [a] -> [a]
list_Of_Elements_In_Second_List_But_Not_In_First_List ks ls = list_Of_Elements_In_Second_List_But_Not_In_First_List' ks ls []
   where
      list_Of_Elements_In_Second_List_But_Not_In_First_List'                  :: Eq a => [a] -> [a] -> [a] -> [a]
      list_Of_Elements_In_Second_List_But_Not_In_First_List' [] _      outList = outList
      list_Of_Elements_In_Second_List_But_Not_In_First_List' _  []     outList = outList
      list_Of_Elements_In_Second_List_But_Not_In_First_List' ms (n:ns) outList =
         if elem n ms
            then list_Of_Elements_In_Second_List_But_Not_In_First_List' ms ns outList
            else list_Of_Elements_In_Second_List_But_Not_In_First_List' ms ns (outList ++ [n])

Great. Our program works nicely. Try it.

Now, Haskell provides us a lot of tools, especially tools to work with lists. Thus, usually we can avoid writing a lot of code or “reinventing the wheel”, if we just think carefully and research what it is that Haskell provides.

Indeed, we can save valuable time if we use Haskell’s filter for lists. We can give the filter a lambda (anonymous function) and a list and it will return the filtered list to us. In our case, the anonymous function should check if the value given to it is an element of the first list. Since the filter will call the lambda with each element of the list we provide, we should provide the second list and our job will be done.

module Main where

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      let as = [1,2,3,100]
      let bs = [5,4,1,6,2,3,4]
      let cs = list_Of_Elements_In_Second_List_But_Not_In_First_List as bs
      print cs
      putStrLn "Program ends."

list_Of_Elements_In_Second_List_But_Not_In_First_List      :: Eq a => [a] -> [a] -> [a]
list_Of_Elements_In_Second_List_But_Not_In_First_List ks ls = filter (\x -> notElem x ks) ls

And since all our work is done in one line, we may want to do away with creating a whole function for something that Haskell makes so easy. Thus:

module Main where

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      let as = [1,2,3,100]
      let bs = [5,4,1,6,2,3,4]
      let cs = filter (\x -> notElem x as) bs
      print cs
      putStrLn "Program ends."

Finishing, I would like to give you a bonus. Here is a program that finds the gamut of similarities and differences between two lists:

module Main where

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      let as = [1,2,3,100]
      let bs = [5,4,1,6,2,3,4]

      putStrLn "First list (as):"
      print as
      putStrLn "Second list (bs):"
      print bs

      putStrLn "Elements in the second list (bs) that are also in the first list (as):"
      let cs1 = filter (\x -> elem x as) bs
      print cs1

      putStrLn "Elements in the second list (bs) that are not in the first list (as):"
      let cs2 = filter (\x -> notElem x as) bs
      print cs2

      putStrLn "Elements in the first list (as) that are also in the second list (bs):"
      let cs3 = filter (\x -> elem x bs) as
      print cs3

      putStrLn "Elements in the first list (as) that are not in the second list (bs):"
      let cs4 = filter (\x -> notElem x bs) as
      print cs4

      putStrLn "Program ends."
Advertisements

About Dimitrios Kalemis

I am a systems engineer specializing in Microsoft products and technologies. I am also an author. Please visit my blog to see the blog posts I have written, the books I have written and the applications I have created. I definitely recommend my blog posts under the category "Management", all my books and all my applications. I believe that you will find them interesting and useful. I am in the process of writing more blog posts and books, so please visit my blog from time to time to see what I come up with next. I am also active on other sites; links to those you can find in the "About me" page of my blog.
This entry was posted in Development. Bookmark the permalink.