2
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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"

However, your current version discards elements from the left hand side:

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.