Empty list

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

Empty list

Shishir Srivastava
Hi,

Can someone please explain why this results in error -

[] `elem` [1,2,3]

Shouldn't the empty set by definition be the element of all sets including
a non-empty set ?

I am assuming 'Lists' are different from 'Sets' in Haskell, if yes, is
there a separate module for dealing/working with sets ?

Thanks,
Shishir Srivastava
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150325/dbaed094/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Empty list

Norbert Melzer
You are correct, a list is not a set. A list is a list of things, that can
be there multiple times. A set is a set of things, where nothing can be
twice. So take a look at Data.Set
Am 25.03.2015 14:55 schrieb "Shishir Srivastava" <
shishir.srivastava at gmail.com>:

> Hi,
>
> Can someone please explain why this results in error -
>
> [] `elem` [1,2,3]
>
> Shouldn't the empty set by definition be the element of all sets including
> a non-empty set ?
>
> I am assuming 'Lists' are different from 'Sets' in Haskell, if yes, is
> there a separate module for dealing/working with sets ?
>
> Thanks,
> Shishir Srivastava
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150325/6de1bf19/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Empty list

Brandon Allbery
On Wed, Mar 25, 2015 at 10:00 AM, Norbert Melzer <timmelzer at gmail.com>
wrote:

> You are correct, a list is not a set. A list is a list of things, that can
> be there multiple times. A set is a set of things, where nothing can be
> twice. So take a look at Data.Set
>

Note that this won't actually solve the original problem; Haskell is an
implementation of a strongly typed lambda calculus, not of number theory,
and Haskell collections cannot (easily) contain elements of different types
--- so the empty set is not an element of a set, and the empty list is not
an element of a list.

--
brandon s allbery kf8nh                               sine nomine associates
allbery.b at gmail.com                                  ballbery at sinenomine.net
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150325/df63ef58/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Empty list

Mike Meyer
In reply to this post by Shishir Srivastava
On Wed, Mar 25, 2015 at 8:55 AM, Shishir Srivastava <
shishir.srivastava at gmail.com> wrote:

> Hi,
>
> Can someone please explain why this results in error -
>
> [] `elem` [1,2,3]
>
> Shouldn't the empty set by definition be the element of all sets including
> a non-empty set ?
>

Norbert gave you the information about Lists and Data.Set, but you're wrong
about the properties of the empty set. The empty set is a SUBSET of all
sets. But it's only a MEMBER of supersets of {{}}.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150325/18b6c450/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Empty list

Joel Williamson
In reply to this post by Brandon Allbery
Shishir, you need to distinguish between membership (1 is an element of
[1,2,3], [] is not) and subsets (both [1] and [] are subsets of [1,2,3]).
elem checks the first property, intersection checks the second.

On Wed, 25 Mar 2015 10:03 Brandon Allbery <allbery.b at gmail.com> wrote:

> On Wed, Mar 25, 2015 at 10:00 AM, Norbert Melzer <timmelzer at gmail.com>
> wrote:
>
>> You are correct, a list is not a set. A list is a list of things, that
>> can be there multiple times. A set is a set of things, where nothing can be
>> twice. So take a look at Data.Set
>>
>
> Note that this won't actually solve the original problem; Haskell is an
> implementation of a strongly typed lambda calculus, not of number theory,
> and Haskell collections cannot (easily) contain elements of different types
> --- so the empty set is not an element of a set, and the empty list is not
> an element of a list.
>
> --
> brandon s allbery kf8nh                               sine nomine
> associates
> allbery.b at gmail.com
> ballbery at sinenomine.net
> unix, openafs, kerberos, infrastructure, xmonad
> http://sinenomine.net
>  _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150325/a5187d43/attachment-0001.html>

Reply | Threaded
Open this post in threaded view
|

Empty list

Mike Meyer
In reply to this post by Brandon Allbery
On Wed, Mar 25, 2015 at 9:03 AM, Brandon Allbery <allbery.b at gmail.com>
wrote:

> On Wed, Mar 25, 2015 at 10:00 AM, Norbert Melzer <timmelzer at gmail.com>
> wrote:
>
>> You are correct, a list is not a set. A list is a list of things, that
>> can be there multiple times. A set is a set of things, where nothing can be
>> twice. So take a look at Data.Set
>>
>
> Note that this won't actually solve the original problem; Haskell is an
> implementation of a strongly typed lambda calculus, not of number theory,
> and Haskell collections cannot (easily) contain elements of different types
> --- so the empty set is not an element of a set, and the empty list is not
> an element of a list.
>

Did you forget a couple of "necessarily"'s?

Prelude Data.Set> [] `elem` [[]]
True
Prelude Data.Set> empty `member` (insert empty empty)
True
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150325/7ff0cf94/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Empty list

Max Voit-2
In reply to this post by Shishir Srivastava
Hi Shishir,

(in the following I'm ignoring the problem that lists have order and
elements may be in there multiple times)

On Wed, 25 Mar 2015 13:55:11 +0000
Shishir Srivastava <shishir.srivastava at gmail.com> wrote:

> Shouldn't the empty set by definition be the element of all sets
> including a non-empty set ?

This is not even true in the mathematical sense. True are:
        a) all power sets include the empty set as an *element*
        b) the empty set is a *subset* of all sets

For case (a) you'd need a list of lists since a powerset is a set of
sets.
For (b) `elem` is not the correct function.

Max

Reply | Threaded
Open this post in threaded view
|

Empty list

Joel Neely
In reply to this post by Shishir Srivastava
Given the distinction between lists and sets, you might also consider

Prelude Data.Set Data.List> [] `isInfixOf` [1,2,3]
True
Prelude Data.Set Data.List> (fromList []) `isSubsetOf` (fromList [1,2,3])
True

Of course `isInfixOf` is in general more restrictive than `isSubsetOf`, in
the sense that the infix relationship depends on ordering, which the subset
relationship does not.

Hope that helps,

-jn-



On Wed, Mar 25, 2015 at 8:55 AM, Shishir Srivastava <
shishir.srivastava at gmail.com> wrote:

> Hi,
>
> Can someone please explain why this results in error -
>
> [] `elem` [1,2,3]
>
> Shouldn't the empty set by definition be the element of all sets including
> a non-empty set ?
>
> I am assuming 'Lists' are different from 'Sets' in Haskell, if yes, is
> there a separate module for dealing/working with sets ?
>
> Thanks,
> Shishir Srivastava
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>


--
Beauty of style and harmony and grace and good rhythm depend on simplicity.
- Plato
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150326/2f53f259/attachment.html>