[fixed some typos, mainly missing primes]
superset xs = superset' x . sort where x = sort xs
_ `superset'` [] = True [] `superset'` _ = False (x:xs) `superset'` (y:ys) | x == y = xs `superset'` ys | x < y = xs `superset'` (y:ys) | otherwise = False
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
The algorithm is correct but it's not faster, xs `super` ys takes O(n*m) time whereas superset takes O(n * log n + m * log m) time given a proper sorting algorithm. Here, n = length xs and m = length ys.
Of course, you are right. In worst case super is much slower than superset. In average case (for some assumptions about the inputs) it could perform quite well because of the chance to detect non-subset words early.
2) Put xs into a good data structure and achieve a O(m * log n) time for multiple ys.
You mean something along supermap xs = let mx = Map.fromListWith (+) [ (x,1) | x <- xs ] ins _ 1 = Nothing ins _ v = Just (v-1) upd m y = case Map.updateLookupWithKey ins y m of (Nothing,_ ) -> mzero (_ ,m') -> return m' in not . null . foldM upd mx Thanks for your time, BR, -- -- Mirko Rahn -- Tel +49-721 608 7504 -- --- http://liinwww.ira.uka.de/~rahn/ ---