fold over elem?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

fold over elem?

Logesh Pillay-3
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?

Reply | Threaded
Open this post in threaded view
|

Re: fold over elem?

Heinrich Apfelmus
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

Reply | Threaded
Open this post in threaded view
|

fold over elem?

Daniel Fischer-4
In reply to this post by Logesh Pillay-3
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


Reply | Threaded
Open this post in threaded view
|

fold over elem?

anymane

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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners