X-Git-Url: http://git.megacz.com/?p=ghc-hetmet.git;a=blobdiff_plain;f=docs%2Fusers_guide%2Fglasgow_exts.xml;h=de69b6006300bca4e780cccf406da4a5a64d67bd;hp=b1e9c3127296a53b15563143520271b46c4a3688;hb=67cb409159fa9136dff942b8baaec25909416022;hpb=a975e8341a53ec9cef25af816a9bf9ce96c16391 diff --git a/docs/users_guide/glasgow_exts.xml b/docs/users_guide/glasgow_exts.xml index b1e9c31..de69b60 100644 --- a/docs/users_guide/glasgow_exts.xml +++ b/docs/users_guide/glasgow_exts.xml @@ -319,7 +319,7 @@ it is always correct! It is also intended for processing into text. Indeed, the result of such processing is part of the description of the External + url="http://www.haskell.org/ghc/docs/papers/core.ps.gz">External Core language. So that document is a good place to look for a type-set version. We would be very happy if someone wanted to volunteer to produce an SGML @@ -993,7 +993,7 @@ and improve termination (Section 3.2 of the paper). -The web page: http://www.cse.ogi.edu/PacSoft/projects/rmb +The web page: http://www.cse.ogi.edu/PacSoft/projects/rmb/ contains up to date information on recursive monadic bindings. @@ -1058,6 +1058,166 @@ This name is not supported by GHC. branches. + + + + + Generalised (SQL-Like) List Comprehensions + list comprehensionsgeneralised + + extended list comprehensions + + group + sql + + + Generalised list comprehensions are a further enhancement to the + list comprehension syntatic sugar to allow operations such as sorting + and grouping which are familiar from SQL. They are fully described in the + paper + Comprehensive comprehensions: comprehensions with "order by" and "group by", + except that the syntax we use differs slightly from the paper. +Here is an example: + +employees = [ ("Simon", "MS", 80) +, ("Erik", "MS", 100) +, ("Phil", "Ed", 40) +, ("Gordon", "Ed", 45) +, ("Paul", "Yale", 60)] + +output = [ (the dept, sum salary) +| (name, dept, salary) <- employees +, then group by dept +, then sortWith by (sum salary) +, then take 5 ] + +In this example, the list output would take on + the value: + + +[("Yale", 60), ("Ed", 85), ("MS", 180)] + + +There are three new keywords: group, by, and using. +(The function sortWith is not a keyword; it is an ordinary +function that is exported by GHC.Exts.) + +There are five new forms of compehension qualifier, +all introduced by the (existing) keyword then: + + + + +then f + + + This statement requires that f have the type + forall a. [a] -> [a]. You can see an example of it's use in the + motivating example, as this form is used to apply take 5. + + + + + + + +then f by e + + + This form is similar to the previous one, but allows you to create a function + which will be passed as the first argument to f. As a consequence f must have + the type forall a. (a -> t) -> [a] -> [a]. As you can see + from the type, this function lets f "project out" some information + from the elements of the list it is transforming. + + An example is shown in the opening example, where sortWith + is supplied with a function that lets it find out the sum salary + for any item in the list comprehension it transforms. + + + + + + + +then group by e using f + + + This is the most general of the grouping-type statements. In this form, + f is required to have type forall a. (a -> t) -> [a] -> [[a]]. + As with the then f by e case above, the first argument + is a function supplied to f by the compiler which lets it compute e on every + element of the list being transformed. However, unlike the non-grouping case, + f additionally partitions the list into a number of sublists: this means that + at every point after this statement, binders occuring before it in the comprehension + refer to lists of possible values, not single values. To help understand + this, let's look at an example: + + +-- This works similarly to groupWith in GHC.Exts, but doesn't sort its input first +groupRuns :: Eq b => (a -> b) -> [a] -> [[a]] +groupRuns f = groupBy (\x y -> f x == f y) + +output = [ (the x, y) +| x <- ([1..3] ++ [1..2]) +, y <- [4..6] +, then group by x using groupRuns ] + + + This results in the variable output taking on the value below: + + +[(1, [4, 5, 6]), (2, [4, 5, 6]), (3, [4, 5, 6]), (1, [4, 5, 6]), (2, [4, 5, 6])] + + + Note that we have used the the function to change the type + of x from a list to its original numeric type. The variable y, in contrast, is left + unchanged from the list form introduced by the grouping. + + + + + + +then group by e + + + This form of grouping is essentially the same as the one described above. However, + since no function to use for the grouping has been supplied it will fall back on the + groupWith function defined in + GHC.Exts. This + is the form of the group statement that we made use of in the opening example. + + + + + + + +then group using f + + + With this form of the group statement, f is required to simply have the type + forall a. [a] -> [[a]], which will be used to group up the + comprehension so far directly. An example of this form is as follows: + + +output = [ x +| y <- [1..5] +, x <- "hello" +, then group using inits] + + + This will yield a list containing every prefix of the word "hello" written out 5 times: + + +["","h","he","hel","hell","hello","helloh","hellohe","hellohel","hellohell","hellohello","hellohelloh",...] + + + + + + @@ -1152,16 +1312,16 @@ GHC allows a small extension to the syntax of left operator sections, which allows you to define postfix operators. The extension is this: the left section (e !) - + is equivalent (from the point of view of both type checking and execution) to the expression ((!) e) - + (for any expression e and operator (!). The strict Haskell 98 interpretation is that the section is equivalent to (\y -> (!) e y) - + That is, the operator must be a function of two arguments. GHC allows it to take only one argument, and that in turn allows you to write the function postfix. @@ -1689,8 +1849,8 @@ adding a new existential quantification construct. - -Type classes + +Existentials and type classes An easy extension is to allow @@ -2016,19 +2176,8 @@ In the example, the equality dictionary is used to satisfy the equality constrai generated by the call to elem, so that the type of insert itself has no Eq constraint. -This behaviour contrasts with Haskell 98's peculiar treatment of -contexts on a data type declaration (Section 4.2.1 of the Haskell 98 Report). -In Haskell 98 the definition - - data Eq a => Set' a = MkSet' [a] - -gives MkSet' the same type as MkSet above. But instead of -making available an (Eq a) constraint, pattern-matching -on MkSet' requires an (Eq a) constraint! -GHC faithfully implements this behaviour, odd though it is. But for GADT-style declarations, -GHC's behaviour is much more useful, as well as much more intuitive. -For example, a possible application of GHC's behaviour is to reify dictionaries: +For example, one possible application is to reify dictionaries: data NumInst a where MkNumInst :: Num a => NumInst a @@ -2042,6 +2191,38 @@ For example, a possible application of GHC's behaviour is to reify dictionaries: Here, a value of type NumInst a is equivalent to an explicit (Num a) dictionary. + +All this applies to constructors declared using the syntax of . +For example, the NumInst data type above could equivalently be declared +like this: + + data NumInst a + = Num a => MkNumInst (NumInst a) + +Notice that, unlike the situation when declaring an existental, there is +no forall, because the Num constrains the +data type's univerally quantified type variable a. +A constructor may have both universal and existential type variables: for example, +the following two declarations are equivalent: + + data T1 a + = forall b. (Num a, Eq b) => MkT1 a b + data T2 a where + MkT2 :: (Num a, Eq b) => a -> b -> T2 a + + +All this behaviour contrasts with Haskell 98's peculiar treatment of +contexts on a data type declaration (Section 4.2.1 of the Haskell 98 Report). +In Haskell 98 the definition + + data Eq a => Set' a = MkSet' [a] + +gives MkSet' the same type as MkSet above. But instead of +making available an (Eq a) constraint, pattern-matching +on MkSet' requires an (Eq a) constraint! +GHC faithfully implements this behaviour, odd though it is. But for GADT-style declarations, +GHC's behaviour is much more useful, as well as much more intuitive. + The rest of this section gives further details about GADT-style data @@ -2193,7 +2374,7 @@ the type a is refined to Int. That's the A precise specification of the type rules is beyond what this user manual aspires to, but the design closely follows that described in the paper Simple +url="http://research.microsoft.com/%7Esimonpj/papers/gadt/">Simple unification-based type inference for GADTs, (ICFP 2006). The general principle is this: type refinement is only carried out @@ -2212,7 +2393,7 @@ the result type of the case expression. Hence the addition < These and many other examples are given in papers by Hongwei Xi, and Tim Sheard. There is a longer introduction -on the wiki, +on the wiki, and Ralf Hinze's Fun with phantom types also has a number of examples. Note that papers may use different notation to that implemented in GHC. @@ -2388,14 +2569,14 @@ Haskell 98, you can inherit instances of Eq, Ord + newtype Dollars = Dollars Int - + and you want to use arithmetic on Dollars, you have to explicitly define an instance of Num: - + instance Num Dollars where Dollars a + Dollars b = Dollars (a+b) ... @@ -2413,17 +2594,17 @@ dictionary, only slower! GHC now permits such instances to be derived instead, using the flag , so one can write - + newtype Dollars = Dollars Int deriving (Eq,Show,Num) - + and the implementation uses the same Num dictionary for Dollars as for Int. Notionally, the compiler derives an instance declaration of the form - + instance Num Int => Num Dollars - + which just adds or removes the newtype constructor according to the type. @@ -2433,27 +2614,27 @@ We can also derive instances of constructor classes in a similar way. For example, suppose we have implemented state and failure monad transformers, such that - + instance Monad m => Monad (State s m) instance Monad m => Monad (Failure m) - + In Haskell 98, we can define a parsing monad by - + type Parser tok m a = State [tok] (Failure m) a - + which is automatically a monad thanks to the instance declarations above. With the extension, we can make the parser type abstract, without needing to write an instance of class Monad, via - + newtype Parser tok m a = Parser (State [tok] (Failure m) a) deriving Monad In this case the derived instance declaration is of the form - + instance Monad (State [tok] (Failure m)) => Monad (Parser tok m) - + Notice that, since Monad is a constructor class, the instance is a partial application of the new type, not the @@ -2468,12 +2649,12 @@ newtype is the last class parameter. In this case, a ``partial application'' of the class appears in the deriving clause. For example, given the class - + class StateMonad s m | m -> s where ... instance Monad m => StateMonad s (State s m) where ... - + then we can derive an instance of StateMonad for Parsers by - + newtype Parser tok m a = Parser (State [tok] (Failure m) a) deriving (Monad, StateMonad [tok]) @@ -2481,7 +2662,7 @@ then we can derive an instance of StateMonad for Par The derived instance is obtained by completing the application of the class to the new type: - + instance StateMonad [tok] (State [tok] (Failure m)) => StateMonad [tok] (Parser tok m) @@ -2501,9 +2682,9 @@ the newtype and its representation. Derived instance declarations are constructed as follows. Consider the declaration (after expansion of any type synonyms) - + newtype T v1...vn = T' (t vk+1...vn) deriving (c1...cm) - + where @@ -2532,17 +2713,17 @@ where Then, for each ci, the derived instance declaration is: - + instance ci t => ci (T v1...vk) As an example which does not work, consider - + newtype NonMonad m s = NonMonad (State s m s) deriving Monad - + Here we cannot derive the instance - + instance Monad (State s m) => Monad (NonMonad m) - + because the type variable s occurs in State s m, and so cannot be "eta-converted" away. It is a good thing that this @@ -2556,7 +2737,7 @@ Notice also that the order of class parameters becomes important, since we can only derive instances for the last one. If the StateMonad class above were instead defined as - + class StateMonad m s | m -> s where ... @@ -2588,8 +2769,8 @@ the standard method is used or the one described here.) This section, and the next one, documents GHC's type-class extensions. There's lots of background in the paper Type -classes: exploring the design space (Simon Peyton Jones, Mark +url="http://research.microsoft.com/~simonpj/Papers/type-class-design-space/">Type +classes: exploring the design space (Simon Peyton Jones, Mark Jones, Erik Meijer). @@ -2668,7 +2849,7 @@ class type variable, thus: The type of elem is illegal in Haskell 98, because it contains the constraint Eq a, constrains only the class type variable (in this case a). -GHC lifts this restriction. +GHC lifts this restriction (flag ). @@ -2680,7 +2861,7 @@ GHC lifts this restriction. Functional dependencies are implemented as described by Mark Jones -in “Type Classes with Functional Dependencies”, Mark P. Jones, +in “Type Classes with Functional Dependencies”, Mark P. Jones, In Proceedings of the 9th European Symposium on Programming, ESOP 2000, Berlin, Germany, March 2000, Springer-Verlag LNCS 1782, . @@ -3015,7 +3196,7 @@ must be of the form C a where a is a type variable that occurs in the head. -The flag loosens these restrictions +The flag loosens these restrictions considerably. Firstly, multi-parameter type classes are permitted. Secondly, the context and head of the instance declaration can each consist of arbitrary (well-kinded) assertions (C t1 ... tn) subject only to the @@ -3144,7 +3325,7 @@ typechecker loop: class F a b | a->b instance F [a] [[a]] instance (D c, F a c) => D [a] -- 'c' is not mentioned in the head - + Similarly, it can be tempting to lift the coverage condition: class Mul a b c | a b -> c where @@ -3380,7 +3561,7 @@ instance of Num or of IsString< -The standard defaulting rule (Haskell Report, Section 4.3.4) +The standard defaulting rule (Haskell Report, Section 4.3.4) is extended thus: defaulting applies when all the unresolved constraints involve standard classes or IsString; and at least one is a numeric class or IsString. @@ -3421,7 +3602,7 @@ to work since it gets translated into an equality comparison. Type signatures -The context of a type signature +The context of a type signature Unlike Haskell 98, constraints in types do not have to be of the form (class type-variable) or @@ -4057,9 +4238,18 @@ The function f3 has a rank-3 type; it has rank-2 types on the left of a function arrow. -GHC allows types of arbitrary rank; you can nest foralls -arbitrarily deep in function arrows. (GHC used to be restricted to rank 2, but -that restriction has now been lifted.) +GHC has three flags to control higher-rank types: + + + : data constructors (only) can have polymorphic argment types. + + + : any function (including data constructors) can have a rank-2 type. + + + : any function (including data constructors) can have an arbitrary-rank type. +That is, you can nest foralls +arbitrarily deep in function arrows. In particular, a forall-type (also called a "type scheme"), including an operational type class context, is legal: @@ -4071,6 +4261,8 @@ field type signatures. As the type of an implicit parameter In a pattern type signature (see ) + + Of course forall becomes a keyword; you can't use forall as a type variable any more! @@ -4322,7 +4514,7 @@ Notice here that the Maybe type is parameterised by the [a]). The technical details of this extension are described in the paper -Boxy types: +Boxy types: type inference for higher-rank types and impredicativity, which appeared at ICFP 2006. @@ -4385,7 +4577,7 @@ A lexically scoped type variable can be bound by: In Haskell, a programmer-written type signature is implicitly quantified over its free type variables (Section +url="http://www.haskell.org/onlinereport/decls.html#sect4.1.2">Section 4.1.2 of the Haskel Report). Lexically scoped type variables affect this implicit quantification rules @@ -4450,7 +4642,7 @@ type variable s into scope, in the annotated expression Pattern type signatures A type signature may occur in any pattern; this is a pattern type -signature. +signature. For example: -- f and g assume that 'a' is already in scope @@ -4463,9 +4655,27 @@ already in scope (i.e. bound by the enclosing context), matters are simple: the signature simply constrains the type of the pattern in the obvious way. -There is only one situation in which you can write a pattern type signature that -mentions a type variable that is not already in scope, namely in pattern match -of an existential data constructor. For example: +Unlike expression and declaration type signatures, pattern type signatures are not implictly generalised. +The pattern in a patterm binding may only mention type variables +that are already in scope. For example: + + f :: forall a. [a] -> (Int, [a]) + f xs = (n, zs) + where + (ys::[a], n) = (reverse xs, length xs) -- OK + zs::[a] = xs ++ ys -- OK + + Just (v::b) = ... -- Not OK; b is not in scope + +Here, the pattern signatures for ys and zs +are fine, but the one for v is not because b is +not in scope. + + +However, in all patterns other than pattern bindings, a pattern +type signature may mention a type variable that is not in scope; in this case, +the signature brings that type variable into scope. +This is particularly important for existential data constructors. For example: data T = forall a. MkT [a] @@ -4475,14 +4685,19 @@ of an existential data constructor. For example: t3::[a] = [t,t,t] Here, the pattern type signature (t::a) mentions a lexical type -variable that is not already in scope. Indeed, it cannot already be in scope, +variable that is not already in scope. Indeed, it cannot already be in scope, because it is bound by the pattern match. GHC's rule is that in this situation (and only then), a pattern type signature can mention a type variable that is not already in scope; the effect is to bring it into scope, standing for the existentially-bound type variable. -If this seems a little odd, we think so too. But we must have +When a pattern type signature binds a type variable in this way, GHC insists that the +type variable is bound to a rigid, or fully-known, type variable. +This means that any user-written type signature always stands for a completely known type. + + +If all this seems a little odd, we think so too. But we must have some way to bring such type variables into scope, else we could not name existentially-bound type variables in subsequent type signatures. @@ -4580,18 +4795,18 @@ scope over the methods defined in the where part. For exampl The Haskell Report specifies that a group of bindings (at top level, or in a let or where) should be sorted into strongly-connected components, and then type-checked in dependency order -(Haskell +(Haskell Report, Section 4.5.1). As each group is type-checked, any binders of the group that have an explicit type signature are put in the type environment with the specified polymorphic type, and all others are monomorphic until the group is generalised -(Haskell Report, Section 4.5.2). +(Haskell Report, Section 4.5.2). Following a suggestion of Mark Jones, in his paper -Typing Haskell in +Typing Haskell in Haskell, GHC implements a more general scheme. If is specified: @@ -4652,7 +4867,7 @@ Currently, only the former are fully implemented, while we are still working on the latter. As a result, the specification of the language extension is also still to some degree in flux. Hence, a more detailed description of the language extension and its use is currently available -from the Haskell +from the Haskell wiki page on type families. The material will be moved to this user's guide when it has stabilised. @@ -4675,12 +4890,12 @@ Type families are enabled by the flag . Haskell. The background to the main technical innovations is discussed in " +url="http://research.microsoft.com/~simonpj/papers/meta-haskell/"> Template Meta-programming for Haskell" (Proc Haskell Workshop 2002). There is a Wiki page about -Template Haskell at +Template Haskell at http://www.haskell.org/haskellwiki/Template_Haskell, and that is the best place to look for further details. You may also @@ -5503,7 +5718,7 @@ prefix notation: (!) f x = 3 The semantics of Haskell pattern matching is described in +url="http://www.haskell.org/onlinereport/exps.html#sect3.17.2"> Section 3.17.2 of the Haskell Report. To this description add one extra item 10, saying: Matching @@ -5513,7 +5728,7 @@ the pattern !pat against a value v behaves v -Similarly, in Figure 4 of +Similarly, in Figure 4 of Section 3.17.3, add a new case (t): case v of { !pat -> e; _ -> e' } @@ -5521,7 +5736,7 @@ case v of { !pat -> e; _ -> e' } That leaves let expressions, whose translation is given in -Section +Section 3.12 of the Haskell Report. In the translation box, first apply @@ -5835,8 +6050,26 @@ key_function :: Int -> String -> (Bool, Double) The major effect of an INLINE pragma is to declare a function's “cost” to be very low. The normal unfolding machinery will then be very keen to - inline it. - + inline it. However, an INLINE pragma for a + function "f" has a number of other effects: + + +No funtions are inlined into f. Otherwise +GHC might inline a big function into f's right hand side, +making f big; and then inline f blindly. + + +The float-in, float-out, and common-sub-expression transformations are not +applied to the body of f. + + +An INLINE function is not worker/wrappered by strictness analysis. +It's going to be inlined wholesale instead. + + +All of these effects are aimed at ensuring that what gets inlined is +exactly what you asked for, no more and no less. + Syntactically, an INLINE pragma for a function can be put anywhere its type signature could be put. @@ -6024,7 +6257,7 @@ happen. h :: Eq a => a -> a -> a {-# SPECIALISE h :: (Eq a) => [a] -> [a] -> [a] #-} - + The last of these examples will generate a RULE with a somewhat-complex left-hand side (try it yourself), so it might not fire very well. If you use this kind of specialisation, let us know how well it works. @@ -7098,7 +7331,7 @@ carried out at let and where bindings. Haskell's monomorphism restriction (see -Section +Section 4.5.5 of the Haskell Report) can be completely switched off by @@ -7125,7 +7358,7 @@ can be completely switched off by [x] = e -- A pattern binding Experimentally, GHC now makes pattern bindings monomorphic by -default. Use to recover the +default. Use to recover the standard behaviour.