[Haskell-cafe] Re: Slower with ByteStrings?

[Mirko Rahn]

>>from the letters of that word.  A letter can be used at most as many
>>times as it appears in the input word.  So, "letter" can only match
>>words with 0, 1, or 2 t's in them.

>    frequencies = map (\x -> (head x, length x)) . group . sort
>    superset xs = \ys -> let y = frequencies ys in
>         length y == lx &&
>         and (zipWith (\(c,i) (d,j) -> c == d && i >= j) x y)
>       where
>       x  = frequencies xs
>       lx = length x

As far as I understand the spec, this algorithm is not correct:

superset "ubuntu" "tun" == False

Is at least one 'b' necessary, yes or no? If the answer is no, the 
following algorithm solves the problem and is faster then the one above:

del y = del_acc []
     where del_acc _ []              = mzero
	  del_acc v (x:xs) | x == y = return (v++xs)
	  del_acc v (x:xs)          = del_acc (x:v) xs

super u = not . null . foldM (flip del) u

main = interact $ unlines . filter ("ubuntu" `super`) . lines

BR,

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