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?
Logesh Pillay wrote:
I want to check if all the numbers in a list A are elements of a bigger unordered list B.
bs `contains` as = all (`elem` bs) as
Is there some way to fold /A into elem /B?
I don't quite understand what you want to do, can you elaborate? Regards, apfelmus
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. Cheers, Daniel
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@haskell.org http://www.haskell.org/mailman/listinfo/beginners
participants (4)
-
Anish Muttreja -
apfelmus -
Daniel Fischer -
Logesh Pillay