.. _overloaded-lists:
Overloaded lists
----------------
.. extension:: OverloadedLists
:shortdesc: Enable overloaded lists.
:since: 7.8.1
Enable overloaded list syntax (e.g. desugaring of lists via the
``IsList`` class).
GHC supports *overloading of the list notation*. Let us recap the
notation for constructing lists. In Haskell, the list notation can be
used in the following seven ways:
::
[] -- Empty list
[x] -- x : []
[x,y,z] -- x : y : z : []
[x .. ] -- enumFrom x
[x,y ..] -- enumFromThen x y
[x .. y] -- enumFromTo x y
[x,y .. z] -- enumFromThenTo x y z
When the ``OverloadedLists`` extension is turned on, the aforementioned
seven notations are desugared as follows:
::
[] -- fromListN 0 []
[x] -- fromListN 1 (x : [])
[x,y,z] -- fromListN 3 (x : y : z : [])
[x .. ] -- fromList (enumFrom x)
[x,y ..] -- fromList (enumFromThen x y)
[x .. y] -- fromList (enumFromTo x y)
[x,y .. z] -- fromList (enumFromThenTo x y z)
This extension allows programmers to use the list notation for
construction of structures like: ``Set``, ``Map``, ``IntMap``,
``Vector``, ``Text`` and ``Array``. The following code listing gives a
few examples:
::
['0' .. '9'] :: Set Char
[1 .. 10] :: Vector Int
[("default",0), (k1,v1)] :: Map String Int
['a' .. 'z'] :: Text
List patterns are also overloaded. When the ``OverloadedLists``
extension is turned on, these definitions are desugared as follows
::
f [] = ... -- f (toList -> []) = ...
g [x,y,z] = ... -- g (toList -> [x,y,z]) = ...
(Here we are using view-pattern syntax for the translation, see
:ref:`view-patterns`.)
The ``IsList`` class
~~~~~~~~~~~~~~~~~~~~
In the above desugarings, the functions ``toList``, ``fromList`` and
``fromListN`` are all methods of the ``IsList`` class, which is itself
exported from the ``GHC.Exts`` module. The type class is defined as
follows:
::
class IsList l where
type Item l
fromList :: [Item l] -> l
toList :: l -> [Item l]
fromListN :: Int -> [Item l] -> l
fromListN _ = fromList
The ``IsList`` class and its methods are intended to be used in
conjunction with the ``OverloadedLists`` extension.
- The type function ``Item`` returns the type of items of the structure
``l``.
- The function ``fromList`` constructs the structure ``l`` from the
given list of ``Item l``.
- The function ``fromListN`` takes the input list's length as a hint.
Its behaviour should be equivalent to ``fromList``. The hint can be
used for more efficient construction of the structure ``l`` compared
to ``fromList``. If the given hint is not equal to the input list's
length the behaviour of ``fromListN`` is not specified.
- The function ``toList`` should be the inverse of ``fromList``.
It is perfectly fine to declare new instances of ``IsList``, so that
list notation becomes useful for completely new data types. Here are
several example instances:
::
instance IsList [a] where
type Item [a] = a
fromList = id
toList = id
instance (Ord a) => IsList (Set a) where
type Item (Set a) = a
fromList = Set.fromList
toList = Set.toList
instance (Ord k) => IsList (Map k v) where
type Item (Map k v) = (k,v)
fromList = Map.fromList
toList = Map.toList
instance IsList (IntMap v) where
type Item (IntMap v) = (Int,v)
fromList = IntMap.fromList
toList = IntMap.toList
instance IsList Text where
type Item Text = Char
fromList = Text.pack
toList = Text.unpack
instance IsList (Vector a) where
type Item (Vector a) = a
fromList = Vector.fromList
fromListN = Vector.fromListN
toList = Vector.toList
Users should not, however, provide any instance that overlaps with the first
instance above. Namely, ``fromList`` and ``toList``, when used on lists,
should always be the identity function.
For example, the following instance is disallowed:
::
instance {-# OVERLAPPING #-} IsList [Int] where
type Item [Int] = Int
fromList = reverse
toList = reverse
Rebindable syntax
~~~~~~~~~~~~~~~~~
When desugaring list notation with :extension:`OverloadedLists` GHC uses the
``fromList`` (etc) methods from module ``GHC.Exts``. You do not need to
import ``GHC.Exts`` for this to happen.
However if you use :extension:`RebindableSyntax`, then GHC instead uses
whatever is in scope with the names of ``toList``, ``fromList`` and
``fromListN``. That is, these functions are rebindable; c.f.
:ref:`rebindable-syntax`.
Defaulting
~~~~~~~~~~
Currently, the ``IsList`` class is not accompanied with defaulting
rules. Although feasible, not much thought has gone into how to specify
the meaning of the default declarations like: ::
default ([a])
Speculation about the future
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The current implementation of the ``OverloadedLists`` extension can be
improved by handling the lists that are only populated with literals in
a special way. More specifically, the compiler could allocate such lists
statically using a compact representation and allow ``IsList`` instances
to take advantage of the compact representation. Equipped with this
capability the ``OverloadedLists`` extension will be in a good position
to subsume the ``OverloadedStrings`` extension (currently, as a special
case, string literals benefit from statically allocated compact
representation).