From 3234a4ade7204c4206831b4c1dc4a8b23624cc6b Mon Sep 17 00:00:00 2001 From: Simon Peyton Jones Date: Thu, 14 Feb 2013 13:04:14 +0000 Subject: Add OverloadedLists, allowing list syntax to be overloaded This work was all done by Achim Krause George Giorgidze Weijers Jeroen It allows list syntax, such as [a,b], [a..b] and so on, to be overloaded so that it works for a variety of types. The design is described here: http://hackage.haskell.org/trac/ghc/wiki/OverloadedLists Eg. you can use it for maps, so that [(1,"foo"), (4,"bar")] :: Map Int String The main changes * The ExplicitList constructor of HsExpr gets witness field * Ditto ArithSeq constructor * Ditto the ListPat constructor of HsPat Everything else flows from this. --- docs/users_guide/flags.xml | 7 ++ docs/users_guide/glasgow_exts.xml | 157 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 164 insertions(+) (limited to 'docs') diff --git a/docs/users_guide/flags.xml b/docs/users_guide/flags.xml index f856f66dcf..299b4d527b 100644 --- a/docs/users_guide/flags.xml +++ b/docs/users_guide/flags.xml @@ -808,6 +808,13 @@ dynamic + + + Enable overloaded lists. + + dynamic + + Enable generalised algebraic data types. diff --git a/docs/users_guide/glasgow_exts.xml b/docs/users_guide/glasgow_exts.xml index 9dae3553b1..c088eee99a 100644 --- a/docs/users_guide/glasgow_exts.xml +++ b/docs/users_guide/glasgow_exts.xml @@ -4656,6 +4656,163 @@ to work since it gets translated into an equality comparison. + +Overloaded lists + + GHC supports overloading of the list notation. +Before turning our attention to the overloading, let us 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 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 +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 .) + + During the typechecking and desugaring phases, GHC uses whatever is in +scope with the names of toList, fromList and +fromListN. That is, these functions are rebindable; +c.f. + +That said, the GHC.Exts module exports the +IsList class that can be used to overload +these functions 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 FromList class and its methods are intended to be +used in conjunction with the 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. + + + +In the following, we give several example instances of the +FromList type class: + + +instance FromList [a] where + type Item [a] = a + fromList = id + toList = id + +instance (Ord a) => FromList (Set a) where + type Item (Set a) = a + fromList = Set.fromList + toList = Set.toList + +instance (Ord k) => FromList (Map k v) where + type Item (Map k v) = (k,v) + fromList = Map.fromList + toList = Map.toList + +instance FromList (IntMap v) where + type Item (IntMap v) = (Int,v) + fromList = IntMap.fromList + toList = IntMap.toList + +instance FromList Text where + type Item Text = Char + fromList = Text.pack + toList = Text.unpack + +instance FromList (Vector a) where + type Item (Vector a) = a + fromList = Vector.fromList + fromListN = Vector.fromListN + toList = Vector.toList + + +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]) + + +The current implementation of the +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 + extension will be in a good position to +subsume the extension (currently, as a +special case, string literals benefit from statically allocated compact +representation). + + + -- cgit v1.2.1