- Haskell-prime - Haskell.org

Re: TypeFamilies vs. etc - restrained instance overlap
by Anthony Clayden 26 Jun '11

26 Jun '11

Hi all THE TOPIC: [from the original post] >TypeFamilies vs. FunctionalDependencies & type-level recursion >David Mazieres dm-list-haskell-prime at scs.stanford.edu >Sun May 29 20:59:44 CEST 2011 >... GHC is on its way to accepting "a ~ b" as a constraint that >types a and b are equal. If there were a corresponding "a /~ b", ... >Of course, I have no idea how the compiler could know such constraints >are sufficient to avoid overlapping types. ... I think I do have an idea - see below. More important, how does type inference proceed without the dreaded *search* and potentially premature commit to an instance? I've also some ideas on that. (But this post will already be long enough, see separately for type inference.) THE WHAT: [SPJ responded to the OP] >1. As things stand in GHC you can do some things with functional dependencies that you can't do with type families. The archetypical example is type equality. > .... (example that needed overlapping instances, so rejected for type families) > But you can with fundeps > class Eq a b c | a b -> c > instance Eq k k True > instance Eq j k False As other posters pointed out, this form isn't quite right, and the form that works is more cumbersome and obscure. The thread then veered away into how fundeps could be improved, mostly resulting in the rules becoming even harder to understand (at least for me). SPJ mused: >2. In a hypothetical extension to type families, namely *closed* type families, you could support overlap: > closed type family Eq a b :: * where > type instance Eq k k = True > type instance Eq j k = False > The idea is that you give all the equations together; matching is top-to-bottom; and the type inference only picks an equation when all the earlier equations are guaranteed not to match. So there is no danger of making different choices in different parts of the program (which is what gives rise to unsoundness). THE HOW: I'd like to tackle this from another approach: what would it need to extend type families with a restrained form of instances? (Because, like SPJ "A big reason I like type families better is simply that I can understand them.") I prefer the following style: type family Eq a b :: * -- not closed type instance Eq k k = TTrue type instance Eq j k | j /~ k = TFalse -- effectively this makes the type family closed (Variations of this idea have appeared and reappeared at various times [at least since "A Theory of Overloading" Stuckey & Sulzmann, ICFP 2002, section 8.2, using disequalities in CHR's]. I'm keenly aware that the Haskell-prime process is only supposed to consider already-implemented extensions, so I'm trying to draw in as much pre-existing work as possible.) (The pattern-guard style of syntax seems natural, but I'll leave others to debate the lexicals ;-) Other examples: instance (Monad m) => MonadState s (StateT s m) where ... instance (Monad (t m), MonadTrans t, MonadState s m) => MonadState s (t m) | (t m) /~ (StateT s m) where .. type instance IsFunction (a -> b) = TTrue type instance IsFunction a | a /~ (_ -> _) = TFalse -- using _ as 'don't care' type var THE WHY: Advantages: A1: Each instance 'stands alone' (so they don't have to be defined in the same place). This approach avoids one difficulty SPJ points out about sequence of equations: >3. Closed type families are not implemented yet. The only tricky point I see would be how to express in System FC the proof that "earlier equations don't match". Moreover, to support abstraction one might well want David's /~ predicate, so that you could say > f :: forall a b. (a /~ b) => ..blah.. > This f can be applied to any types a,b provided they don't match. I'm frankly unsure about all the consequences here. A2: The instances don't overlap, although the instance heads do. So ... A3: Introducing a new instance (perhaps imported from an ostensibly unrelated module) does not 'silently' change behaviour. (One of the long-standing complaints about overlaps.) That is: if the new instance overlaps, we get a compile fail. A4: And we can validate instances for overlap 'there and then' as the compiler encounters each instance. That is, how Hugs behaves, whereas GHC currently defers validating overlap until it encounters a use-site where it can't figure out which instance to choose. GHC's behaviour was a source of confusion even in the thread that followed SPJ's post, because instances appeared to compile clean, but in fact couldn't be used. THE HOW (part 1 - validating instances): Instance validation uses mechanisms already in GHC for the limited forms of overlap it supports in Type Families: V0: The terms each side of the /~ must be of the same Kind (same rule as for type equalities). V1: Upon encountering each instance, compare it one by one with all other instances in scope. V2: If the heads don't overlap, we're OK. V3: If they do overlap, form the mgu for the overlap. V4: Substitute the mgu into the RHS of the instances, if they're confluent we're OK. (Up to this point is existing GHC behaviour.) V5: If they do overlap but aren't confluent, and neither has a disequality restraint, reject. V6: If <none of the above>, substitute the mgu into the disequality(s) for the instance(s). At least one must lead to a contradiction. Example from GHC's documentation for type families: > type instance G (a, Int) = [a] > type instance G (Char, b) = [b] -- ILLEGAL overlap on G (Char, Int) > type instance G (Bool, b) | b /~ Int = [b] > -- legal, because substituting the mgu for the overlap yields > -- G (Bool, Int) | Int /~ Int -- at validation step V6 THE HOW (part 2 - type inference): see the next episode. ... Ends AntC

