# [Haskell-cafe] Practise fingerspelling with Haskell! (Code cleanup request)

Mirko Rahn rahn at ira.uka.de
Thu Jul 19 05:27:46 EDT 2007

```Just some remarks:

> difference = length . filter (==False) . uncurry (zipWith (==))

Maybe

difference = length . filter id . uncurry (zipWith (/=))

or even

difference w = length . filter id . zipWith (/=) w

and defer the call of uncurry. We then have

keepOneDiff = filter ((< 2) . uncurry difference)

[Clearly the last version has a point...]

But once having done this, we see, that we construct the pair in
listPairs and deconstruct it in keepOneDiff. While this is perfectly
valid (and good practice to separate the concerns), in the concrete
setting one could write

wanted ws = [ (w,v) | (w:vs) <- tails ws, v <- vs, difference w v < 2 ]

and thus only create the pairs when necessary. Moreover, we only
calculate the difference to check whether it is smaller than 2. We can
do this directly (capturing the common pattern):

diff_lt_2 = diff (diff (const . const \$ False))

diff _ []     []     = True
diff f (x:xs) (y:ys) = if x == y then diff f xs ys else f xs ys
diff _ _ _           = error "length xs /= length ys!?"

We now have

wanted ws = [ (w,v) | (w:vs) <- tails ws, v <- vs, diff_lt_2 w v ]

This modification boosts performance a lot, for example fingerspell 15
100 runs in 5.5 instead of 53 secs on my machine.

A last remark:

> requirements w = length w == wl && all (isAlpha) w

traverses w twice (although length does'nt touch the elements). One
could do this in one pass along the lines

req []      []                = True
req (_:ys) (x:xs) | isAlpha x = req ys xs
req _       _                 = False

requirements = req (replicate wl undefined)

Unfortunately this is slower, I guess it has something to do with the
use of the strict foldl' for length and with the fact that in
/usr/shar/dict/words there seems to be only words for which all isAlpha
returns True.

A very last sentence: The req given above is just an instance of an even
more general diff, so I finally reached the following:

import Data.List (tails)
import Data.Char (isAlpha)
import Control.Monad (liftM)

fingerspell wl p =
let okay = diff_eq_0 (replicate wl True) . map isAlpha
-- | faster in the concrete setting but not in general!?
-- let okay w = length w == wl && all isAlpha w
in liftM words (readFile "/usr/share/dict/words") >>=
mapM_ putStrLn . take p . wanted . filter okay

-- difference w = length . filter id . zipWith (/=) w
-- diff_le_1 w v == difference w v < 2

wanted ws = [ w++", "++v | (w:vs) <- tails ws, v <- vs, diff_le_1 w v ]
where diff_le_1 = diff (error "length w /= length v") diff_eq_0

diff g f (x:xs) (y:ys)
| x == y           = diff g f xs ys
| otherwise        =        f xs ys
diff g _    xs     ys  =      g   xs ys

diff_eq_0 :: Eq a => [a] -> [a] -> Bool
diff_eq_0 = diff (\ u v -> null u && null v) (const . const \$ False)

/BR

--
-- Mirko Rahn -- Tel +49-721 608 7504 --
--- http://liinwww.ira.uka.de/~rahn/ ---
```

More information about the Haskell-Cafe mailing list