1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
.. _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).
|