1 0

TypeFamilies vs. FunctionalDependencies & type-level recursion
by oleg＠okmij.org 17 Jun '11

17 Jun '11

Dan Doel wrote: > class C a b | a -> b where > foo :: a -> b > foo = error "Yo dawg." > > instance C a b where The instance 'C a b' blatantly violates functional dependency and should not have been accepted. The fact that it was is a known bug in GHC. The bug keeps getting mentioned on Haskell mailing lists about every year. Alas, it is still not fixed. Here is one of the earlier messages about it: http://www.haskell.org/pipermail/haskell-cafe/2007-March/023916.html HList does NOT depend on that invalid behavior. The bug is relatively recent (introduced around 2006); HList worked in 2004.

5 10

Re: TypeFamilies vs. FunctionalDependencies & type-level recursion
by Dan Doel 16 Jun '11

16 Jun '11

Sorry about the double send, David. I forgot to switch to reply-all in the gmail interface. On Tue, Jun 14, 2011 at 11:49 AM, <dm-list-haskell-prime(a)scs.stanford.edu> wrote: > You absolutely still can use FunctionalDependencies to determine type > equality in GHC 7. For example, I just verified the code below with > GHC 7.02: > > *Main> typeEq True False > HTrue > *Main> typeEq (1 :: Int) (2 :: Int) > HTrue > *Main> typeEq (1 :: Int) False > HFalse > > As always, you have to make sure one of the overlapping instances is > more specific than the other, which you can do by substituting a > parameter c for HFalse in the false case and fixing c to HFalse using > another class like TypeCast in the context. (As contexts play no role > in instance selection, they don't make the instance any more > specific.) > > While I don't have convenient access to GHC 6 right this second, I'm > pretty sure there has been no change for a while, as the HList paper > discussed this topic in 2004. Okay. I don't really write a lot of code like this, so maybe I missed the quirks. In that case, HList has been relying on broken behavior of fundeps for 7 years. :) Because the instance: instance TypeEq a b c violates the functional dependency, by declaring: instance TypeEq Int Int Int instance TypeEq Int Int Char instance TypeEq Int Int Double ... instance TypeEq Int Char Int instance TypeEq Int Char Char ... and adding the constraint doesn't actually affect which instances are being declared, it just adds a constraint requirement for when any of the instances are used. It appears I was wrong, though. GHC doesn't actually fix the instance for such fundeps, and the following compiles and runs fine: class C a b | a -> b where foo :: a -> b foo = error "Yo dawg." instance C a b where bar :: Int bar = foo "x" baz :: Char baz = foo "x" so we're using an instance C String Int and an instance C String Char despite the fact that there's a functional dependency from the first argument to the second. -- Dan

5 12

New libraries process
by Simon Peyton-Jones 26 May '11

26 May '11

Friends Thanks to those who responded to the message below, about improving the process for developing the core Haskell libraries. http://www.haskell.org/haskellwiki/Library_submissions/NewDraft Feedback has been broadly positive, with constructive suggestions that we've incorporated in the text. I suggest that we leave another week for debate and refinement, and (unless there are some substantial new points) adopt the new process from 9 June. I hope that's agreeable. (We don't have a process for modifying the process :-) Simon | I think there is general agreement that | * The library submission process is too daunting, especially because you have to | come up with a complete implementation of a proposal before you even know | whether it's going to fly. | * The process gets stuck because achieving universal consensus is too difficult | * The maintainer "libraries(a)haskell.org" means that no individual feels responsible | for making a decision on a proposal. | | What we need is something to put in its place. Simon and I have been cooking up a | proposal. Here it is: | | http://www.haskell.org/haskellwiki/Library_submissions/NewDraft | | It is aimed just at libraries whose maintainer is listed as libraries(a)haskell.org. | (The thousands of other libraries with named maintainers can obviously do whatever | their maintainer wants, although perhaps this new draft may be useful for them too.) | | It's a draft. What do you think of it? Do you think it would be better than the | status quo? Can you suggest any improvements? | | ALSO: does anyone (or two or three people) want to volunteer to act as maintainer for | any of the "Volunteer needed" packages? Johan, I was thinking you might serve for | 'containers', perhaps in harness with someone else since it is such a crucial | package. | | | Simon | | _______________________________________________ | Cvs-ghc mailing list | Cvs-ghc(a)haskell.org | http://www.haskell.org/mailman/listinfo/cvs-ghc

