X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=ghc%2Fdocs%2Fusers_guide%2Fglasgow_exts.sgml;h=bedbc0833c247bf007a66ea5dfbc96b600597534;hb=7d67a216958e8986cf067f96f9e9c7a4101fd29b;hp=f14d9f2a71efa679833abae2f77fd5b4c4e147b4;hpb=7db602a0d8f840362c455650cbddc1ecc04ec43d;p=ghc-hetmet.git diff --git a/ghc/docs/users_guide/glasgow_exts.sgml b/ghc/docs/users_guide/glasgow_exts.sgml index f14d9f2..bedbc08 100644 --- a/ghc/docs/users_guide/glasgow_exts.sgml +++ b/ghc/docs/users_guide/glasgow_exts.sgml @@ -12,9 +12,7 @@ the underlying facilities with which we implement Haskell. Thus, you can get at the Raw Iron, if you are willing to write some non-standard code at a more primitive level. You need not be “stuck” on performance because of the implementation costs of Haskell's -“high-level” features—you can always code “under” them. In an -extreme case, you can write all your time-critical code in C, and then -just glue it together with Haskell! +“high-level” features—you can always code “under” them. In an extreme case, you can write all your time-critical code in C, and then just glue it together with Haskell! @@ -78,11 +76,20 @@ for some nested declarations, where this would not be legal in Haskell -Calling out to C: +Pattern guards + + +Instead of being a boolean expression, a guard is a list of qualifiers, exactly as in a list comprehension. See . + + + + + +Foreign calling: Just what it sounds like. We provide lots of rope that you -can dangle around your neck. Please see . +can dangle around your neck. Please see . @@ -107,17 +114,180 @@ Details in . + + +Generic classes: + + +Generic class declarations allow you to define a class +whose methods say how to work over an arbitrary data type. +Then it's really easy to make any new type into an instance of +the class. This generalises the rather ad-hoc "deriving" feature +of Haskell 98. +Details in . + + + Before you get too carried away working at the lowest level (e.g., -sloshing MutableByteArray#s around your program), you may wish to -check if there are system libraries that provide a “Haskellised -veneer” over the features you want. See . +sloshing MutableByteArray#s around your +program), you may wish to check if there are libraries that provide a +“Haskellised veneer” over the features you want. See +. + + + + Language options + + languageoption + + optionslanguage + + extensionsoptions controlling + + + These flags control what variation of the language are + permitted. Leaving out all of them gives you standard Haskell + 98. + + + + + : + + + This simultaneously enables all of the extensions to + Haskell 98 described in , except where otherwise + noted. + + + + + : + + + Switch off the Haskell 98 monomorphism restriction. + Independent of the + flag. + + + + + + + + + + + + See . Only relevant + if you also use . + + + + + : + + + See . Only relevant if + you also use . + + + + + + + + See . Only relevant if + you also use . + + + + + + + + See . Independent of + . + + + + + + + -fno-implicit-prelude + option GHC normally imports + Prelude.hi files for you. If you'd + rather it didn't, then give it a + option. The idea + is that you can then import a Prelude of your own. (But + don't call it Prelude; the Haskell + module namespace is flat, and you must not conflict with + any Prelude module.) + + Even though you have not imported the Prelude, all + the built-in syntax still refers to the built-in Haskell + Prelude types and values, as specified by the Haskell + Report. For example, the type [Int] + still means Prelude.[] Int; tuples + continue to refer to the standard Prelude tuples; the + translation for list comprehensions continues to use + Prelude.map etc. + + With one group of exceptions! You may want to + define your own numeric class hierarchy. It completely + defeats that purpose if the literal "1" means + "Prelude.fromInteger 1", which is what + the Haskell Report specifies. So the + flag causes the + following pieces of built-in syntax to refer to whatever + is in scope, not the Prelude versions: + + + + Integer and fractional literals mean + "fromInteger 1" and + "fromRational 3.2", not the + Prelude-qualified versions; both in expressions and in + patterns. + + + + Negation (e.g. "- (f x)") + means "negate (f x)" (not + Prelude.negate). + + + + In an n+k pattern, the standard Prelude + Ord class is used for comparison, + but the necessary subtraction uses whatever + "(-)" is in scope (not + "Prelude.(-)"). + + + + + + + + + + +Unboxed types and primitive operations + +PrelGHC module + + +This module defines all the types which are primitive in Glasgow +Haskell, and the operations provided for them. - + Unboxed types @@ -125,1023 +295,1433 @@ veneer” over the features you want. See . Unboxed types (Glasgow extension) +Most types in GHC are boxed, which means +that values of that type are represented by a pointer to a heap +object. The representation of a Haskell Int, for +example, is a two-word heap object. An unboxed +type, however, is represented by the value itself, no pointers or heap +allocation are involved. + + + +Unboxed types correspond to the “raw machine” types you +would use in C: Int# (long int), +Double# (double), Addr# +(void *), etc. The primitive operations +(PrimOps) on these types are what you might expect; e.g., +(+#) is addition on +Int#s, and is the machine-addition that we all +know and love—usually one instruction. + + + +Primitive (unboxed) types cannot be defined in Haskell, and are +therefore built into the language and compiler. Primitive types are +always unlifted; that is, a value of a primitive type cannot be +bottom. We use the convention that primitive types, values, and +operations have a # suffix. + + + +Primitive values are often represented by a simple bit-pattern, such +as Int#, Float#, +Double#. But this is not necessarily the case: +a primitive value might be represented by a pointer to a +heap-allocated object. Examples include +Array#, the type of primitive arrays. A +primitive array is heap-allocated because it is too big a value to fit +in a register, and would be too expensive to copy around; in a sense, +it is accidental that it is represented by a pointer. If a pointer +represents a primitive value, then it really does point to that value: +no unevaluated thunks, no indirections…nothing can be at the +other end of the pointer than the primitive value. + + + +There are some restrictions on the use of primitive types, the main +one being that you can't pass a primitive value to a polymorphic +function or store one in a polymorphic data type. This rules out +things like [Int#] (i.e. lists of primitive +integers). The reason for this restriction is that polymorphic +arguments and constructor fields are assumed to be pointers: if an +unboxed integer is stored in one of these, the garbage collector would +attempt to follow it, leading to unpredictable space leaks. Or a +seq operation on the polymorphic component may +attempt to dereference the pointer, with disastrous results. Even +worse, the unboxed value might be larger than a pointer +(Double# for instance). + + -These types correspond to the “raw machine” types you would use in -C: Int# (long int), Double# (double), Addr# (void *), etc. The -primitive operations (PrimOps) on these types are what you -might expect; e.g., (+#) is addition on Int#s, and is the -machine-addition that we all know and love—usually one instruction. +Nevertheless, A numerically-intensive program using unboxed types can +go a lot faster than its “standard” +counterpart—we saw a threefold speedup on one example. + + + +Unboxed Tuples + + -There are some restrictions on the use of unboxed types, the main one -being that you can't pass an unboxed value to a polymorphic function -or store one in a polymorphic data type. This rules out things like -[Int#] (i.e. lists of unboxed integers). The reason for this -restriction is that polymorphic arguments and constructor fields are -assumed to be pointers: if an unboxed integer is stored in one of -these, the garbage collector would attempt to follow it, leading to -unpredictable space leaks. Or a seq operation on the polymorphic -component may attempt to dereference the pointer, with disastrous -results. Even worse, the unboxed value might be larger than a pointer -(Double# for instance). +Unboxed tuples aren't really exported by PrelGHC, +they're available by default with . An +unboxed tuple looks like this: -Nevertheless, A numerically-intensive program using unboxed types can -go a lot faster than its “standard” counterpart—we saw a -threefold speedup on one example. + + +(# e_1, ..., e_n #) + + -Please see for the details of unboxed types and the -operations on them. +where e_1..e_n are expressions of any +type (primitive or non-primitive). The type of an unboxed tuple looks +the same. - + +Unboxed tuples are used for functions that need to return multiple +values, but they avoid the heap allocation normally associated with +using fully-fledged tuples. When an unboxed tuple is returned, the +components are put directly into registers or on the stack; the +unboxed tuple itself does not have a composite representation. Many +of the primitive operations listed in this section return unboxed +tuples. + - -Primitive state-transformer monad - + +There are some pretty stringent restrictions on the use of unboxed tuples: + -state transformers (Glasgow extensions) -ST monad (Glasgow extension) + + + + + + Unboxed tuple types are subject to the same restrictions as +other unboxed types; i.e. they may not be stored in polymorphic data +structures or passed to polymorphic functions. + + + -This monad underlies our implementation of arrays, mutable and -immutable, and our implementation of I/O, including “C calls”. + Unboxed tuples may only be constructed as the direct result of +a function, and may only be deconstructed with a case expression. +eg. the following are valid: + + + +f x y = (# x+1, y-1 #) +g x = case f x x of { (# a, b #) -> a + b } + + + +but the following are invalid: + + + +f x y = g (# x, y #) +g (# x, y #) = x + y + + + + + -The ST library, which provides access to the ST monad, is a -GHC/Hugs extension library and is described in the separate GHC/Hugs Extension Libraries document. + No variable can have an unboxed tuple type. This is illegal: + + + +f :: (# Int, Int #) -> (# Int, Int #) +f x = x + + + +because x has an unboxed tuple type. + + - + - -Primitive arrays, mutable and otherwise - + -primitive arrays (Glasgow extension) -arrays, primitive (Glasgow extension) +Note: we may relax some of these restrictions in the future. -GHC knows about quite a few flavours of Large Swathes of Bytes. +The IO and ST monads use unboxed +tuples to avoid unnecessary allocation during sequences of operations. + + + +Character and numeric types + +character types, primitive +numeric types, primitive +integer types, primitive +floating point types, primitive -First, GHC distinguishes between primitive arrays of (boxed) Haskell -objects (type Array# obj) and primitive arrays of bytes (type -ByteArray#). +There are the following obvious primitive types: + +type Char# +type Int# +type Word# +type Addr# +type Float# +type Double# +type Int64# +type Word64# + + +Char# +Int# +Word# +Addr# +Float# +Double# +Int64# +Word64# + -Second, it distinguishes between… - +If you really want to know their exact equivalents in C, see +ghc/includes/StgTypes.h in the GHC source tree. + - -Immutable: - -Arrays that do not change (as with “standard” Haskell arrays); you -can only read from them. Obviously, they do not need the care and -attention of the state-transformer monad. +Literals for these types may be written as follows: - - - -Mutable: - + -Arrays that may be changed or “mutated.” All the operations on them -live within the state-transformer monad and the updates happen -in-place. + + +1# an Int# +1.2# a Float# +1.34## a Double# +'a'# a Char#; for weird characters, use e.g. '\o<octal>'# +"a"# an Addr# (a `char *'); only characters '\0'..'\255' allowed + + +literals, primitive +constants, primitive +numbers, primitive - - - -“Static” (in C land): - + + + + +Comparison operations + -A C routine may pass an Addr# pointer back into Haskell land. There -are then primitive operations with which you may merrily grab values -over in C land, by indexing off the “static” pointer. +comparisons, primitive +operators, comparison - - - -“Stable” pointers: - + -If, for some reason, you wish to hand a Haskell pointer (i.e., -not an unboxed value) to a C routine, you first make the -pointer “stable,” so that the garbage collector won't forget that it -exists. That is, GHC provides a safe way to pass Haskell pointers to -C. + + +{>,>=,==,/=,<,<=}# :: Int# -> Int# -> Bool + +{gt,ge,eq,ne,lt,le}Char# :: Char# -> Char# -> Bool + -- ditto for Word# and Addr# + + +># +>=# +==# +/=# +<# +<=# +gt{Char,Word,Addr}# +ge{Char,Word,Addr}# +eq{Char,Word,Addr}# +ne{Char,Word,Addr}# +lt{Char,Word,Addr}# +le{Char,Word,Addr}# + + + +Primitive-character operations + -Please see for more details. +characters, primitive operations +operators, primitive character - - - -“Foreign objects”: - + -A “foreign object” is a safe way to pass an external object (a -C-allocated pointer, say) to Haskell and have Haskell do the Right -Thing when it no longer references the object. So, for example, C -could pass a large bitmap over to Haskell and say “please free this -memory when you're done with it.” + + +ord# :: Char# -> Int# +chr# :: Int# -> Char# + + +ord# +chr# + + + +Primitive-<Literal>Int</Literal> operations + -Please see for more details. +integers, primitive operations +operators, primitive integer - - - + + + + +{+,-,*,quotInt,remInt,gcdInt}# :: Int# -> Int# -> Int# +negateInt# :: Int# -> Int# + +iShiftL#, iShiftRA#, iShiftRL# :: Int# -> Int# -> Int# + -- shift left, right arithmetic, right logical + +addIntC#, subIntC#, mulIntC# :: Int# -> Int# -> (# Int#, Int# #) + -- add, subtract, multiply with carry + + ++# +-# +*# +quotInt# +remInt# +gcdInt# +iShiftL# +iShiftRA# +iShiftRL# +addIntC# +subIntC# +mulIntC# +shift operations, integer -The libraries section gives more details on all these “primitive -array” types and the operations on them, . Some of these extensions -are also supported by Hugs, and the supporting libraries are described -in the GHC/Hugs Extension Libraries -document. +Note: No error/overflow checking! - + - -Calling C directly from Haskell - + +Primitive-<Literal>Double</Literal> and <Literal>Float</Literal> operations -C calls (Glasgow extension) -_ccall_ (Glasgow extension) -_casm_ (Glasgow extension) +floating point numbers, primitive +operators, primitive floating point -GOOD ADVICE: Because this stuff is not Entirely Stable as far as names -and things go, you would be well-advised to keep your C-callery -corraled in a few modules, rather than sprinkled all over your code. -It will then be quite easy to update later on. + + +{+,-,*,/}## :: Double# -> Double# -> Double# +{<,<=,==,/=,>=,>}## :: Double# -> Double# -> Bool +negateDouble# :: Double# -> Double# +double2Int# :: Double# -> Int# +int2Double# :: Int# -> Double# + +{plus,minux,times,divide}Float# :: Float# -> Float# -> Float# +{gt,ge,eq,ne,lt,le}Float# :: Float# -> Float# -> Bool +negateFloat# :: Float# -> Float# +float2Int# :: Float# -> Int# +int2Float# :: Int# -> Float# + + - -<Function>_ccall_</Function> and <Function>_casm_</Function>: an introduction - + ++## +-## +*## +/## +<## +<=## +==## +=/## +>=## +>## +negateDouble# +double2Int# +int2Double# + + + +plusFloat# +minusFloat# +timesFloat# +divideFloat# +gtFloat# +geFloat# +eqFloat# +neFloat# +ltFloat# +leFloat# +negateFloat# +float2Int# +int2Float# + + + +And a full complement of trigonometric functions: + + + + + +expDouble# :: Double# -> Double# +logDouble# :: Double# -> Double# +sqrtDouble# :: Double# -> Double# +sinDouble# :: Double# -> Double# +cosDouble# :: Double# -> Double# +tanDouble# :: Double# -> Double# +asinDouble# :: Double# -> Double# +acosDouble# :: Double# -> Double# +atanDouble# :: Double# -> Double# +sinhDouble# :: Double# -> Double# +coshDouble# :: Double# -> Double# +tanhDouble# :: Double# -> Double# +powerDouble# :: Double# -> Double# -> Double# + + +trigonometric functions, primitive + + + +similarly for Float#. + -The simplest way to use a simple C function +There are two coercion functions for Float#/Double#: -double fooC( FILE *in, char c, int i, double d, unsigned int u ) +float2Double# :: Float# -> Double# +double2Float# :: Double# -> Float# +float2Double# +double2Float# + + + +The primitive version of decodeDouble +(encodeDouble is implemented as an external C +function): -is to provide a Haskell wrapper: + + +decodeDouble# :: Double# -> PrelNum.ReturnIntAndGMP + + +encodeDouble# +decodeDouble# + + + +(And the same for Float#s.) + + + + + +Operations on/for <Literal>Integers</Literal> (interface to GMP) + + + +arbitrary precision integers +Integer, operations on + + + +We implement Integers (arbitrary-precision +integers) using the GNU multiple-precision (GMP) package (version +2.0.2). + + + +The data type for Integer is either a small +integer, represented by an Int, or a large integer +represented using the pieces required by GMP's +MP_INT in gmp.h (see +gmp.info in +ghc/includes/runtime/gmp). It comes out as: + + + + + +data Integer = S# Int# -- small integers + | J# Int# ByteArray# -- large integers + + +Integer type The primitive +ops to support large Integers use the +“pieces” of the representation, and are as follows: -fooH :: Char -> Int -> Double -> Word -> IO Double -fooH c i d w = _ccall_ fooC (“stdin”::Addr) c i d w +negateInteger# :: Int# -> ByteArray# -> Integer + +{plus,minus,times}Integer#, gcdInteger#, + quotInteger#, remInteger#, divExactInteger# + :: Int# -> ByteArray# + -> Int# -> ByteArray# + -> (# Int#, ByteArray# #) + +cmpInteger# + :: Int# -> ByteArray# + -> Int# -> ByteArray# + -> Int# -- -1 for <; 0 for ==; +1 for > + +cmpIntegerInt# + :: Int# -> ByteArray# + -> Int# + -> Int# -- -1 for <; 0 for ==; +1 for > + +gcdIntegerInt# :: + :: Int# -> ByteArray# + -> Int# + -> Int# + +divModInteger#, quotRemInteger# + :: Int# -> ByteArray# + -> Int# -> ByteArray# + -> (# Int#, ByteArray#, + Int#, ByteArray# #) + +integer2Int# :: Int# -> ByteArray# -> Int# + +int2Integer# :: Int# -> Integer -- NB: no error-checking on these two! +word2Integer# :: Word# -> Integer + +addr2Integer# :: Addr# -> Integer + -- the Addr# is taken to be a `char *' string + -- to be converted into an Integer. +negateInteger# +plusInteger# +minusInteger# +timesInteger# +quotInteger# +remInteger# +gcdInteger# +gcdIntegerInt# +divExactInteger# +cmpInteger# +divModInteger# +quotRemInteger# +integer2Int# +int2Integer# +word2Integer# +addr2Integer# + + + +Words and addresses + -The function fooH unbox all of its arguments, call the C -function fooC and box the corresponding arguments. +word, primitive type +address, primitive type +unsigned integer, primitive type +pointer, primitive type -One of the annoyances about _ccall_s is when the C types don't quite -match the Haskell compiler's ideas. For this, the _casm_ variant -may be just the ticket (NB: no chance of such code going -through a native-code generator): +A Word# is used for bit-twiddling operations. +It is the same size as an Int#, but has no sign +nor any arithmetic operations. + + +type Word# -- Same size/etc as Int# but *unsigned* +type Addr# -- A pointer from outside the "Haskell world" (from C, probably); + -- described under "arrays" + + +Word# +Addr# + + + +Word#s and Addr#s have +the usual comparison operations. Other +unboxed-Word ops (bit-twiddling and coercions): -import Addr -import CString +{gt,ge,eq,ne,lt,le}Word# :: Word# -> Word# -> Bool + +and#, or#, xor# :: Word# -> Word# -> Word# + -- standard bit ops. + +quotWord#, remWord# :: Word# -> Word# -> Word# + -- word (i.e. unsigned) versions are different from int + -- versions, so we have to provide these explicitly. + +not# :: Word# -> Word# + +shiftL#, shiftRL# :: Word# -> Int# -> Word# + -- shift left, right logical + +int2Word# :: Int# -> Word# -- just a cast, really +word2Int# :: Word# -> Int# + + +bit operations, Word and Addr +gtWord# +geWord# +eqWord# +neWord# +ltWord# +leWord# +and# +or# +xor# +not# +quotWord# +remWord# +shiftL# +shiftRA# +shiftRL# +int2Word# +word2Int# + + + +Unboxed-Addr ops (C casts, really): + + +{gt,ge,eq,ne,lt,le}Addr# :: Addr# -> Addr# -> Bool + +int2Addr# :: Int# -> Addr# +addr2Int# :: Addr# -> Int# +addr2Integer# :: Addr# -> (# Int#, ByteArray# #) + + +gtAddr# +geAddr# +eqAddr# +neAddr# +ltAddr# +leAddr# +int2Addr# +addr2Int# +addr2Integer# + + + +The casts between Int#, +Word# and Addr# +correspond to null operations at the machine level, but are required +to keep the Haskell type checker happy. + -oldGetEnv name - = _casm_ “%r = getenv((char *) %0);” name >>= \ litstring -> - return ( - if (litstring == nullAddr) then - Left ("Fail:oldGetEnv:"++name) - else - Right (unpackCString litstring) - ) + +Operations for indexing off of C pointers +(Addr#s) to snatch values are listed under +“arrays”. + + + + + +Arrays + + +arrays, primitive + + + +The type Array# elt is the type of primitive, +unpointed arrays of values of type elt. + + + + + +type Array# elt +Array# + + + +Array# is more primitive than a Haskell +array—indeed, the Haskell Array interface is +implemented using Array#—in that an +Array# is indexed only by +Int#s, starting at zero. It is also more +primitive by virtue of being unboxed. That doesn't mean that it isn't +a heap-allocated object—of course, it is. Rather, being unboxed +means that it is represented by a pointer to the array itself, and not +to a thunk which will evaluate to the array (or to bottom). The +components of an Array# are themselves boxed. + + + +The type ByteArray# is similar to +Array#, except that it contains just a string +of (non-pointer) bytes. -The first literal-literal argument to a _casm_ is like a printf -format: %r is replaced with the “result,” %0–%n-1 are -replaced with the 1st–nth arguments. As you can see above, it is an -easy way to do simple C casting. Everything said about _ccall_ goes -for _casm_ as well. + + +type ByteArray# + + +ByteArray# -The use of _casm_ in your code does pose a problem to the compiler -when it comes to generating an interface file for a freshly compiled -module. Included in an interface file is the unfolding (if any) of a -declaration. However, if a declaration's unfolding happens to contain -a _casm_, its unfolding will not be emitted into the interface -file even if it qualifies by all the other criteria. The reason why -the compiler prevents this from happening is that unfolding _casm_s -into an interface file unduly constrains how code that import your -module have to be compiled. If an imported declaration is unfolded and -it contains a _casm_, you now have to be using a compiler backend -capable of dealing with it (i.e., the C compiler backend). If you are -using the C compiler backend, the unfolded _casm_ may still cause you -problems since the C code snippet it contains may mention CPP symbols -that were in scope when compiling the original module are not when -compiling the importing module. +Arrays of these types are useful when a Haskell program wishes to +construct a value to pass to a C procedure. It is also possible to use +them to build (say) arrays of unboxed characters for internal use in a +Haskell program. Given these uses, ByteArray# +is deliberately a bit vague about the type of its components. +Operations are provided to extract values of type +Char#, Int#, +Float#, Double#, and +Addr# from arbitrary offsets within a +ByteArray#. (For type +Foo#, the $i$th offset gets you the $i$th +Foo#, not the Foo# at +byte-position $i$. Mumble.) (If you want a +Word#, grab an Int#, +then coerce it.) -If you're willing to put up with the drawbacks of doing cross-module -inlining of C code (GHC - A Better C Compiler :-), the option - will turn off the default behaviour. --funfold-casms-in-hi-file option +Lastly, we have static byte-arrays, of type +Addr# [mentioned previously]. (Remember +the duality between arrays and pointers in C.) Arrays of this types +are represented by a pointer to an array in the world outside Haskell, +so this pointer is not followed by the garbage collector. In other +respects they are just like ByteArray#. They +are only needed in order to pass values from C to Haskell. - -Literal-literals + +Reading and writing + + +Primitive arrays are linear, and indexed starting at zero. + + + +The size and indices of a ByteArray#, Addr#, and +MutableByteArray# are all in bytes. It's up to the program to +calculate the correct byte offset from the start of the array. This +allows a ByteArray# to contain a mixture of values of different +type, which is often needed when preparing data for and unpicking +results from C. (Umm…not true of indices…WDP 95/09) + + + +Should we provide some sizeOfDouble# constants? + -Literal-literals -The literal-literal argument to _casm_ can be made use of separately -from the _casm_ construct itself. Indeed, we've already used it: +Out-of-range errors on indexing should be caught by the code which +uses the primitive operation; the primitive operations themselves do +not check for out-of-range indexes. The intention is that the +primitive ops compile to one machine instruction or thereabouts. +We use the terms “reading” and “writing” to refer to accessing +mutable arrays (see ), and +“indexing” to refer to reading a value from an immutable +array. + + + +Immutable byte arrays are straightforward to index (all indices in bytes): -fooH :: Char -> Int -> Double -> Word -> IO Double -fooH c i d w = _ccall_ fooC (“stdin”::Addr) c i d w +indexCharArray# :: ByteArray# -> Int# -> Char# +indexIntArray# :: ByteArray# -> Int# -> Int# +indexAddrArray# :: ByteArray# -> Int# -> Addr# +indexFloatArray# :: ByteArray# -> Int# -> Float# +indexDoubleArray# :: ByteArray# -> Int# -> Double# + +indexCharOffAddr# :: Addr# -> Int# -> Char# +indexIntOffAddr# :: Addr# -> Int# -> Int# +indexFloatOffAddr# :: Addr# -> Int# -> Float# +indexDoubleOffAddr# :: Addr# -> Int# -> Double# +indexAddrOffAddr# :: Addr# -> Int# -> Addr# + -- Get an Addr# from an Addr# offset +indexCharArray# +indexIntArray# +indexAddrArray# +indexFloatArray# +indexDoubleArray# +indexCharOffAddr# +indexIntOffAddr# +indexFloatOffAddr# +indexDoubleOffAddr# +indexAddrOffAddr# -The first argument that's passed to fooC is given as a literal-literal, -that is, a literal chunk of C code that will be inserted into the generated -.hc code at the right place. +The last of these, indexAddrOffAddr#, extracts an Addr# using an offset +from another Addr#, thereby providing the ability to follow a chain of +C pointers. -A literal-literal is restricted to having a type that's an instance of -the CCallable class, see -for more information. +Something a bit more interesting goes on when indexing arrays of boxed +objects, because the result is simply the boxed object. So presumably +it should be entered—we never usually return an unevaluated +object! This is a pain: primitive ops aren't supposed to do +complicated things like enter objects. The current solution is to +return a single element unboxed tuple (see ). -Notice that literal-literals are by their very nature unfriendly to -native code generators, so exercise judgement about whether or not to -make use of them in your code. + + +indexArray# :: Array# elt -> Int# -> (# elt #) + + +indexArray# - -Using function headers - + +The state type -C calls, function headers +state, primitive type +State# -When generating C (using the directive), one can assist the -C compiler in detecting type errors by using the -#include directive -to provide .h files containing function headers. +The primitive type State# represents the state of a state +transformer. It is parameterised on the desired type of state, which +serves to keep states from distinct threads distinct from one another. +But the only effect of this parameterisation is in the type +system: all values of type State# are represented in the same way. +Indeed, they are all represented by nothing at all! The code +generator “knows” to generate no code, and allocate no registers +etc, for primitive states. -For example, + + +type State# s + + + + + +The type GHC.RealWorld is truly opaque: there are no values defined +of this type, and no operations over it. It is “primitive” in that +sense - but it is not unlifted! Its only role in life is to be +the type which distinguishes the IO state transformer. -typedef unsigned long *StgForeignObj; -typedef long StgInt; - -void initialiseEFS (StgInt size); -StgInt terminateEFS (void); -StgForeignObj emptyEFS(void); -StgForeignObj updateEFS (StgForeignObj a, StgInt i, StgInt x); -StgInt lookupEFS (StgForeignObj a, StgInt i); - - - - - -You can find appropriate definitions for StgInt, StgForeignObj, -etc using gcc on your architecture by consulting -ghc/includes/StgTypes.h. The following table summarises the -relationship between Haskell types and C types. - - - - - - - - - - -C type name - Haskell Type - - - - -StgChar - Char# - - - -StgInt - Int# - - - -StgWord - Word# - - - -StgAddr - Addr# - - - -StgFloat - Float# - - - -StgDouble - Double# - - - -StgArray - Array# - - - -StgByteArray - ByteArray# - - - -StgArray - MutableArray# - - - -StgByteArray - MutableByteArray# - - - -StgStablePtr - StablePtr# - - - -StgForeignObj - ForeignObj# - - - - - - - - -Note that this approach is only essential for returning -floats (or if sizeof(int) != sizeof(int *) on your -architecture) but is a Good Thing for anyone who cares about writing -solid code. You're crazy not to do it. +data RealWorld + + - -Subverting automatic unboxing with “stable pointers” - + +State of the world -stable pointers (Glasgow extension) +A single, primitive, value of type State# RealWorld is provided. -The arguments of a _ccall_ automatically unboxed before the -call. There are two reasons why this is usually the Right Thing to -do: + + +realWorld# :: State# RealWorld + + +realWorld# state object +(Note: in the compiler, not a PrimOp; just a mucho magic +Id. Exported from GHC, though). + - - + + + +Mutable arrays -C is a strict language: it would be excessively tedious to pass -unevaluated arguments and require the C programmer to force their -evaluation before using them. +mutable arrays +arrays, mutable +Corresponding to Array# and ByteArray#, we have the types of +mutable versions of each. In each case, the representation is a +pointer to a suitable block of (mutable) heap-allocated storage. + + + + +type MutableArray# s elt +type MutableByteArray# s + + +MutableArray# +MutableByteArray# - - + + +Allocation - Boxed values are stored on the Haskell heap and may be moved -within the heap if a garbage collection occurs—that is, pointers -to boxed objects are not stable. +mutable arrays, allocation +arrays, allocation +allocation, of mutable arrays - - + +Mutable arrays can be allocated. Only pointer-arrays are initialised; +arrays of non-pointers are filled in by “user code” rather than by +the array-allocation primitive. Reason: only the pointer case has to +worry about GC striking with a partly-initialised array. + + + + +newArray# :: Int# -> elt -> State# s -> (# State# s, MutableArray# s elt #) + +newCharArray# :: Int# -> State# s -> (# State# s, MutableByteArray# s elt #) +newIntArray# :: Int# -> State# s -> (# State# s, MutableByteArray# s elt #) +newAddrArray# :: Int# -> State# s -> (# State# s, MutableByteArray# s elt #) +newFloatArray# :: Int# -> State# s -> (# State# s, MutableByteArray# s elt #) +newDoubleArray# :: Int# -> State# s -> (# State# s, MutableByteArray# s elt #) + + +newArray# +newCharArray# +newIntArray# +newAddrArray# +newFloatArray# +newDoubleArray# -It is possible to subvert the unboxing process by creating a “stable -pointer” to a value and passing the stable pointer instead. For -example, to pass/return an integer lazily to C functions storeC and -fetchC might write: +The size of a ByteArray# is given in bytes. + + + + + +Reading and writing + + +arrays, reading and writing -storeH :: Int -> IO () -storeH x = makeStablePtr x >>= \ stable_x -> - _ccall_ storeC stable_x +readArray# :: MutableArray# s elt -> Int# -> State# s -> (# State# s, elt #) +readCharArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Char# #) +readIntArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Int# #) +readAddrArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Addr# #) +readFloatArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Float# #) +readDoubleArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Double# #) + +writeArray# :: MutableArray# s elt -> Int# -> elt -> State# s -> State# s +writeCharArray# :: MutableByteArray# s -> Int# -> Char# -> State# s -> State# s +writeIntArray# :: MutableByteArray# s -> Int# -> Int# -> State# s -> State# s +writeAddrArray# :: MutableByteArray# s -> Int# -> Addr# -> State# s -> State# s +writeFloatArray# :: MutableByteArray# s -> Int# -> Float# -> State# s -> State# s +writeDoubleArray# :: MutableByteArray# s -> Int# -> Double# -> State# s -> State# s + + +readArray# +readCharArray# +readIntArray# +readAddrArray# +readFloatArray# +readDoubleArray# +writeArray# +writeCharArray# +writeIntArray# +writeAddrArray# +writeFloatArray# +writeDoubleArray# + -fetchH :: IO Int -fetchH x = _ccall_ fetchC >>= \ stable_x -> - deRefStablePtr stable_x >>= \ x -> - freeStablePtr stable_x >> - return x + + + +Equality + + +arrays, testing for equality + + + +One can take “equality” of mutable arrays. What is compared is the +name or reference to the mutable array, not its contents. + + + + + +sameMutableArray# :: MutableArray# s elt -> MutableArray# s elt -> Bool +sameMutableByteArray# :: MutableByteArray# s -> MutableByteArray# s -> Bool +sameMutableArray# +sameMutableByteArray# + + + +Freezing mutable arrays + -The garbage collector will refrain from throwing a stable pointer away -until you explicitly call one of the following from C or Haskell. +arrays, freezing mutable +freezing mutable arrays +mutable arrays, freezing + + + +Only unsafe-freeze has a primitive. (Safe freeze is done directly in Haskell +by copying the array and then using unsafeFreeze.) -void freeStablePointer( StgStablePtr stablePtrToToss ) -freeStablePtr :: StablePtr a -> IO () +unsafeFreezeArray# :: MutableArray# s elt -> State# s -> (# State# s, Array# s elt #) +unsafeFreezeByteArray# :: MutableByteArray# s -> State# s -> (# State# s, ByteArray# #) +unsafeFreezeArray# +unsafeFreezeByteArray# + + + + + +Synchronizing variables (M-vars) + -As with the use of free in C programs, GREAT CARE SHOULD BE -EXERCISED to ensure these functions are called at the right time: too -early and you get dangling references (and, if you're lucky, an error -message from the runtime system); too late and you get space leaks. +synchronising variables (M-vars) +M-Vars -And to force evaluation of the argument within fooC, one would -call one of the following C functions (according to type of argument). +Synchronising variables are the primitive type used to implement +Concurrent Haskell's MVars (see the Concurrent Haskell paper for +the operational behaviour of these operations). -void performIO ( StgStablePtr stableIndex /* StablePtr s (IO ()) */ ); -StgInt enterInt ( StgStablePtr stableIndex /* StablePtr s Int */ ); -StgFloat enterFloat ( StgStablePtr stableIndex /* StablePtr s Float */ ); +type MVar# s elt -- primitive + +newMVar# :: State# s -> (# State# s, MVar# s elt #) +takeMVar# :: SynchVar# s elt -> State# s -> (# State# s, elt #) +putMVar# :: SynchVar# s elt -> State# s -> State# s +SynchVar# +newSynchVar# +takeMVar +putMVar + + + + + + + +Primitive state-transformer monad + + + +state transformers (Glasgow extensions) +ST monad (Glasgow extension) + + + +This monad underlies our implementation of arrays, mutable and +immutable, and our implementation of I/O, including “C calls”. + + + +The ST library, which provides access to the +ST monad, is described in . + + + + + +Primitive arrays, mutable and otherwise + + + +primitive arrays (Glasgow extension) +arrays, primitive (Glasgow extension) -performIO -enterInt -enterFloat +GHC knows about quite a few flavours of Large Swathes of Bytes. + + + +First, GHC distinguishes between primitive arrays of (boxed) Haskell +objects (type Array# obj) and primitive arrays of bytes (type +ByteArray#). + + + +Second, it distinguishes between… + + + +Immutable: + + +Arrays that do not change (as with “standard” Haskell arrays); you +can only read from them. Obviously, they do not need the care and +attention of the state-transformer monad. + + + + +Mutable: + + +Arrays that may be changed or “mutated.” All the operations on them +live within the state-transformer monad and the updates happen +in-place. + + + + +“Static” (in C land): + + +A C routine may pass an Addr# pointer back into Haskell land. There +are then primitive operations with which you may merrily grab values +over in C land, by indexing off the “static” pointer. + + + + +“Stable” pointers: + + +If, for some reason, you wish to hand a Haskell pointer (i.e., +not an unboxed value) to a C routine, you first make the +pointer “stable,” so that the garbage collector won't forget that it +exists. That is, GHC provides a safe way to pass Haskell pointers to +C. -Nota Bene: _ccall_GC__ccall_GC_ must be used if any of -these functions are used. +Please see for more details. - - - - -Foreign objects: pointing outside the Haskell heap - - + + + +“Foreign objects”: + -foreign objects (Glasgow extension) +A “foreign object” is a safe way to pass an external object (a +C-allocated pointer, say) to Haskell and have Haskell do the Right +Thing when it no longer references the object. So, for example, C +could pass a large bitmap over to Haskell and say “please free this +memory when you're done with it.” -There are two types that GHC programs can use to reference -(heap-allocated) objects outside the Haskell world: Addr and -ForeignObj. +Please see for more details. - - -If you use Addr, it is up to you to the programmer to arrange -allocation and deallocation of the objects. + + + -If you use ForeignObj, GHC's garbage collector will call upon the -user-supplied finaliser function to free the object when the -Haskell world no longer can access the object. (An object is -associated with a finaliser function when the abstract -Haskell type ForeignObj is created). The finaliser function is -expressed in C, and is passed as argument the object: +The libraries documentatation gives more details on all these +“primitive array” types and the operations on them. - + - -void foreignFinaliser ( StgForeignObj fo ) - - + +Pattern guards -when the Haskell world can no longer access the object. Since -ForeignObjs only get released when a garbage collection occurs, we -provide ways of triggering a garbage collection from within C and from -within Haskell. +Pattern guards (Glasgow extension) +The discussion that follows is an abbreviated version of Simon Peyton Jones's original proposal. (Note that the proposal was written before pattern guards were implemented, so refers to them as unimplemented.) +Suppose we have an abstract data type of finite maps, with a +lookup operation: -void GarbageCollect() -performGC :: IO () +lookup :: FiniteMap -> Int -> Maybe Int +The lookup returns Nothing if the supplied key is not in the domain of the mapping, and (Just v) otherwise, +where v is the value that the key maps to. Now consider the following definition: + +clunky env var1 var2 | ok1 && ok2 = val1 + val2 +| otherwise = var1 + var2 +where + m1 = lookup env var1 + m2 = lookup env var2 + ok1 = maybeToBool m1 + ok2 = maybeToBool m2 + val1 = expectJust m1 + val2 = expectJust m2 + + -More information on the programmers' interface to ForeignObj can be -found in the library documentation. +The auxiliary functions are - - - -Avoiding monads - + +maybeToBool :: Maybe a -> Bool +maybeToBool (Just x) = True +maybeToBool Nothing = False - -C calls to `pure C' -unsafePerformIO - +expectJust :: Maybe a -> a +expectJust (Just x) = x +expectJust Nothing = error "Unexpected Nothing" + -The _ccall_ construct is part of the IO monad because 9 out of 10 -uses will be to call imperative functions with side effects such as -printf. Use of the monad ensures that these operations happen in a -predictable order in spite of laziness and compiler optimisations. +What is clunky doing? The guard ok1 && +ok2 checks that both lookups succeed, using +maybeToBool to convert the Maybe +types to booleans. The (lazily evaluated) expectJust +calls extract the values from the results of the lookups, and binds the +returned values to val1 and val2 +respectively. If either lookup fails, then clunky takes the +otherwise case and returns the sum of its arguments. -To avoid having to be in the monad to call a C function, it is -possible to use unsafePerformIO, which is available from the -IOExts module. There are three situations where one might like to -call a C function from outside the IO world: +This is certainly legal Haskell, but it is a tremendously verbose and +un-obvious way to achieve the desired effect. Arguably, a more direct way +to write clunky would be to use case expressions: - - - - - - -Calling a function with no side-effects: - -atan2d :: Double -> Double -> Double -atan2d y x = unsafePerformIO (_ccall_ atan2d y x) - -sincosd :: Double -> (Double, Double) -sincosd x = unsafePerformIO $ do - da <- newDoubleArray (0, 1) - _casm_ “sincosd( %0, &((double *)%1[0]), &((double *)%1[1]) );” x da - s <- readDoubleArray da 0 - c <- readDoubleArray da 1 - return (s, c) +clunky env var1 var1 = case lookup env var1 of + Nothing -> fail + Just val1 -> case lookup env var2 of + Nothing -> fail + Just val2 -> val1 + val2 +where + fail = val1 + val2 - + +This is a bit shorter, but hardly better. Of course, we can rewrite any set +of pattern-matching, guarded equations as case expressions; that is +precisely what the compiler does when compiling equations! The reason that +Haskell provides guarded equations is because they allow us to write down +the cases we want to consider, one at a time, independently of each other. +This structure is hidden in the case version. Two of the right-hand sides +are really the same (fail), and the whole expression +tends to become more and more indented. - - - Calling a set of functions which have side-effects but which can -be used in a purely functional manner. - -For example, an imperative implementation of a purely functional -lookup-table might be accessed using the following functions. - +Here is how I would write clunky: + -empty :: EFS x -update :: EFS x -> Int -> x -> EFS x -lookup :: EFS a -> Int -> a - -empty = unsafePerformIO (_ccall_ emptyEFS) - -update a i x = unsafePerformIO $ - makeStablePtr x >>= \ stable_x -> - _ccall_ updateEFS a i stable_x - -lookup a i = unsafePerformIO $ - _ccall_ lookupEFS a i >>= \ stable_x -> - deRefStablePtr stable_x +clunky env var1 var1 + | Just val1 <- lookup env var1 + , Just val2 <- lookup env var2 + = val1 + val2 +...other equations for clunky... - -You will almost always want to use ForeignObjs with this. - + +The semantics should be clear enough. The qualifers are matched in order. +For a <- qualifier, which I call a pattern guard, the +right hand side is evaluated and matched against the pattern on the left. +If the match fails then the whole guard fails and the next equation is +tried. If it succeeds, then the appropriate binding takes place, and the +next qualifier is matched, in the augmented environment. Unlike list +comprehensions, however, the type of the expression to the right of the +<- is the same as the type of the pattern to its +left. The bindings introduced by pattern guards scope over all the +remaining guard qualifiers, and over the right hand side of the equation. - - - Calling a side-effecting function even though the results will -be unpredictable. For example the trace function is defined by: - +Just as with list comprehensions, boolean expressions can be freely mixed +with among the pattern guards. For example: + -trace :: String -> a -> a -trace string expr - = unsafePerformIO ( - ((_ccall_ PreTraceHook sTDERR{-msg-}):: IO ()) >> - fputs sTDERR string >> - ((_ccall_ PostTraceHook sTDERR{-msg-}):: IO ()) >> - return expr ) - where - sTDERR = (“stderr” :: Addr) +f x | [y] <- x + , y > 3 + , Just z <- h y + = ... - -(This kind of use is not highly recommended—it is only really -useful in debugging code.) - - - - - + +Haskell's current guards therefore emerge as a special case, in which the +qualifier list has just one element, a boolean expression. + - + + The foreign interface + + The foreign interface consists of the following components: + + + + The Foreign Function Interface language specification + (included in this manual, in ). + + + + The Foreign module (see ) collects together several interfaces + which are useful in specifying foreign language + interfaces, including the following: + + + + The ForeignObj module (see ), for managing pointers from + Haskell into the outside world. + + + + The StablePtr module (see ), for managing pointers + into Haskell from the outside world. + + + + The CTypes module (see ) gives Haskell equivalents for the + standard C datatypes, for use in making Haskell bindings + to existing C libraries. + + + + The CTypesISO module (see ) gives Haskell equivalents for C + types defined by the ISO C standard. + + + + The Storable library, for + primitive marshalling of data types between Haskell and + the foreign language. + + + + + + +The following sections also give some hints and tips on the use +of the foreign function interface in GHC. - -C-calling “gotchas” checklist +<Sect2 id="glasgow-foreign-headers"> +<Title>Using function headers -C call dangers -CCallable -CReturnable - - - -And some advice, too. +C calls, function headers - - - - - - For modules that use _ccall_s, etc., compile with -.-fvia-C option You don't have to, but you should. - -Also, use the flag (hack) to inform the C -compiler of the fully-prototyped types of all the C functions you -call. ( says more about this…) - -This scheme is the only way that you will get any -typechecking of your _ccall_s. (It shouldn't be that way, but…). -GHC will pass the flag to gcc so that you'll get warnings -if any _ccall_ed functions have no prototypes. - +When generating C (using the directive), one can assist the +C compiler in detecting type errors by using the -#include directive +to provide .h files containing function headers. - - -Try to avoid _ccall_s to C functions that take float -arguments or return float results. Reason: if you do, you will -become entangled in (ANSI?) C's rules for when arguments/results are -promoted to doubles. It's a nightmare and just not worth it. -Use doubles if possible. - -If you do use floats, check and re-check that the right thing is -happening. Perhaps compile with and look at -the intermediate C (.hc). - +For example, - - - - - The compiler uses two non-standard type-classes when -type-checking the arguments and results of _ccall_: the arguments -(respectively result) of _ccall_ must be instances of the class -CCallable (respectively CReturnable). Both classes may be -imported from the module CCall, but this should only be -necessary if you want to define a new instance. (Neither class -defines any methods—their only function is to keep the -type-checker happy.) - -The type checker must be able to figure out just which of the -C-callable/returnable types is being used. If it can't, you have to -add type signatures. For example, - - - -f x = _ccall_ foo x - - - -is not good enough, because the compiler can't work out what type x -is, nor what type the _ccall_ returns. You have to write, say: - - - -f :: Int -> IO Double -f x = _ccall_ foo x - - - -This table summarises the standard instances of these classes. - - - - - - - - - -Type -CCallable -CReturnable -Which is probably… - - - -Char - Yes - Yes - unsigned char - - - -Int - Yes - Yes - long int - - - -Word - Yes - Yes - unsigned long int - - - -Addr - Yes - Yes - void * - - - -Float - Yes - Yes - float - - - -Double - Yes - Yes - double - - - -() - No - Yes - void - - - -[Char] - Yes - No - char * (null-terminated) - - - -Array - Yes - No - unsigned long * - - - -ByteArray - Yes - No - unsigned long * - - - -MutableArray - Yes - No - unsigned long * - - - -MutableByteArray - Yes - No - unsigned long * - - - -State - Yes - Yes - nothing! - - - -StablePtr - Yes - Yes - unsigned long * - - - -ForeignObjs - Yes - Yes - see later - - - - - - - -Actually, the Word type is defined as being the same size as a -pointer on the target architecture, which is probably -unsigned long int. - -The brave and careful programmer can add their own instances of these -classes for the following types: - - - - -A boxed-primitive type may be made an instance of both -CCallable and CReturnable. - -A boxed primitive type is any data type with a -single unary constructor with a single primitive argument. For -example, the following are all boxed primitive types: - - - -Int -Double -data XDisplay = XDisplay Addr# -data EFS a = EFS# ForeignObj# - - - -instance CCallable (EFS a) -instance CReturnable (EFS a) - - - - - - - - - Any datatype with a single nullary constructor may be made an -instance of CReturnable. For example: +#include "HsFFI.h" - - -data MyVoid = MyVoid -instance CReturnable MyVoid +void initialiseEFS (HsInt size); +HsInt terminateEFS (void); +HsForeignObj emptyEFS(void); +HsForeignObj updateEFS (HsForeignObj a, HsInt i, HsInt x); +HsInt lookupEFS (HsForeignObj a, HsInt i); - - - - - - - - As at version 2.09, String (i.e., [Char]) is still -not a CReturnable type. - -Also, the now-builtin type PackedString is neither -CCallable nor CReturnable. (But there are functions in -the PackedString interface to let you get at the necessary bits…) - - - - - - - - - - - The code-generator will complain if you attempt to use %r in -a _casm_ whose result type is IO (); or if you don't use %r -precisely once for any other result type. These messages are -supposed to be helpful and catch bugs—please tell us if they wreck -your life. - - - - - - If you call out to C code which may trigger the Haskell garbage -collector or create new threads (examples of this later…), then you -must use the _ccall_GC__ccall_GC_ primitive or -_casm_GC__casm_GC_ primitive variant of C-calls. (This -does not work with the native code generator—use .) This -stuff is hairy with a capital H! - - - - + The types HsInt, + HsForeignObj etc. are described in . - + Note that this approach is only + essential for returning + floats (or if sizeof(int) != + sizeof(int *) on your architecture) but is a Good + Thing for anyone who cares about writing solid code. You're + crazy not to do it. @@ -1152,12 +1732,11 @@ stuff is hairy with a capital H! -This section documents GHC's implementation of multi-paramter type +This section documents GHC's implementation of multi-parameter type classes. There's lots of background in the paper Type classes: exploring the design space (Simon Peyton -Jones, Mark Jones, Erik Meijer). +URL="http://research.microsoft.com/~simonpj/multi.ps.gz" >Type +classes: exploring the design space (Simon Peyton Jones, Mark +Jones, Erik Meijer). @@ -1186,7 +1765,7 @@ type: - forall tv1..tvn (c1, ...,cn) => type + forall tv1..tvn (c1, ...,cn) => type @@ -1214,7 +1793,7 @@ ambiguity. Here, for example, is an illegal type: - forall a. Eq a => Int + forall a. Eq a => Int @@ -1238,7 +1817,7 @@ universally quantified type variable b: - forall a. C a b => burble + forall a. C a b => burble @@ -1247,7 +1826,7 @@ mention a: - forall a. Eq b => burble + forall a. Eq b => burble @@ -1279,8 +1858,8 @@ are perfectly OK - f :: Eq (m a) => [m a] -> [m a] - g :: Eq [a] => ... + f :: Eq (m a) => [m a] -> [m a] + g :: Eq [a] => ... @@ -1305,7 +1884,7 @@ This choice recovers principal types, a property that Haskell 1.4 does not have. class Collection c a where - union :: c a -> c a -> c a + union :: c a -> c a -> c a ...etc. @@ -1323,10 +1902,10 @@ this is OK: class C a where { - op :: D b => a -> b -> b + op :: D b => a -> b -> b } - class C a => D a where { ... } + class C a => D a where { ... } @@ -1345,11 +1924,11 @@ be acyclic. So these class declarations are OK: - class Functor (m k) => FiniteMap m k where + class Functor (m k) => FiniteMap m k where ... - class (Monad m, Monad (t m)) => Transform t m where - lift :: m a -> (t m) a + class (Monad m, Monad (t m)) => Transform t m where + lift :: m a -> (t m) a @@ -1367,7 +1946,7 @@ Thus: class Collection c a where - mapC :: Collection c b => (a->b) -> c a -> c b + mapC :: Collection c b => (a->b) -> c a -> c b @@ -1378,7 +1957,7 @@ is OK because the constraint (Collection a b) mentions class C a where - op :: Eq a => (a,b) -> (a,b) + op :: Eq a => (a,b) -> (a,b) @@ -1389,8 +1968,8 @@ superclass context: - class Eq a => C a where - op ::(a,b) -> (a,b) + class Eq a => C a where + op ::(a,b) -> (a,b) @@ -1410,7 +1989,7 @@ the class type variables. For example: class Coll s a where empty :: s - insert :: s -> a -> s + insert :: s -> a -> s @@ -1425,7 +2004,7 @@ example, Coll might be rewritten class Coll s a where empty :: s a - insert :: s a -> a -> s a + insert :: s a -> a -> s a @@ -1439,8 +2018,8 @@ class like this: class CollE s where empty :: s - class CollE s => Coll s a where - insert :: s -> a -> s + class CollE s => Coll s a where + insert :: s -> a -> s @@ -1453,7 +2032,7 @@ class like this: - + Instance declarations @@ -1467,8 +2046,8 @@ declarations - instance context1 => C type1 where ... - instance context2 => C type2 where ... + instance context1 => C type1 where ... + instance context2 => C type2 where ... @@ -1544,7 +2123,7 @@ change that decision, at least for Main.) There are no restrictions on the type in an instance head, except that at least one must not be a type variable. -The instance "head" is the bit after the "=>" in an instance decl. For +The instance "head" is the bit after the "=>" in an instance decl. For example, these are OK: @@ -1573,7 +2152,7 @@ loop if it wasn't excluded: - instance C a => C a where ... + instance C a => C a where ... @@ -1594,9 +2173,9 @@ effect of a "class synonym": - class (C1 a, C2 a, C3 a) => C a where { } + class (C1 a, C2 a, C3 a) => C a where { } - instance (C1 a, C2 a, C3 a) => C a where { } + instance (C1 a, C2 a, C3 a) => C a where { } @@ -1604,7 +2183,7 @@ This allows you to write shorter signatures: - f :: C a => ... + f :: C a => ... @@ -1612,7 +2191,7 @@ instead of - f :: (C1 a, C2 a, C3 a) => ... + f :: (C1 a, C2 a, C3 a) => ... @@ -1671,7 +2250,7 @@ be type variables. Thus -instance C a b => Eq (a,b) where ... +instance C a b => Eq (a,b) where ... @@ -1679,7 +2258,7 @@ is OK, but -instance C Int b => Foo b where ... +instance C Int b => Foo b where ... @@ -1717,7 +2296,7 @@ syntax for this now agrees with Hugs's, namely: - forall a b. (Ord a, Eq b) => a -> b -> a + forall a b. (Ord a, Eq b) => a -> b -> a @@ -1735,7 +2314,7 @@ allows us to say exactly what this means. For example: - g :: b -> b + g :: b -> b @@ -1747,7 +2326,7 @@ means this: - g :: forall b. (b -> b) + g :: forall b. (b -> b) @@ -1768,13 +2347,13 @@ the types of the constructor arguments. Here are several examples: -data T a = T1 (forall b. b -> b -> b) a +data T a = T1 (forall b. b -> b -> b) a -data MonadT m = MkMonad { return :: forall a. a -> m a, - bind :: forall a b. m a -> (a -> m b) -> m b +data MonadT m = MkMonad { return :: forall a. a -> m a, + bind :: forall a b. m a -> (a -> m b) -> m b } -newtype Swizzle = MkSwizzle (Ord a => [a] -> [a]) +newtype Swizzle = MkSwizzle (Ord a => [a] -> [a]) @@ -1787,11 +2366,11 @@ types, in which there is a for-all in the argument types.: -T1 :: forall a. (forall b. b -> b -> b) -> a -> T1 a -MkMonad :: forall m. (forall a. a -> m a) - -> (forall a b. m a -> (a -> m b) -> m b) - -> MonadT m -MkSwizzle :: (Ord a => [a] -> [a]) -> Swizzle +T1 :: forall a. (forall b. b -> b -> b) -> a -> T a +MkMonad :: forall m. (forall a. a -> m a) + -> (forall a b. m a -> (a -> m b) -> m b) + -> MonadT m +MkSwizzle :: (Ord a => [a] -> [a]) -> Swizzle @@ -1810,13 +2389,13 @@ As for type signatures, implicit quantification happens for non-overloaded types too. So if you write this: - data T a = MkT (Either a b) (b -> b) + data T a = MkT (Either a b) (b -> b) it's just as if you had written this: - data T a = MkT (forall b. Either a b) (forall b. b -> b) + data T a = MkT (forall b. Either a b) (forall b. b -> b) That is, since the type variable b isn't in scope, it's @@ -1838,15 +2417,15 @@ the constructor to suitable values, just as usual. For example, -(T1 (\xy->x) 3) :: T Int +(T1 (\xy->x) 3) :: T Int (MkSwizzle sort) :: Swizzle (MkSwizzle reverse) :: Swizzle (let r x = Just x b m k = case m of - Just y -> k y - Nothing -> Nothing + Just y -> k y + Nothing -> Nothing in MkMonad r b) :: MonadT Maybe @@ -1872,16 +2451,16 @@ polymorphic types. For example: - f :: T a -> a -> (a, Char) + f :: T a -> a -> (a, Char) f (T1 f k) x = (f k x, f 'c' 'd') - g :: (Ord a, Ord b) => Swizzle -> [a] -> (a -> b) -> [b] + g :: (Ord a, Ord b) => Swizzle -> [a] -> (a -> b) -> [b] g (MkSwizzle s) xs f = s (map f (s xs)) - h :: MonadT m -> [m a] -> m [a] + h :: MonadT m -> [m a] -> m [a] h m [] = return m [] - h m (x:xs) = bind m x $ \y -> - bind m (h m xs) $ \ys -> + h m (x:xs) = bind m x $ \y -> + bind m (h m xs) $ \ys -> return m (y:ys) @@ -1901,7 +2480,7 @@ For example: newtype TIM s a = TIM (ST s (Maybe a)) - runTIM :: (forall s. TIM s a) -> Maybe a + runTIM :: (forall s. TIM s a) -> Maybe a runTIM (TIM m) = runST m @@ -1913,8 +2492,8 @@ an argument of type (forall s. TIM s a). Instead you must bind the variable and pattern match in the right hand side: - runTIM :: (forall s. TIM s a) -> Maybe a - runTIM tm = case tm of { TIM m -> runST m } + runTIM :: (forall s. TIM s a) -> Maybe a + runTIM tm = case tm of { TIM m -> runST m } The tm on the right hand side is (invisibly) instantiated, like @@ -1950,7 +2529,7 @@ this rule. The restriction makes type inference feasible. In the illegal example, the sub-expression MkSwizzle has the -polymorphic type (Ord b => [b] -> [b]) -> Swizzle and is not +polymorphic type (Ord b => [b] -> [b]) -> Swizzle and is not a sub-expression of an enclosing application. On the other hand, this expression is OK: @@ -1958,14 +2537,14 @@ expression is OK: - map (T1 (\a b -> a)) [1,2,3] + map (T1 (\a b -> a)) [1,2,3] even though it involves a partial application of T1, because -the sub-expression T1 (\a b -> a) has type Int -> T +the sub-expression T1 (\a b -> a) has type Int -> T Int. @@ -2010,7 +2589,7 @@ constructors), thus: - mkTs :: (forall b. b -> b -> b) -> a -> [T a] + mkTs :: (forall b. b -> b -> b) -> a -> [T a] mkTs f x y = [T1 f x, T1 f y] @@ -2018,7 +2597,7 @@ constructors), thus: This type signature tells the compiler to attribute f with -the polymorphic type (forall b. b -> b -> b) when type +the polymorphic type (forall b. b -> b -> b) when type checking the body of mkTs, so now the application of T1 is fine. @@ -2038,8 +2617,8 @@ grammar: -rank2type ::= [forall tyvars .] [context =>] funty -funty ::= ([forall tyvars .] [context =>] ty) -> funty +rank2type ::= [forall tyvars .] [context =>] funty +funty ::= ([forall tyvars .] [context =>] ty) -> funty | ty ty ::= ...current Haskell monotype syntax... @@ -2060,8 +2639,8 @@ define mkTs like this: -mkTs :: (forall b. b -> b -> b) -> a -> [T a] -mkTs = \ f x y -> [T1 f x, T1 f y] +mkTs :: (forall b. b -> b -> b) -> a -> [T a] +mkTs = \ f x y -> [T1 f x, T1 f y] @@ -2078,6 +2657,53 @@ rank-2 types as applied to data constructors. + + +Type synonyms and hoisting + + + +GHC also allows you to write a forall in a type synonym, thus: + + type Discard a = forall b. a -> b -> a + + f :: Discard a + f x y = x + +However, it is often convenient to use these sort of synonyms at the right hand +end of an arrow, thus: + + type Discard a = forall b. a -> b -> a + + g :: Int -> Discard Int + g x y z = x+y + +Simply expanding the type synonym would give + + g :: Int -> (forall b. Int -> b -> Int) + +but GHC "hoists" the forall to give the isomorphic type + + g :: forall b. Int -> Int -> b -> Int + +In general, the rule is this: to determine the type specified by any explicit +user-written type (e.g. in a type signature), GHC expands type synonyms and then repeatedly +performs the transformation: + + type1 -> forall a. type2 +==> + forall a. type1 -> type2 + +(In fact, GHC tries to retain as much synonym information as possible for use in +error messages, but that is a usability issue.) This rule applies, of course, whether +or not the forall comes from a synonym. For example, here is another +valid way to write g's type signature: + + g :: Int -> Int -> forall b. b -> Int + + + + @@ -2095,7 +2721,7 @@ proved very useful. Here's the idea. Consider the declaration: - data Foo = forall a. MkFoo a (a -> Bool) + data Foo = forall a. MkFoo a (a -> Bool) | Nil @@ -2108,7 +2734,7 @@ The data type Foo has two constructors with types: - MkFoo :: forall a. a -> (a -> Bool) -> Foo + MkFoo :: forall a. a -> (a -> Bool) -> Foo Nil :: Foo @@ -2157,7 +2783,7 @@ apply fn to val to get a boolean. For e - f :: Foo -> Bool + f :: Foo -> Bool f (MkFoo val fn) = fn val @@ -2182,7 +2808,7 @@ Simply that MkFoo has the (nearly) isomorphic type - MkFoo :: (exists a . (a, a -> Bool)) -> Foo + MkFoo :: (exists a . (a, a -> Bool)) -> Foo @@ -2206,8 +2832,8 @@ arbitrary contexts before the constructor. For example: -data Baz = forall a. Eq a => Baz1 a a - | forall b. Show b => Baz2 b (b -> b) +data Baz = forall a. Eq a => Baz1 a a + | forall b. Show b => Baz2 b (b -> b) @@ -2219,8 +2845,8 @@ The two constructors have the types you'd expect: -Baz1 :: forall a. Eq a => a -> a -> Baz -Baz2 :: forall b. Show b => b -> (b -> b) -> Baz +Baz1 :: forall a. Eq a => a -> a -> Baz +Baz2 :: forall b. Show b => b -> (b -> b) -> Baz @@ -2235,7 +2861,7 @@ So this program is legal: - f :: Baz -> String + f :: Baz -> String f (Baz1 p q) | p == q = "Yes" | otherwise = "No" f (Baz1 v fn) = show (fn v) @@ -2288,7 +2914,7 @@ ask what type f1 has: - f1 :: Foo -> a -- Weird! + f1 :: Foo -> a -- Weird! @@ -2297,7 +2923,7 @@ this: - f1 :: forall a. Foo -> a -- Wrong! + f1 :: forall a. Foo -> a -- Wrong! @@ -2351,7 +2977,7 @@ declarations. So this is illegal: - newtype T = forall a. Ord a => MkT a + newtype T = forall a. Ord a => MkT a @@ -2418,7 +3044,7 @@ could define a function like the following: -assert :: Bool -> a -> a +assert :: Bool -> a -> a assert False x = error "assertion failed!" assert _ x = x @@ -2445,8 +3071,8 @@ use of assert in the user's source: -kelvinToC :: Double -> Double -kelvinToC k = assert (k &gt;= 0.0) (k+273.15) +kelvinToC :: Double -> Double +kelvinToC k = assert (k >= 0.0) (k+273.15) @@ -2459,7 +3085,7 @@ assertion was made, -assert pred val ==> assertError "Main.hs|15" pred val +assert pred val ==> assertError "Main.hs|15" pred val @@ -2479,7 +3105,8 @@ expressions of the form assert pred e will be rewritten to Assertion failures can be caught, see the documentation for the -Hugs/GHC Exception library for information of how. +Exception library () +for the details. @@ -2574,7 +3201,7 @@ into scope (except in the type signature itself!). So this is illegal: - f :: a -> a + f :: a -> a f x = x::a @@ -2604,7 +3231,7 @@ scope over the methods defined in the where part. For exampl class C a where - op :: [a] -> a + op :: [a] -> a op xs = let ys::[a] ys = reverse xs @@ -2638,7 +3265,7 @@ no scoping associated with the names of the type variables in a separate type si - f :: [a] -> [a] + f :: [a] -> [a] f (xs::[b]) = reverse xs @@ -2691,7 +3318,7 @@ For example, the following all fail to type check: k (x::a) True = ... -- a unifies with Int k (x::Int) False = ... - w :: [b] -> [b] + w :: [b] -> [b] w (x::a) = x -- a unifies with [b] @@ -2744,9 +3371,9 @@ you want: - f :: Int -> [a] -> [a] - f n :: ([a] -> [a]) = let g (x::a, y::a) = (y,x) - in \xs -> map g (reverse xs `zip` xs) + f :: Int -> [a] -> [a] + f n :: ([a] -> [a]) = let g (x::a, y::a) = (y,x) + in \xs -> map g (reverse xs `zip` xs) @@ -2791,7 +3418,7 @@ in lambda abstractions: - (\ (x::a, y) :: a -> x) + (\ (x::a, y) :: a -> x) @@ -2802,7 +3429,7 @@ For example: f1 (x::c) = f1 x -- ok - f2 = \(x::c) -> f2 x -- not ok + f2 = \(x::c) -> f2 x -- not ok @@ -2821,7 +3448,7 @@ in case expressions: - case e of { (x::a, y) :: a -> x } + case e of { (x::a, y) :: a -> x } @@ -2832,7 +3459,7 @@ Thus this is OK: - case (True,False) of { (x::a, y) -> x } + case (True,False) of { (x::a, y) -> x } @@ -2842,7 +3469,7 @@ also OK to say: - case (True,False) of { (x::Bool, y) -> x } + case (True,False) of { (x::Bool, y) -> x } @@ -2858,7 +3485,7 @@ consider how one would parse this: - \ x :: a -> b -> x + \ x :: a -> b -> x @@ -2892,7 +3519,7 @@ though it binds a type variable: - f :: (b->b) = \(x::b) -> x + f :: (b->b) = \(x::b) -> x @@ -2908,7 +3535,7 @@ restriction. Thus: - g :: a -> a -> Bool = \x y. x==y + g :: a -> a -> Bool = \x y. x==y @@ -2937,7 +3564,7 @@ For example: data T = forall a. MkT [a] - f :: T -> T + f :: T -> T f (MkT [t::a]) = MkT t3 where t3::[a] = [t,t,t] @@ -2993,7 +3620,7 @@ The sledgehammer you can bring to bear is the INLINEINLINE pragma pragma, used thusly: -key_function :: Int -> String -> (Bool, Double) +key_function :: Int -> String -> (Bool, Double) #ifdef __GLASGOW_HASKELL__ {-# INLINE key_function #-} @@ -3067,7 +3694,7 @@ types. Thus, if you have an overloaded function: -hammeredLookup :: Ord key => [(key, value)] -> key -> value +hammeredLookup :: Ord key => [(key, value)] -> key -> value @@ -3077,7 +3704,7 @@ If it is heavily used on lists with Widget keys, you could specialise it as follows: -{-# SPECIALIZE hammeredLookup :: [(Widget, value)] -> Widget -> value #-} +{-# SPECIALIZE hammeredLookup :: [(Widget, value)] -> Widget -> value #-} @@ -3102,10 +3729,10 @@ NOTE: the =blah feature isn't implemented in GHC 4.xx. An example in which the = blah form will Win Big: -toDouble :: Real a => a -> Double +toDouble :: Real a => a -> Double toDouble = fromRational . toRational -{-# SPECIALIZE toDouble :: Int -> Double = i2d #-} +{-# SPECIALIZE toDouble :: Int -> Double = i2d #-} i2d (I# i) = D# (int2Double# i) -- uses Glasgow prim-op directly @@ -3136,7 +3763,7 @@ signature could be put. Same idea, except for instance declarations. For example: -instance (Eq a) => Eq (Foo a) where { ... usual stuff ... } +instance (Eq a) => Eq (Foo a) where { ... usual stuff ... } {-# SPECIALIZE instance Eq (Foo [(Int, Bar)] #-} @@ -3258,7 +3885,7 @@ If the type of the pattern variable is polymorphic, it must For example, here is the foldr/build rule: -"fold/build" forall k z (g::forall b. (a->b->b) -> b -> b) . +"fold/build" forall k z (g::forall b. (a->b->b) -> b -> b) . foldr k z (build g) = g k z @@ -3273,11 +3900,11 @@ The left hand side of a rule must consist of a top-level variable applied to arbitrary expressions. For example, this is not OK: -"wrong1" forall e1 e2. case True of { True -> e1; False -> e2 } = e1 +"wrong1" forall e1 e2. case True of { True -> e1; False -> e2 } = e1 "wrong2" forall f. f True = True -In "wrong1", the LHS is not an application; in "wrong1", the LHS has a pattern variable +In "wrong1", the LHS is not an application; in "wrong2", the LHS has a pattern variable in the head. @@ -3652,7 +4279,7 @@ Rewrite rules can be used to get the same effect as a feature present in earlier version of GHC: - {-# SPECIALIZE fromIntegral :: Int8 -> Int16 = int8ToInt16 #-} + {-# SPECIALIZE fromIntegral :: Int8 -> Int16 = int8ToInt16 #-} This told GHC to use int8ToInt16 instead of fromIntegral whenever @@ -3713,7 +4340,7 @@ If you add you get a more detailed listing. The defintion of (say) build in PrelBase.lhs looks llike this: - build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a] + build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a] {-# INLINE build #-} build g = g (:) [] @@ -3741,3 +4368,260 @@ program even if fusion doesn't happen. More rules in PrelList.lhs + + +Generic classes + + +The ideas behind this extension are described in detail in "Derivable type classes", +Ralf Hinze and Simon Peyton Jones, Haskell Workshop, Montreal Sept 2000, pp94-105. +An example will give the idea: + + + + import Generics + + class Bin a where + toBin :: a -> [Int] + fromBin :: [Int] -> (a, [Int]) + + toBin {| Unit |} Unit = [] + toBin {| a :+: b |} (Inl x) = 0 : toBin x + toBin {| a :+: b |} (Inr y) = 1 : toBin y + toBin {| a :*: b |} (x :*: y) = toBin x ++ toBin y + + fromBin {| Unit |} bs = (Unit, bs) + fromBin {| a :+: b |} (0:bs) = (Inl x, bs') where (x,bs') = fromBin bs + fromBin {| a :+: b |} (1:bs) = (Inr y, bs') where (y,bs') = fromBin bs + fromBin {| a :*: b |} bs = (x :*: y, bs'') where (x,bs' ) = fromBin bs + (y,bs'') = fromBin bs' + + +This class declaration explains how toBin and fromBin +work for arbitrary data types. They do so by giving cases for unit, product, and sum, +which are defined thus in the library module Generics: + + + data Unit = Unit + data a :+: b = Inl a | Inr b + data a :*: b = a :*: b + + +Now you can make a data type into an instance of Bin like this: + + instance (Bin a, Bin b) => Bin (a,b) + instance Bin a => Bin [a] + +That is, just leave off the "where" clasuse. Of course, you can put in the +where clause and over-ride whichever methods you please. + + + + Using generics + To use generics you need to + + + Use the flag. + + + Import the module Generics from the + lang package. This import brings into + scope the data types Unit, + :*:, and :+:. (You + don't need this import if you don't mention these types + explicitly; for example, if you are simply giving instance + declarations.) + + + + + Changes wrt the paper + +Note that the type constructors :+: and :*: +can be written infix (indeed, you can now use +any operator starting in a colon as an infix type constructor). Also note that +the type constructors are not exactly as in the paper (Unit instead of 1, etc). +Finally, note that the syntax of the type patterns in the class declaration +uses "{|" and "{|" brackets; curly braces +alone would ambiguous when they appear on right hand sides (an extension we +anticipate wanting). + + + + Terminology and restrictions + +Terminology. A "generic default method" in a class declaration +is one that is defined using type patterns as above. +A "polymorphic default method" is a default method defined as in Haskell 98. +A "generic class declaration" is a class declaration with at least one +generic default method. + + + +Restrictions: + + + +Alas, we do not yet implement the stuff about constructor names and +field labels. + + + + + +A generic class can have only one parameter; you can't have a generic +multi-parameter class. + + + + + +A default method must be defined entirely using type patterns, or entirely +without. So this is illegal: + + class Foo a where + op :: a -> (a, Bool) + op {| Unit |} Unit = (Unit, True) + op x = (x, False) + +However it is perfectly OK for some methods of a generic class to have +generic default methods and others to have polymorphic default methods. + + + + + +The type variable(s) in the type pattern for a generic method declaration +scope over the right hand side. So this is legal (note the use of the type variable ``p'' in a type signature on the right hand side: + + class Foo a where + op :: a -> Bool + op {| p :*: q |} (x :*: y) = op (x :: p) + ... + + + + + + +The type patterns in a generic default method must take one of the forms: + + a :+: b + a :*: b + Unit + +where "a" and "b" are type variables. Furthermore, all the type patterns for +a single type constructor (:*:, say) must be identical; they +must use the same type variables. So this is illegal: + + class Foo a where + op :: a -> Bool + op {| a :+: b |} (Inl x) = True + op {| p :+: q |} (Inr y) = False + +The type patterns must be identical, even in equations for different methods of the class. +So this too is illegal: + + class Foo a where + op1 :: a -> Bool + op {| a :*: b |} (Inl x) = True + + op2 :: a -> Bool + op {| p :*: q |} (Inr y) = False + +(The reason for this restriction is that we gather all the equations for a particular type consructor +into a single generic instance declaration.) + + + + + +A generic method declaration must give a case for each of the three type constructors. + + + + + +The type for a generic method can be built only from: + + Function arrows + Type variables + Tuples + Arbitrary types not involving type variables + +Here are some example type signatures for generic methods: + + op1 :: a -> Bool + op2 :: Bool -> (a,Bool) + op3 :: [Int] -> a -> a + op4 :: [a] -> Bool + +Here, op1, op2, op3 are OK, but op4 is rejected, because it has a type variable +inside a list. + + +This restriction is an implementation restriction: we just havn't got around to +implementing the necessary bidirectional maps over arbitrary type constructors. +It would be relatively easy to add specific type constructors, such as Maybe and list, +to the ones that are allowed. + + + + +In an instance declaration for a generic class, the idea is that the compiler +will fill in the methods for you, based on the generic templates. However it can only +do so if + + + + The instance type is simple (a type constructor applied to type variables, as in Haskell 98). + + + + + No constructor of the instance type has unboxed fields. + + + +(Of course, these things can only arise if you are already using GHC extensions.) +However, you can still give an instance declarations for types which break these rules, +provided you give explicit code to override any generic default methods. + + + + + + + +The option dumps incomprehensible stuff giving details of +what the compiler does with generic declarations. + + + + + Another example + +Just to finish with, here's another example I rather like: + + class Tag a where + nCons :: a -> Int + nCons {| Unit |} _ = 1 + nCons {| a :*: b |} _ = 1 + nCons {| a :+: b |} _ = nCons (bot::a) + nCons (bot::b) + + tag :: a -> Int + tag {| Unit |} _ = 1 + tag {| a :*: b |} _ = 1 + tag {| a :+: b |} (Inl x) = tag x + tag {| a :+: b |} (Inr y) = nCons (bot::a) + tag y + + + + + +