[Haskell-beginners] fold over elem?

[Anish Muttreja]

On Fri, Sep 19, 2008 at 08:04:03PM +0200, Daniel Fischer wrote:
> Am Freitag, 19. September 2008 19:32 schrieb Logesh Pillay:
> > I want to check if all the numbers in a list A are elements of a bigger
> > unordered list B.
> >
> > Is there some way to fold  /A into elem /B?
> >
> 
> I suppose what you want is an efficient way to check if all elements of A also 
> belong to B?
> I think if the type of elements belongs to Ord, your best bet, if B is large 
> but not huge, is to sort B or build a Set from it and exploit the faster 
> membership tests. If B is huge (or even infinite), that could require too 
> much memory.

Sorting B and looking up elements of A in it would be O(b*log b) + O(a * log b), b = |B| and a = |A|.  So, if a is much smaller than b, it may be better to sort list A and look up elements of A in it. In either case, sort the smaller list.

Cheers,
Anish

> 
> Cheers,
> Daniel
> 
> 
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners