Simple Diff

gistfile1.hs

data Edit a
    = Insert a
    | Delete a
    | Same   a 
    deriving (Show, Eq)
    
isSame :: Edit a -> Bool
isSame x = case x of
  Insert {} -> False
  Delete {} -> False
  Same   {} -> True

diff :: Eq a => [a] -> [a] -> [Edit a]
diff [] ys = map Insert ys
diff xs [] = map Delete xs
diff (x : xs) (y : ys) 
  | x == y    = Same x : diff xs ys
  | otherwise = 
    let dx = diff (x : xs) ys
        dy = diff xs       (y : ys)
    in if length (filter isSame dx) < length (filter isSame dy) then
          Delete x : dy
       else
          Insert y : dx