March 2006 - Haskell-prime

RE: Infix expressions
by Simon Peyton-Jones 17 Mar '06

17 Mar '06

| The second header line shows categories, whereas the links in the grey | boxes are to articles. The "idioms" category collects together articles | that are about idioms. | | We could have an "idioms" or "programming techniques" article as well, | of course. It only needs to be written. Interesting. I thought there would be a rationale! But my point is this: I didn't even know that there is a concept of a "category" on the Haskell web site. And I visit it regularly. An innocent visitor certainly won't. Now I know that there is such a concept, but I have no idea what it might mean, or how I might use it. My suggestion: by all means have categories, whatever they are. But can we arrange the home page of Haskell.org so that a new and ignorant visitor can simply look on the visible page (without prior knowledge) and know where to go? And can there be some information readily accessible that explains what categories are, and how to use them and add to them? Sorry to be stupid about this. Simon

2 1

RE: Infix expressions
by Simon Peyton-Jones 17 Mar '06

17 Mar '06

| > Incidentally, I looked on the Haskell home page for links to programming | > idioms and advice, but came up empty. The obvious place to look was | > under "Using Haskell", but I didn't find anything. Was I being stupid? | > Haskell.org is the obvious place to look for advice about programming in | > Haskell. | | There should be a link to "Idioms" above the grey boxes? Oh yes so there is! But what is the rationale for what goes in those two header lines, and what goes in the grey box lists? Why would "idioms" be in the first place but not the second, and FAQ in the second but not the first? Perhaps we could have just the grey boxes? (Incidentally "idioms" is too short to tell me "follow me". Something like "Programming techniques" would be more suggestive.) Simon

2 1

RE: relaxed instance rules spec (was: the MPTC Dilemma (please solve))
by Simon Peyton-Jones 16 Mar '06

16 Mar '06

Claus, I urge you to read our paper "Understanding functional dependencies via Constraint Handling Rules", which you can find here http://research.microsoft.com/%7Esimonpj/papers/fd%2Dchr/. It will tell you more than you want to know about why relaxing apparently-conservative rules is entirely non-trivial. It's one of those areas in which it is easy to suggest a plausible-sounding alternative, but much harder to either prove or disprove whether the alternative a sound one. The paper describes rules we are reasonably sure of. It would be great to relax those rules. But you do need to have a proof that the relaxation preserves the properties we want. Go right ahead! The paper provides a good framework for such work, I think. Simon | -----Original Message----- | From: Claus Reinke [mailto:claus.reinke@talk21.com] | Sent: 28 February 2006 19:54 | To: Simon Peyton-Jones; haskell-prime(a)haskell.org | Subject: relaxed instance rules spec (was: the MPTC Dilemma (please solve)) | | >The specification is here: | >http://www.haskell.org/ghc/dist/current/docs/users_guide/type-extension s.html#instance-decls | | two questions/suggestions about this: | | 1. there are other termination criteria one migh think of, though | many will be out because they are not easy to specify. but here | is an annoyingly simple example that doesn't fit the current rules | even though it is clearly terminating (it's not even recursive): | | class Fail all -- no instances! | | class TypeNotEq a b | instance Fail a => TypeNotEq a a | instance TypeNotEq a b | | class Test a b where test :: a -> b -> Bool | instance TypeNotEq a b => Test a b where test _ _ = False | instance Test a a where test _ _ = True | | main = print $ (test True 'c', test True False) | | never mind the overlap, the point here is that we redirect from | Test a b to TypeNotEq a b, and ghc informs us that the | "Constraint is no smaller than the instance head". | | it is true that the parameters don't get smaller (same number, | same number of constructors, etc.), but they are passed to a | "smaller" predicate (in terms of call-graph reachability: there | are fewer predicates reachable from TypeNotEq than from | Test - in particular, Test is not reachable from TypeNotEq). | | this is a non-local criterion, but a fairly simple one. and it seems | very strange to invoke "undecidable instances" for this example | (or is there anything undecidable about it?). | | 2. the coverage condition only refers to the instance head. this | excludes programs such as good old record selection (which | should terminate because it recurses over finite types, and is | confluent -in fact deterministic- because of best-fit overlap | resolution): | | -- | field selection | infixl #? | | class Select label val rec | label rec -> val where | (#?) :: rec -> label -> val | | instance Select label val ((label,val),r) where | ((_,val),_) #? label = val | | instance Select label val r => Select label val (l,r) where | (_,r) #? label = r #? label | | now, it is true that in the second instance declaration, "val" is | not covered in {label,(l,r)}. however, it is covered in the recursive | call, subject to the very same FD, if that recursive call complies | with the (recursive) coverage criterion. in fact, for this particular | task, that is the only place where it could be covered. | | would it be terribly difficult to take such indirect coverage (via | the instance constraints) into account? there'd be no search | involved (the usual argument against looking at the constraints), | and it seems strange to exclude such straightforward "consume | a type" recursions, doesn't it? | | cheers, | claus

