[Haskell-beginners] subset - a little add

[Daniel Fischer]

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]
>

Variant:

subset xs ys = all (`elem` ys) xs

but is that really what you want? That says subset [1,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.
>
>
>
> Luca.