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

##
`OverloadedLists`

Further GHC improvements/extensions that may benefit ## 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:

```
https://gitlab.haskell.org/ghc/ghc/issues/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.