8 20

RE: Infix expressions
by Simon Peyton-Jones 16 Mar '06

16 Mar '06

I often wish that cool tricks like this could be collected on the Haskell web site. Now that it's a wiki, anyone could do that. Simon | -----Original Message----- | From: haskell-prime-bounces(a)haskell.org [mailto:haskell-prime-bounces@haskell.org] On Behalf Of | oleg(a)pobox.com | Sent: 15 March 2006 04:34 | To: doaitse(a)cs.uu.nl; haskell-prime(a)haskell.org | Subject: Infix expressions | | | Doaitse Swierstra wrote: | > In Haskell we write `f` in order to infixify the identifier f. In ABC | > the stuff between backquotes is not limited to an identifier, but any | > expression may occur there. This would allow one to write e.g. | > | > xs `zipWith (+)` ys | | Chung-chieh Shan and Dylan Thurston showed the Haskell98 solution for | exactly the same example, in their article `Infix expressions', | back in 2002: | http://www.haskell.org/pipermail/haskell-cafe/2002-July/003215.html | | For ease of reference, here's their elegant solution: | | > infixr 0 -:, :- | > data Infix f y = f :- y | > x -:f:- y = x `f` y | > | > main = print $ [1,2,3] -: zipWith (+) :- [4,5,6] | | | For completeness, here's the `dual': | | > infixr 5 -! | > (-!) = flip ($) | > infixr 5 !- | > (!-) = ($) | > | > add2 x y = x + y | > add3 x y z = x + y + z | > add4 x y z u = x + y + z + u | > | > testa1 = 1 -! add2 !- 3 + 4 | > testa2 = 1 -! add3 1 !- 3 + 4 | > testa3 = 1 - 2 -! add4 1 5 !- 3 * 4 | | All code is Haskell98. | _______________________________________________ | Haskell-prime mailing list | Haskell-prime(a)haskell.org | http://haskell.org/mailman/listinfo/haskell-prime

5 5

RE: Infix expressions
by Simon Peyton-Jones 16 Mar '06

16 Mar '06

If it is sufficiently non-obvious to require this thread, perhaps it'd be worth adding the relevant guidance can be added to the idioms page itself? Incidentally, I looked on the Haskell home page for links to programming idioms and advice, but came up empty. The obvious place to look was under "Using Haskell", but I didn't find anything. Was I being stupid? Haskell.org is the obvious place to look for advice about programming in Haskell. S | -----Original Message----- | From: haskell-prime-bounces(a)haskell.org [mailto:haskell-prime-bounces@haskell.org] On Behalf Of | Donald Bruce Stewart | Sent: 15 March 2006 23:49 | To: Malcolm Wallace | Cc: haskell-prime(a)haskell.org | Subject: Re: Infix expressions | | Malcolm.Wallace: | > dons(a)cse.unsw.edu.au (Donald Bruce Stewart) writes: | > | > > Yes, this is _exactly_ the kind of thing to add to the Idioms | > > page of the wiki, here: | > > http://www.haskell.org/haskellwiki/Category:Idioms | > > So if anyone knows of an interesting Haskell trick, and wants to write | > > about it, add a page! | > | > It is not entirely clear _how_ to add a page hanging off Idioms. When | > you click on "Edit this page", the text edit box contains only a single | > word: [[Category:Haskell]], and no visible record of the existing text. | > Rather confusing, and there is no link to "add a new page" or similar. | | To add your page to a particular category, have [[Category:Idioms]] (for | example) appear at the bottom of the page -- it then appears automagically. | | You add a new page just by typing that page's url into your browser. | You'll get a blank page suggesting that you create it (once you log on). | | -- Don | | _______________________________________________ | Haskell-prime mailing list | Haskell-prime(a)haskell.org | http://haskell.org/mailman/listinfo/haskell-prime

