# Haskell union list implementation pt 2

This is my revision from another post

union' :: (Eq a) => [a] -> [a] -> [a]
union' [] list = list
union' (x:xs) list
| not \$ x elem list = x : union' xs list
| otherwise = union' xs list


Any suggestions welcome.

If this is a question, let's check whether you actually reinvented union:

import Data.List (union)
import Test.QuickCheck

union' :: (Eq a) => [a] -> [a] -> [a]
union' = ...

prop_union :: [Int] -> [Int] -> Property
prop_union xs ys = union' xs ys === union xs ys

main = quickCheck prop_union


It will fail after some tests:

*** Failed! Falsifiable (after 4 tests and 2 shrinks):
[]
[1,1]
[1,1] /= [1]

While your union' returned [1,1] on [] [1,1], Data.List.union returned [1]. That's because it's left-biased. In order to actually reinvent the wheel, you need to get rid of duplicates on the second list:

union' :: Eq a => [a] -> [a] -> [a]
union' xs [] = xs
union' [] ys = nub ys


But it gets weirder. While the left hand side is allowed to have duplicates, elements on the right hand side that were already in the left hand side need to get discarded:

union "Hello" "World" == "HelloWrd"


union' "Hello" "World" == "HeWorld"


Your version is right-biased. The original list xs should be contained completely:

union' xs ys = xs ++ deleteDuplicatesAndXSElements ys


The deleteDuplicatesAndXSElements is left as an exercise. If you define it correctly, you can get rid of all the other cases.

By the way, I don't agree with the previous answer concerning ++. Appending is a problem if you do it over and over again, since (a ++ b) ++ c will have quadratic runtime instead of linear with a ++ (b ++ c), but here you're doing it once.

Last but not least, don't use not .. elem. notElem is a function in Prelude.