Non-minimal edit distance algorithm in Haskell

Edit.hs

module Edit where

import Data.Maybe (isNothing)
import Test.QuickCheck (Property, (==>))

-- |Edit algebra: add, remove, or replace characters
data Edit a
  = Add a
  | Rm a
  | Replace a a deriving (Eq, Show)

parse :: [a] -> [a] -> [Edit a]
parse = go
  where go (s:ss) (t:ts) = Replace s t : go ss ts
        go [] (t:ts) = Add t : go [] ts
        go (s:ss) [] = Rm s : go ss []
        go [] [] = []

edit :: Eq a => [a] -> [Edit a] -> Maybe [a]
edit xs' is' = sequence $ go xs' is'
  where go :: Eq a => [a] -> [Edit a] -> [Maybe a]
        go (x:xs) (Replace i1 i2:is) =
          if i1 == x then Just i2 : go xs is else [Nothing]
        go [] (Replace _ _:_) = [Nothing]
        go [] (Add i:is) = Just i : go [] is
        go (_:_) (Add _:_) = [Nothing]
        go (x:xs) (Rm i:is) = if i == x then go xs is else [Nothing]
        go [] (Rm _:_) = [Nothing]
        go (_:_) [] = [Nothing]
        go [] [] = []

-- |After parsing x -> y, we should be able to get to y given x
prop_editWithSrcAfterParseIsTgt :: Eq a => [a] -> [a] -> Bool
prop_editWithSrcAfterParseIsTgt x y =
  edit x (parse x y) == Just y

-- |After parsing with x -> y, given a (z /= x), an edit should yield Nothing
prop_editWithoutSrcAfterParseIsNothing :: Eq a => [a] -> [a] -> [a] -> Property
prop_editWithoutSrcAfterParseIsNothing x y z =
  (x /= z) ==> isNothing (edit z (parse x y))