[Haskell-beginners] subset - a little add
daniel.is.fischer at web.de
Fri Jan 29 04:06:29 EST 2010
Am Freitag 29 Januar 2010 08:36:35 schrieb Luca Ciciriello:
> Just a little add to may previous mail.
> The solution I've found from myself is:
> subset :: [String] -> [String] -> Bool
> subset xs ys = and [elem x ys | x <- xs]
subset xs ys = all (`elem` ys) xs
but is that really what you want? That says subset [1,1,1,1]  ~> True.
If you regard your lists as representatives of sets (as the name suggests),
then that's correct, otherwise not.
However, this is O(length xs * length ys). If you need it only for types
belonging to Ord, a much better way is
import qualified Data.Set as Set
import Data.Set (fromList, isSubsetOf, ...)
subset xs ys = fromList xs `isSubsetOf` fromList ys
or, if you don't want to depend on Data.Set,
subset xs ys = sort xs `isOrderedSublistOf` sort ys
xxs@(x:xs) `isOrderedSublistOf` (y:ys)
| x < y = False
| x == y = xs `isOrderedSublistOf` ys
| otherwise = xxs `isOrderedSublistOf` ys
 `isOrderedSublistOf` _ = True
_ `isOrderedSublistOf`  = False
> My question is if exists a more elegant way to do that.
More information about the Beginners