Empty list - Beginners - Haskell.org

newer
Monoids and Groups

Empty list

older
Type Parameters and Type Variables

Shishir Srivastava

25 Mar 2015 25 Mar '15

9:55 a.m.

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

Attachments:

attachment.html (text/html — 699 bytes)

Reply

Sign in to reply online Use email software

Show replies by date

Norbert Melzer

25 Mar 25 Mar

10 a.m.

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@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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Reply

Sign in to reply online Use email software

Brandon Allbery

10:03 a.m.

On Wed, Mar 25, 2015 at 10:00 AM, Norbert Melzer 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@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

Reply

Sign in to reply online Use email software

Joel Williamson

10:10 a.m.

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 wrote:

On Wed, Mar 25, 2015 at 10:00 AM, Norbert Melzer 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@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Reply

Sign in to reply online Use email software

Mike Meyer

10:11 a.m.

On Wed, Mar 25, 2015 at 9:03 AM, Brandon Allbery wrote:

On Wed, Mar 25, 2015 at 10:00 AM, Norbert Melzer 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

Reply

Sign in to reply online Use email software

Mike Meyer

10:07 a.m.

On Wed, Mar 25, 2015 at 8:55 AM, Shishir Srivastava < shishir.srivastava@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 {{}}.

Reply

Sign in to reply online Use email software

Max Voit

10:12 a.m.

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

Sign in to reply online Use email software

Joel Neely

26 Mar 26 Mar

7:54 a.m.

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@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@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

Reply

Sign in to reply online Use email software

3708

Age (days ago)

3709

Last active (days ago)

Download

7 comments

7 participants

tags

participants (7)

Brandon Allbery
Joel Neely
Joel Williamson
Max Voit
Mike Meyer
Norbert Melzer
Shishir Srivastava