[Haskell-beginners] fold over elem?
anishmuttreja at gmail.com
Sat Sep 20 13:36:06 EDT 2008
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.
> Beginners mailing list
> Beginners at haskell.org
More information about the Beginners