4 3

Proposal: Make gcd total
by Daniel Fischer 26 May '11

26 May '11

I would like to propose the elimination of the special error case gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined" to replace it with gcd 0 0 = 0 (which would be an automatic consequence of removing the above line). Rationale: 1. It makes gcd a total function. 2. It makes gcd associative. 3. It makes folding gcd over a list safe. 4. It conforms to common mathematical practice: In a commutative ring, a greatest common divisor of two elements a, b is a common divisor g of a and b such that every common divisor d of a and b also divides g (if R is a commutative ring, a \in R, d \in R is a divisor of a iff there exists c \in R with a = d*c [leaving out noncommutative rings for simplicity]). Since every ring element divides 0, the above definition entails gcd 0 0 = 0. Further, in a principal ideal ring, the greatest common divisors of two elements a and b are the generators of the ideal (a,b), again that characterisation of greatest common divisors says gcd 0 0 = 0: (0,0) = {0} = (0). Pros: see above. Cons: ? I'm not aware of any, the change shouldn't break existing code, since that would have to check for the special case anyway. Daniel

7 8

TypeSynonymInstances should be enabled by default
by Andrew Pennebaker 21 Apr '11

21 Apr '11

Source: https://github.com/mcandre/genetics With {-# LANGUAGE TypeSynonymInstances #-} , my genetic algorithm code compiles and runs perfectly. $ make $ ./helloga ... hellowobld helloworyd helloporld hellyworld helloworrd hellowofld hellpworld Best candidate: helloworld Without it, Haskell refuses to declare an instance on Strings. $ make ghc --make -O2 -fforce-recomp helloga.hs [1 of 2] Compiling Genetics ( Genetics.hs, Genetics.o ) [2 of 2] Compiling Main ( helloga.hs, helloga.o ) helloga.hs:27:10: Illegal instance declaration for `Gene String' (All instance types must be of the form (T t1 ... tn) where T is not a synonym. Use -XTypeSynonymInstances if you want to disable this.) In the instance declaration for `Gene String' make: *** [all] Error 1 The fix is easy to discover and apply, but this is my first typeclass, nothing complicated. As a newbie I prefer that it "just works" without my having to use the special compile flag. Cheers, Andrew Pennebaker www.yellosoft.us

2 1

Proposal: Define UTF-8 to be the encoding of Haskell source files
by Roel van Dijk 18 Apr '11

18 Apr '11

Per the Haskell Prime process I would like to make an official proposal [1]. * Proposal The Haskell 2010 language specification states that: "Haskell uses the Unicode character set" [2]. It does not state what encoding should be used. This means, strictly speaking, it is not possible to reliably exchange Haskell source files on the byte level. I propose to make UTF-8 the only allowed encoding for Haskell source files. Implementations must discard an initial Byte Order Mark (BOM) if present [3]. * Pros - Ensures that Haskell source can be reliably exchanged on the byte level. - Disallows implicit ISO-8859-* encodings in source code, ensuring portability. - Little or no implementation burden for compiler writers. * Cons - Existing code relying on a non-UTF8, locale-/implementation-specific encoding will need conversion. (Only relevant for Hugs-only code). * Implementation status ** GHC "GHC assumes that source files are ASCII or UTF-8 only, other encodings are not recognised. However, invalid UTF-8 sequences will be ignored in comments, so it is possible to use other encodings such as Latin-1, as long as the non-comment source code is ASCII only." [4] >From this I deduce that all current code accepted by GHC is compatible with UTF-8. No working code will be broken. ** JHC "JHC allows unrestricted use of the Unicode character set in Haskell source, treating input as UTF-8." [5] ** Hugs Hugs treats input as being in the encoding specified by the current locale, but permits Unicode only in comments and character and string literals. [6] * Related proposal There is one, 5 year old, proposal that is related: "SourceEncodingDetection" [5]. There it is proposed to detect the encoding using an algorithm which can distinguish between UTF-8, UTF-16 and (not always) UTF-32. It can also detect the endianness of the document, if applicable. I think choosing just UTF-8 is a better choice than a detection algorithm. It places less burden on implementation writers and is even more portable. * Next step Discussion! There was already some discussion on the haskell-cafe mailing list [7]. Attached is a patch for the Haskell Report which adds a note stating that source encodings must be UTF-8. Regards, Roel van Dijk [1] - http://hackage.haskell.org/trac/haskell-prime/wiki/Process [2] - http://www.haskell.org/onlinereport/haskell2010/haskellch2.html#x7-150002.1 [3] - http://www.unicode.org/faq/utf_bom.html#bom5 [4] - http://www.haskell.org/ghc/docs/7.0-latest/html/users_guide/separate-compil… [5] - http://hackage.haskell.org/trac/haskell-prime/wiki/SourceEncodingDetection [6] - http://cvs.haskell.org/Hugs/pages/users_guide/locale.html [7] - http://article.gmane.org/gmane.comp.lang.haskell.cafe/87815

