6.2.9. Overloaded lists

OverloadedLists

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 View patterns.)

6.2.9.1. 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

6.2.9.2. Rebindable syntax

When desugaring list notation with 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 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. Rebindable syntax and the implicit Prelude import.

6.2.9.3. 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])

6.2.9.4. 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).