# Singleton

A perhaps surprising thing to learn as we learn about programming is that there are a lot of different kinds of lists, all representing the same conceptual notion – a list is a collection of things arranged in a particular order – but with different performance properties. Whether computing’s menagerie of lists is a source of fascination or of annoyance depends on your interests, but regardless the varieties of lists are there and we must choose among them whenever we desire to line things up in a row.

Take, for example, the `Seq` type in the `containers` package. This is an ingenious data structure that serves a number of purposes well; notably, it supports quite efficient concatenation.

Whereas Haskell’s built-in list type `[]`The `Data.List` module contains many of the basic operations for dealing with lists. has the advantage of being incredibly concise in its definition,

``data [] a = [] | a : [a]``

the `Seq` type pays for its particular performance advantages with a good deal of clever trickery. The data constructors for `Seq` are therefore hidden away from us, because `Seq` only behaves as advertised when its values are constructed via the particular algorithms implemented within the `containers` package. If we were given free reign to muck about with the low-level constructors ourselves, we would have to worry about how finger trees Finger Trees: A Simple General-purpose Data Structure by Ralf Hinze and Ross Paterson, 2006. work. Instead the details are encapsulated by the `Data.Sequence` module and we are freed to just think of a `Seq` as a fancy type of list.

If `Data.Sequence` does not provide us with constructors for `Seq`, then how do we obtain values of the `Seq` type? Other functions! Remember that constructors are functions. List has two constructors:

1. `[] :: [a]`
2. `(:) :: a -> [a] -> [a]`

A constructor for some datatype returns a value of that type. For example, notice that both `[]` and `(:)` produce a result of type `[a]`. They are the constructors for the list type, so they produce lists. But the constructors are not the only functions that can produce a list! They are merely the most fundamental such functions. All other functions are based on those two, they use them in some way. For example, we could write a function like this one:

``````singleton :: a -> [a]
singleton x = (:) x []``````

This definition happens to be written using both of the list constructors, `[]` and `(:)`. We could, equivalently, use the special list syntax to write:

``````singleton :: a -> [a]
singleton x = [x]``````

From the perspective of someone who is just trying to make a list, it doesn’t matter that the `(:)` function is a constructor and `singleton` is not. Any function will do; it doesn’t have to be a constructor. All that concerns us is that, if we want to make a list, once we’ve defined the `singleton` function we now have three tools for doing so:

1. `[] :: [a]`
2. `(:) :: a -> [a] -> [a]`
3. `singleton :: a -> [a]`

And, of course, there are many more, as you can see by browsing the `Data.List` module (although `singleton` does not happen to be one of the tools included there).

If you browse the `Data.Sequence` module, however, you do see a function named `singleton` among the choices.`singleton` in `Data.Sequence`

``singleton :: a -> Seq a``

Why is it that `Data.Sequence` has a `singleton` function and `Data.List` does not? Indeed we do not need to have the `singleton` function be given to us by `Data.Sequence`. The module includes the following two functions which are analogous to the list constructors:

1. `empty :: Seq a`
2. `(<|) :: a -> Seq a -> Seq a`

And using those, we could write the `singleton` for `Seq` ourselves, just like we wrote the `singleton` for lists.

``````import Data.Sequence (Seq)
import qualified Data.Sequence as Seq

singleton :: a -> Seq a
singleton x = (Seq.<|) x Seq.empty``````

So, then, why? If we may be bold enough to offer some speculation:

1. It may be because the authors of the `Data.Sequence` module,We might suggest that in general a module which exports a type but does not export its constructors tends to incur some increased obligation to provide a wider buffet of functions in compensation. being able to use the secret `Seq` constructors that are forbidden to us outside the module, are able to write a more efficient `singleton` function than the one we wrote above, and this is not the case for the `[]` type.

2. It may be because the authors of the `Data.List` module want to encourage you to look at the `[]` list type in a particular light,If emphasizing the constructors was indeed ever anyone’s aim, it seems to be overwhelmingly defeated by the fact that we construct lists using the special bracket syntax, not visibly employing the `(:)` constructor, the majority of the time. to always keep the data constructors and therefore the list’s structure in mind. By denying us high-level conveniences, a library author may attempt to coerce us into thinking about their concept in the “proper” way.

The lack of a `singleton` function certainly does, however, make the `Data.List` module a pariah among comparable libraries. In addition to `Seq` as we have already discussed, we can also look at `Vector``singleton` in `Data.Vector` (a finite list packed contiguously in memory) and `DList``singleton` in `Data.DList` (a simple “list-builder” type supporting efficient concatenation).

• `singleton :: a -> Vector a`
• `singleton :: a -> DList a`

In addition to lists, we can broaden our view to a notion sometimes described as “collections” – types whose purpose is to represent some multiplicity of elements, but with different flavors. For example,

• A set is like a list that does not place its elements into any particular order, and in which no element occurs in the collection more than once.
• A mapMaps actually share a lot more in common with sets than they do with lists. has a second type that serves as the key, and each value of the key type is associated with at most one element of the collection.

Sets`singleton` in `Data.Set` and maps`singleton` in `Data.Map.Lazy` have `singleton` functions in the `containers` library:

• `singleton :: a -> Set a`
• `singleton :: k -> a -> Map k a`

As do the corresponding set`singleton` in `Data.HashSet` and map`singleton` in `Data.HashMap.Lazy` types in the `unordered-containers` library:

• `singleton :: a -> HashSet a`
• `singleton :: Hashable k => k -> a -> HashMap k a`

Note that the `singleton` functions for maps are a little different, because they have that extra `k` parameter. But, when partially applied to one argument, it starts to feel very similar again.

``````λ> :type singleton 'x'
singleton 'x' :: a -> Map Char a``````

So far we have discussed collections that can hold any With the subtle exceptions of `Set` and `HashSet`, which require their elements to have an `Ord` or a `Hashable` instance, respectively. type of element. Various libraries also provide more specialized collections, typically with some performance benefit gained by tuning the data structure in some way particular to the element type. For example, the `Text` type`singleton` in `Data.Text` represents a list of characters as their UTF-16 encoding, and a `ByteString``singleton` in `Data.ByteString` is implemented using FFI. Among these types as well,`singleton` in `Data.ByteString.Char8` the convention`singleton` in `Data.IntSet` of having a function named `singleton` is strong.

• `singleton :: Char -> Text`
• `singleton :: Word8 -> ByteString`
• `singleton :: Char -> ByteString`
• `singleton :: Int -> IntSet`

Many of the types of lists we have discussed here are nicely wrapped up by the multi-parameter typeclass called `ListLike`. This class contains a number of methods for functions that all list-resembling types have, including our simple friend `singleton`.`singleton` in `Data.ListLike`

• `singleton :: ListLike full item => item -> full`
``````λ> import Data.ListLike

λ> singleton "x" :: [String]
["x"]``````

Join Type Classes for courses and projects to get you started and make you an expert in FP with Haskell.