5 10

minor bug in Haskell 2010 standard
by Peter Klausler 14 Apr '11

14 Apr '11

A brief correction to a problem that may have already been noticed and rectified: on page 84 (being page 104 of the PDF), in the last sentence of section 6.4.3, it reads: "0**y is 1 if y is 1, and 0 otherwise." Surely this should read "0**y is 1 if y is 0, and 0 otherwise", yes? Best regards, Peter Klausler at Google in Madison

1 0

Announce: ~Haskell 2011
by Malcolm Wallace 14 Apr '11

14 Apr '11

The Haskell Language committee has had a quiet year. Following the announcement of Haskell 2010 in Nov 2009 [1], and the publication of the 2010 Report in July 2010 [2], we found a distinct lack of complete new proposals to decide upon. As a result, the committee has made the following decisions: (a) we wish to accept the NoDatatypeContexts proposal http://hackage.haskell.org/trac/haskell-prime/wiki/NoDatatypeContexts (b) this delta will be applied to the 2010 Report to form a new baseline; (c) we will _not_ issue a new language standard called 2011; (d) we intend to issue a new language standard in 2012; (e) the committee will continue for another year without new nominations. However, let me make it clear that the apparent lull in committee activity does not mean there are no active proposals being made. On the contrary, proposals for language features (and removals) are made by the community at large (that's you) - the committee's main role is not to make proposals, but to decide which to accept. And there have in fact been a large number of proposals, but very few have made it all the way to the stage of producing a "language report delta" that could be accepted (or modified) by the committee. So, I wish to declare "open season" on proposals for the 2012 standard. If there is a language feature you care about, please do take an hour or two to review the details on our wiki [3], search for older discussions on the mailing lists, and draft the Report changes you think would be necessary. I'm looking forward to a more active and exciting collection of potential language changes for 2012, but it will only happen if you get involved. Regards, Malcolm (Haskell 2011 committee chair) [1] http://www.haskell.org/pipermail/haskell/2009-November/021750.html [2] http://www.haskell.org/pipermail/haskell/2010-July/022189.html [3] http://hackage.haskell.org/trac/haskell-prime/

4 5

[Colin Paul Adams] Re: Proposal: Define UTF-8 to be the encoding of Haskell source files
by Colin Paul Adams 07 Apr '11

07 Apr '11

I forgot to CC the list: >>>>> "Roel" == Roel van Dijk <vandijk.roel(a)gmail.com> writes: Roel> I propose to make UTF-8 the only allowed encoding for Haskell Roel> source files. Implementations must discard an initial Byte Roel> Order Mark (BOM) if present [3]. Roel> * Pros - Ensures that Haskell source can be reliably exchanged Roel> on the byte level. - Disallows implicit ISO-8859-* encodings Roel> in source code, ensuring portability. - Little or no Roel> implementation burden for compiler writers. Having thought this over a bit more, I don't think it's a good idea. Allowed? Allowed for what? What does it achieve? Nothing, as far as I can see. Authors will still be able to write their Haskell code in any encoding they like. And any compiler can have a front-end script with an option to specify the encoding used by source files, which simply uses iconv on the fly to translate. I think the real place to mandate UTF-8 would be for Hackage. That's where it matters (an alternative design would be to add an encoding field in the .cabal file, but I don't think this has much merit). -- Colin Adams Preston Lancashire () ascii ribbon campaign - against html e-mail /\ www.asciiribbon.org - against proprietary attachments

5 13