Since various people seem to have misunderstood the problem, I shall try to state it more precisely. What is required is a function diff :: Ord a -> [a] -> [a] -> [DiffElement a] for the type data DiffElement a = InBoth a | InFirst a | InSecond a such that given the functions f1 (InBoth a) = Just a f1 (InFirst a) = Just a f1 (InSecond a) = Nothing and f2 (InBoth a) = Just a f2 (InFirst a) = Nothing f2 (InSecond a) = Just a the following identities hold: mapPartial f1 (diff l1 l2) == l1 and mapPartial f2 (diff l1 l2) == l2 This is a well-known problem. The most helpful Web page I could find about it is here: http://apinkin.net/space/DifferenceEngine There is an algorithm known as Myer's algorithm, but obviously I want it in Haskell rather than C, and it would be nice if someone else had written it so I don't have to.