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
Data.List module contains many of the basic operations for dealing with lists. has the advantage of being incredibly concise in its definition,
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.
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:
 :: [a]
(:) :: a -> [a] -> [a]
A constructor for some datatype returns a value of that type. For example, notice that both
(:) 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,
(:). 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:
 :: [a]
(:) :: a -> [a] -> [a]
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.
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:
empty :: Seq a
(<|) :: a -> Seq a -> Seq a
And using those, we could write the
Seq ourselves, just like we wrote the
singleton for lists.
So, then, why? If we may be bold enough to offer some speculation:
It may be because the authors of the
Data.Sequencemodule,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
Seqconstructors that are forbidden to us outside the module, are able to write a more efficient
singletonfunction than the one we wrote above, and this is not the case for the
It may be because the authors of the
Data.Listmodule 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
Data.Vector (a finite list packed contiguously in memory) and
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.
singleton :: a -> Set a
singleton :: k -> a -> Map k a
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.
So far we have discussed collections that can hold any With the subtle exceptions of
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
Data.Text represents a list of characters as their UTF-16 encoding, and a
Data.ByteString is implemented using FFI.
ForeignPtr Among these types as well,
Data.ByteString.Char8 the convention
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 :: ListLike full item => item -> full