diff in Haskell: clarification

[George Russell]

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.