2 1

only explicit universal quantification
by Wolfgang Jeltsch 16 Mar '06

16 Mar '06

Hello, what about dropping implicit universal quantification of type variables from the language, meaning that every universal quantification has to be made explicit? One advantage of this would be that spelling mistakes in type variables would be detected by the compiler more often since every type variable would need to be “declared” by a forall (or exists). In addition one could think of different semantics for unbound type variables. Such a variable could refer to a quantification at a higher level which would solve the problem of sometimes not being able to give type declarations for let/where declarations. For example, in the following example, the type variable e in the where clause would refer to the same type as the type variable e in the type declaration of the function example: example :: forall e. Enum e => e -> e example = helper where helper :: e -> e helper = succ I know, these would be rather drastic changes but they seem sensible to me. What do others think? Best wishes, Wolfgang

3 2

RE: Infix expressions
by Simon Marlow 15 Mar '06

15 Mar '06

On 15 March 2006 13:41, Malcolm Wallace wrote: > dons(a)cse.unsw.edu.au (Donald Bruce Stewart) writes: > >> Yes, this is _exactly_ the kind of thing to add to the Idioms >> page of the wiki, here: >> http://www.haskell.org/haskellwiki/Category:Idioms >> So if anyone knows of an interesting Haskell trick, and wants to >> write about it, add a page! > > It is not entirely clear _how_ to add a page hanging off Idioms. When > you click on "Edit this page", the text edit box contains only a > single word: [[Category:Haskell]], and no visible record of the > existing text. Rather confusing, and there is no link to "add a new > page" or similar. Good point. I don't know either, but I just thought I'd point out that "Hitchiker's Guide to Haskell" is in a section called "P", for some unknown reason. Cheers, Simon

1 0

Infix expressions
by oleg＠pobox.com 15 Mar '06

15 Mar '06

Doaitse Swierstra wrote: > In Haskell we write `f` in order to infixify the identifier f. In ABC > the stuff between backquotes is not limited to an identifier, but any > expression may occur there. This would allow one to write e.g. > > xs `zipWith (+)` ys Chung-chieh Shan and Dylan Thurston showed the Haskell98 solution for exactly the same example, in their article `Infix expressions', back in 2002: http://www.haskell.org/pipermail/haskell-cafe/2002-July/003215.html For ease of reference, here's their elegant solution: > infixr 0 -:, :- > data Infix f y = f :- y > x -:f:- y = x `f` y > > main = print $ [1,2,3] -: zipWith (+) :- [4,5,6] For completeness, here's the `dual': > infixr 5 -! > (-!) = flip ($) > infixr 5 !- > (!-) = ($) > > add2 x y = x + y > add3 x y z = x + y + z > add4 x y z u = x + y + z + u > > testa1 = 1 -! add2 !- 3 + 4 > testa2 = 1 -! add3 1 !- 3 + 4 > testa3 = 1 - 2 -! add4 1 5 !- 3 * 4 All code is Haskell98.

1 0

RE: overlapping instances and constraints
by Simon Peyton-Jones 11 Mar '06

11 Mar '06

