# Overloaded list notation

This wiki page documents the design and implementation of the GHC extension for overloading Haskell's list notation (added in GHC 7.8).

## Current Implementation

Let us briefly recap the notation for constructing lists. In Haskell, the list notation can be 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, the
definitions

f [] = ... g [x,y,z] = ...

will be treated as

f (toList -> []) = ... g (toList -> [x,y,z]) = ...

GHC, during the typechecking and desugaring phases, uses whatever is in scope
with the names of `fromList`

, `toList`

and `fromListN`

(i.e., `fromList`

, `toList`

and
`fromListN`

are rebindable).

That said, the `GHC.Exts`

module exports the `IsList`

class that can
be used to overload `fromListN`

and `fromListN`

for different
structures. 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 `Item`

type
function returns the type of items of the structure `l`

. The fromList
function constructs the structure `l`

from the given list of `Item l`

.
The `fromListN`

function 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 instances of the `IsList`

class should satisfy the following
property:

fromList . toList = id

In the following, we give several example instances of the `IsList`

type
class:

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 toList = Vector.toList fromListN = Vector.fromListN

## Further GHC improvements/extensions that may benefit `OverloadedLists`

## 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])`

## Literal Lists

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

Somewhat related discussions:

http://hackage.haskell.org/trac/ghc/ticket/5218 http://www.serpentine.com/blog/2012/09/12/the-case-of-the-mysterious-explosion-in-space/ http://www.mail-archive.com/haskell-cafe@haskell.org/msg101412.html

## Heterogeneous Lists

The `OverloadedLists`

extension as, implemented above, would not be able to be used on heterogeneous lists, for example, as implemented below:

data HList :: [*] -> * where HNil :: HList '[] HCons :: a -> HList xs -> HList (a ': xs)

This is a bit disappointing. However, I'm not really sure how you could make this extension support this use case, even if you added some hacks to the `IsList`

class.

## Length-{indexed,observed} Vectors

The current extension can't be used to represent list literals for length-indexed vectors as e.g.

-- (alternatively, GHC.TypeLits.Nat) data Nat = Ze | Su Nat data Vec :: * -> Nat -> * where Nil :: Vec a Ze Cons :: a -> Vec a n -> Vec a (Su n)

as the length-information is not provided in a suitable way.