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.
_______________________________________________
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