Overlapping instances are undoubtedly useful, but they raise lots of interesting questions. Such as - A program that type checks can have its meaning changed by adding an instance declaration - Similarly adding "import M()" can change the meaning of a program (by changing which instances are visible - Haskell would need to be a lot more specific about exactly where context reduction takes place. Consider f xs x = xs == [x] Do we infer the type (Eq a) => [a] -> a -> Bool? Thereby committing to a particular choice of instance? Or do we (as GHC does) infer the type (Eq [a]) => [a] -> a -> Bool, so that if f is applied at (say) type Char, then an instance Eq [Char] instance would apply. GHC is careful to do the latter. - When exactly is overlap permitted? Is this ok? instance C a Int instance C Bool b Previously GHC rejected this, on the grounds that it could be ambiguous when you came across (C Bool Int). But not GHC accepts it, on the grounds that (C Bool Char) is quite unambiguous. [Actually this last point is relevant for MPTCs even if overlap isn't allowed.] Concerning using the instance context, yes, it's attractive, but it involves *search* which the current mechanism does not. Presumably you have in mind that the type system should "commit" only when there is only one remaining instance declaration that can fit. You need to be very careful not to prune off search branches prematurely, because in a traditional HM type checker you don't know what all the type are completely. And you need to take functional dependencies into account during the search (but not irrevocably). I have not implemented this in GHC. I don't know anyone who has. I don't even know anyone who has specified it. All good stuff to debate. I'd be happy to see the traffic on MPTCs reach half the level that syntax debates do! In general, I think that type-system proposals are much easier to evaluate when accompanied with formal type rules. It's not just a macho thing -- it really helps in debugging the dark corners. Simon | -----Original Message----- | From: haskell-prime-bounces(a)haskell.org [mailto:haskell-prime-bounces@haskell.org] On Behalf Of | Claus Reinke | Sent: 26 February 2006 16:28 | To: haskell-prime(a)haskell.org | Subject: overlapping instances and constraints | | | the point about overlapping instances is that they shouldn't, | so we are looking for ways to resolve what looks like overlaps | unambiguously, so that there are no overlapping instances left. | | we don't want overlapping instances in the language definition, | but we do want more expressive means of defining non- | overlapping instances. | | 1. resolving overlaps in favour of the most specific declaration | does so, so why is that approach slated as "adopt: probably no"? | | http://hackage.haskell.org/trac/haskell-prime/ticket/54 | | 2. FDs can help to make types in instance declarations more | specific, thus avoiding some overlaps or at least helping the | "best-match" to resolve overlaps. defaults resolve some of | the simplest overlaps (which instance of Num did you mean?), | but not others, because their overloading is not expressed in | terms of classes (which empty list did you mean?). | | 3. in this context, could someone please remind me what exactly | is the reason that class constraints in instance declarations are | ignored when deciding whether two instances overlap? | | we have two worlds to consider, the unconstrained world of | semi-decidable type class programming, and the restricted | world which guarantees termination of type class inference. | | in the first world, it seems there is no reason not to look at | the constraints, because there are no termination guarantees | anyway. and in the second world, it seems there is no reason | not to look at the constraints, because we know that doing | so will terminate nicely, thank you. | | so why are some instance declarations still rejected as | overlapping even if their constraints clearly say they don't? | | cheers, | claus | | _______________________________________________ | Haskell-prime mailing list | Haskell-prime(a)haskell.org | http://haskell.org/mailman/listinfo/haskell-prime

9 20

darcs patch: add Data.Set.notMember and Data.Map.notMember / generalized infix notation use case
by Jean-Philippe Bernardy 11 Mar '06

11 Mar '06

Patch applied. Still, In time, I suppose the somewhat ugly not (element `member` set) sould be addressed by a mixture of generalized infix notation and the definition of such an operator: f /. g = \x y -> f (g x y) allowing element `not/.member` set Cheers, JP. On 3/11/06, Cale Gibbard <cgibbard(a)gmail.com> wrote: > > I don't like notElem either > > > > > * quite useful for cleaning up guards: > > > > > > f x | not (x `Set.member` map) && foo = ... > > > is hard to read. > > > > You may swap quards (or the "then" and "else" branches of "if"), or > > avoid the infix notation (which is horrible in this case anyway). > > > Although I'd normally agree with negated versions of things being > somewhat redundant, the infix version here is rather important, since > one often wants the code to look the same way as the mathematics. The > symbols \in and \not\in are both usually written infix, and that's not > going to change soon. Putting the membership operation in between is > nice, because we read the guard here as "If x is a member of xs > then..." rather than "If member x xs then..." anyway. Perhaps if the > proposal to allow somewhat more general expressions as infix operators > goes through (which I'm actually ambivalent about), I'd feel different > about this case. > > If you want to reduce redundancy, let's unify the 3 separate ways to > say 'map'. :) > > - Cale > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://www.haskell.org/mailman/listinfo/libraries >

1 0