listDiff.hs

import qualified Data.Set as Set

old = ['A', 'B', 'C']
current = ['B', 'D', 'E', 'E', 'D']

-- diff old current = (['A', 'C'], ['D', 'E'])
-- to remove: ['A', 'C']
-- to add: ['D', 'E']

diff [] [] = ([], [])
diff old current = diff' current (Set.fromList old) Set.empty []

diff' :: Ord a => [a] -> Set.Set a -> Set.Set a -> [a] -> ([a], [a])
diff' [] oldSet _ toAdd = (Set.elems oldSet, toAdd)
diff' (x:xs) oldSet nextSet toAdd =
    let
        (oldSet', toAdd')
          | Set.member x oldSet = (Set.delete x oldSet, toAdd)
          | Set.member x nextSet = (oldSet, toAdd)
          | otherwise = (oldSet, x:toAdd)

        nextSet' = Set.insert x nextSet
    in
        diff' xs oldSet' nextSet' toAdd'

main = do
    print $ diff old current