Edit distance monoid

distance.hs

import Data.Monoid
import Data.Function

class (Ord m, Monoid m) => Metric m where
  ins :: Int -> m
  del :: Int -> m
  delta :: Int -> Int -> m

distance :: Metric m => [Int] -> [Int] -> m
distance [] [] = mempty
distance [] (y:ys) = ins y `mappend` distance [] ys
distance (x:xs) [] = del x `mappend` distance xs []
distance (x:xs) (y:ys) = minimum
  [ ins y `mappend` distance (x:xs) ys
  , del x `mappend` distance xs (y:ys)
  , delta x y `mappend` distance xs ys
  ]

instance Monoid Int where
  mempty = 0
  mappend = (+)
  
instance Metric Int where
  ins _ = 5
  del _ = 5
  delta x y = abs (x - y)

data Step = Ins Int | Del Int | Delta Int deriving (Eq, Ord, Show)
data Edit m = Edit { metric :: m, steps :: [Step]  } deriving (Eq, Ord, Show)

instance Monoid m => Monoid (Edit m) where
  mempty = Edit mempty []
  Edit m1 e1 `mappend` Edit m2 e2 = Edit (m1 `mappend` m2) (e1 ++ e2)

instance Metric m => Metric (Edit m) where
  ins x = Edit (ins x) [Ins x]
  del x = Edit (del x) [Del x]
  delta x y = if (d == mempty) then mempty else Edit d [Delta (y - x)]
    where d = delta x y