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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
