Home > Uncategorized > Word chains: a unified framework for neighbour (equivalence) testing

Word chains: a unified framework for neighbour (equivalence) testing

In the previous post the anagram test was separate from the others and not expressed in operations/transformations. I worked on this a bit and this is where I ended up

data Operation = Change | InsertXs | InsertYs | DeleteXs | DeleteYs | ReOrder

getf Change   = \(x:xs) (y:ys)   -> ([],xs,ys)
getf InsertXs = \xs     ys@(y:_) -> ([],y:xs,ys)
getf InsertYs = \xs@(x:_) ys     -> ([],xs,x:ys)
getf DeleteXs = \(x:xs) ys       -> ([],xs,ys) 
getf DeleteYs = \xs     (y:ys)   -> ([],xs,ys)
getf ReOrder  = \(x:xs)   ys     ->
                    case mkHead x ys [] of
                        Just ys' -> ([ReOrder],xs,ys')
                        _ -> ([],x:xs,ys)
            where
                mkHead _ []     _  = Nothing
                mkHead h (x:xs) ys 
                    | h == x    = Just (xs ++ ys) 
                    | otherwise = mkHead h xs (x:ys)

unifyable args =
    case args of
        (_, [], [])                -> return True
        (ops, x:xs, y:ys) | x == y -> unifyable (ops,xs,ys)
        (ops, xs, ys)              -> do { op <- ops; unifyable ((getf op) xs ys) }

neighbours xs ys = any id $ unifyable (operations, xs, ys)
    where 
        operations = 
            case length xs - length ys of
                0  -> [Change,ReOrder]
                1  -> [InsertYs,DeleteXs]
                -1 -> [InsertXs,DeleteYs]
                _  -> []

Advertisements
Categories: Uncategorized
  1. May 2, 2015 at 7:21 pm

    Just realized that InsertXs and DeleteYs are equivalent (as well as InsertYs and DeleteXs ofcourse). (I realized this when I saw a bug in the insert implementation.) Operations does not have to specify both.

    operations =
    case length xs – length ys of
    0 -> [Change,ReOrder]
    1 -> [InsertYs]
    -1 -> [InsertXs]
    _ -> []

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: