Home > Uncategorized > Word chains: efficient implementation of the rule set

Word chains: efficient implementation of the rule set

I continued to rewrite the neighbour test in the previous post. I had two, some what contradictary, goals

  • It should be efficient
  • It should match the definition more closely

This is my current version.

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

neighbours xs ys =
   case length xs - length ys of
     0  -> eval [change] || anagram xs ys
     1  -> eval [insert_ys,delete_xs]
     -1 -> eval [insert_xs,delete_ys]
     _  -> False
 where
    eval ops = any id $ unifyable ops (xs,ys)
    anagram xs ys = xs /= ys && sort xs == sort ys
    change (x:xs) (y:ys) = (xs,ys)
    insert_xs xs (y:ys) = (y:xs,ys)
    insert_ys (x:xs) ys = (xs,x:ys)
    delete_xs (x:xs) ys = (xs,ys)
    delete_ys xs (y:ys) = (xs,ys)

Except for the anagram test the test now has a rather efficient unification framework which uses replace, insert and delete operations to unify the two words. Not revolutionary but it was fun at least.

Advertisements
Categories: Uncategorized
  1. No comments yet.
  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: