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,

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:

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

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

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.

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 Vectorsingleton in Data.Vector (a finite list packed contiguously in memory) and DListsingleton 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.

Setssingleton in Data.Set and mapssingleton 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 setsingleton in Data.HashSet and mapsingleton 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 typesingleton in Data.Text represents a list of characters as their UTF-16 encoding, and a ByteStringsingleton in Data.ByteString is implemented using FFI. ForeignPtr Among these types as well,singleton in Data.ByteString.Char8 the conventionsingleton 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"]