Mirko Rahn wrote:
wanted ws = [ (w,v) | (w:vs) <- tails ws, v <- vs, difference w v < 2 ]
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.
Note that using Peano-numbers can achieve the same effect of stopping the length calculation as soon as more than one character is different. data Nat = Zero | Succ Nat deriving (Eq, Ord) instance Num Nat where (Succ x) + y = Succ (x+y) Zero + y = y fromInteger 0 = Zero fromInteger n = Succ $ fromInteger (n-1) difference :: Pair -> Nat difference = Data.List.genericLength . filter not . uncurry (zipWith (==)) wanted ws = [ (w,v) | (w:vs) <- tails ws, v <- vs, difference w v <= 1 ] Regards, apfelmus