Version 13 (modified by duairc, 2 years ago) (diff) |
---|

# Overloaded list notation

This wiki page documents the design and implementation of the GHC extension for overloading Haskell's list notation.

## 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/[email protected]/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.