Prevent repeat printing of common list variables Haskell-CodePudding

Currently, I am making a function that can take the values in two lists, compare them, and print any similar values. If a value is duplicated in both lists, it is not printed a second time.

EXAMPLE

INPUT: commons [1,2,2,3,4] [2,3,4,5,2,6,8]
EXPECTED OUTPUT: [2,3,4]

What I currently have causes a repeated values in both lists to repeat in the output. So, in the above example, the 2 would print twice.

Here is the current code I am working on:

commons :: Eq a => [a] -> [a] -> [a]
commons [] [] = []
commons x y = commons_Helper x y

commons_Helper :: Eq a => [a] -> [a] -> [a]
commons_Helper [] [] = []
commons_Helper x [] = []
commons_Helper [] y = []
commons_Helper (x:xs) y = 
    if elem x y then x : commons_Helper xs y
    else commons_Helper xs y

Any and all help would be greatly appreciated.

EDIT: This must remain as commons :: Eq a => [a] -> [a] -> [a], and I cannot import and libraries

CodePudding user response：

You could make your traversal of the xs list a stateful one, the state keeping track of elements that have been already seen. The state begins life as an empty list.

It is possible to do that by adding a 3rd parameter to your helper function, which currently is not very useful.

commons_Helper :: Eq a => [a] -> [a] -> [a] -> [a]
commons_Helper   []    ys  st  =  []
commons_Helper (x:xs)  ys  st  = 
    if (elem x ys  &&  (not $ elem x st))     -- extra test here
        then  x : (commons_Helper xs ys (x:st))
        else  commons_Helper xs ys st


commons :: Eq a => [a] -> [a] -> [a]
commons xs ys = commons_Helper xs ys []

This state-based technique is very common in Haskell. There is even a library function: mapAccumL :: (s -> a -> (s, b)) -> s -> [a] -> (s, [b]) to support it.