Why is there no built-in Set data type in Haskell?

Question

Is there anyone who can explain to me why there's no Set datatype defined in Haskell?

Sidenote: I'm only learning Haskell as part of a course on logic in which set theory is very important thus it would be really handy to have the notion of a set in Haskell. Having a list and removing duplicates (and possibly sorting) would result in a set as well but I'm curious if there's a particular reason why it's not built-in?

Answer 1

As other answers indicate, the question "Why is there no Set data type in Haskell?" is misguided: there is a Set data type.

If you'd like to know why Set isn't "built in" to Haskell, you could be asking one of two things.

• Why is Set not part of the language specification?
• Why is Set not in Prelude (the functions and data types that are imported by default)?

To answer the former, it is because the language is powerful enough to express the idea of a set without needing to bake it in. Being a language with a high emphasis on functional programming, special syntax for tuples and lists is built in, but even simple data types like Bool are defined in Prelude.

To answer the latter, well, again, with the emphasis on functional programming, most Haskellers tend to use lists. The list monad represents nondeterministic choice, and by allowing duplicates, you can sort of represent weighted choices.

Note how similar list comprehension syntax is to set notation. You can always use Set.fromList to convert a list into a "real" set, if necessary. As a begrudging shout out to Barry, this would be similar to using Python's set() method; Python has list comprehensions as well.

Answer 2

On a more philosophical level --- there can't ever be a strict correspondence between the mathematical concept of a set and a Haskell set implementation. Why not? Well, the type system, for starters. A mathematical set can have anything at all in it: {x | x is a positive integer, i < 15} is a set, but so is {1, tree, ham sandwich}. In Haskell, a Set a will need to hold some particular type. Putting Doubles and Floats into the same set won't typecheck.

As others have said, if you need to do some set-like things and don't mind the type restriction, Data.Set exists. It's not in Prelude because lists are usually more practical. But really, from a language design perspective, it doesn't make sense to think of mathematical sets as one datatype among many. Sets are more fundamental than that. You don't have sets, and numbers, and lists; you have sets of numbers, and sets of lists. The power of recursive types tends to obscure that distinction, but it's still real.

There is a place in Haskell, though, where we define arbitrary collections, and then define functions over those collections. The closest analog of the mathematical concept of sets in Haskell is the type system itself.