[Haskell-cafe] Re: Practise fingerspelling with Haskell! (Code
apfelmus at quantentunnel.de
Wed Jul 18 12:16:55 EDT 2007
Dougal Stanton wrote:
> The following is a slap-dash program for generating a list of pairs of
> words which differ by, at most, one letter. It's quite verbose at the
> moment, because (a) that was the way I wrote it, a snippet at a time,
> and (b) I lack the wit to make it shorter.
> Can anyone recommend ways to make this program more
> efficient/neat/elegant? It runs in decent time on my machine, but it's
> not exceedingly pretty and I'm sure it can be made shorter too.
I like it for its elegant point-free style :)
> -- Number of letters difference between two words.
> difference :: Pair -> Int
> difference = length . filter (==False) . uncurry (zipWith (==))
Apparently, difference can only detect character replacements but not
character insertion or deletion, but that's probably not your use case.
> -- Pairs of words of equal length, sorted to reduce
> -- duplicates of (a,b), (b,a) type. They shouldn't
> -- be completely eradicated because part of the game
> -- is to spot when they;re the same word.
> listPairs :: WordSet -> PairSet
> listPairs ws = [ (w, w') | w <- ws, w' <- ws, length w == length w', w
> <= w' ]
You can avoid generating the superfluous half of the pairs by using tails
listPairs ws = [ (head ws', w')
| ws' <- tails ws, w' <- ws'
, let w = head ws', length w == length w']
Of course, grouping words by length first and pairing the resulting
groups is more efficient than filtering out all the pairs where length
w /= length w'. But you restrict fingerspell to a fixed word length
anyway, so it doesn't matter.
More information about the Haskell-Cafe