[Haskell] MR details (was: Implicit type of numeric constants)
Hello, I don't take my advice to go to haskell-cafe :-) The discussion continued outside the mailing list, and now I have two questions myself: 1. Why do the rules of the monomorphism restriction explicitly mention *simple* pattern bindings? Where is the difference, especially as there is a translation to simple pattern bindings? Why should p | "a"=="b" = 2 | otherwise = 3 be treated different than p = if "a"=="b" then 2 else 3 2. The gentle introduction says in section 12.3: An identifier is monomorphic if is either not overloaded, or is overloaded but is used in at most one specific overloading and is not exported. How does that relate to the report? Maybe I have to withdraw what I said about haskell being well defined. All the best Christian Sievers ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Re: Implicit type of numeric constants
Robert Stroud wrote: > Thanks for your explanation - this is beginning to make more sense to > me. However, I'm not finding it easy to follow the Haskell language > manual, and understand how the rules apply, so please could you > confirm that the following reasoning is correct... > > Firstly, am I right in thinking that "k = 2" is a simple pattern > binding? Yes. > The syntax for a top-level declaration doesn't seem to > include the possibility of declaring a variable, and there doesn't > seem to be an explicit syntax for pattern. I couldn't find it easily either, but eventually I found it: section 3.17.1. The rest of your reasoning seems right, too. > OK - so far so good I hope. What I don't understand though is why the > monomorphism restriction is necessary for the case of a simple > constant declaration. The language manual gives two motivations, > neither of which seems to apply. The first reason is to do with > preventing computations being unexpectedly repeated, but there is no > computation involved here, since k is defined as a constant. The > second reason is to prevent ambiguity, but the example involves a non- > simple binding. So why is it necessary to give a named constant a > monomorphic type, when the unnamed constant has a polymorphic type? I think it would make the language irregular, and you would probably also want slightly more complex constants, and then where to draw the line? What would you think of a = 2 b = a c = -a d = a+1 e = 2^16 f = 1/7 g = product [1..10] What maybe interesting to you is that when I read the claim that the k in the let clause was polymorphic, I didn't think "no, it isn't", but rather "oh, is it?", and then tried it. And the first result of trying to explain that what getting more confused. I think you don't have to know exactly all the things I described in my yesterday's mail - I didn't know them yesterday morning either. All you have to know is that when you get such errors, you can fix them with an explicit type signature. But if you wonder what a strange language that is, continue to ask, it's a bit complex, but well defined and quite regular. (I think the haskell-cafe mailing list might be more apprpriate.) All the best Christian ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Re: Implicit type of numeric constants
Robert Stroud wrote: > Thanks - that's a helpful example. But why is the following not > equivalent to the untyped "k = 2" case: > > let f :: Int -> Int -> Int ; f x y = x * y in (f 2 2, 1/2) > > Does the type of 2 effectively get decided twice, once as an Int, and > once as a Fractional, and is this the "repeated computation" that the > monomorphism restriction is intended to prevent? 2 has the fixed polymorphic type Num a => a, which gets resolved at each occurance. This resolving happens at compile time, so there is no repeated computation at run time involved. However, you need to somehow get both a 2::Int and a 2::Double which may be seen as a trivial case of this repeated computation. > Otherwise, I would have expected that it wouldn't make any difference > whether I used a named 2 or an anonymous 2, but imposing the > monomorphism restriction on the named 2 seems to break referential > transparency. Only if you expect referential transparency for implicitly typed values. All you have to do is say k :: Num a => a k = 2 and everything is fine. Bye Christian Sievers ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Re: Implicit type of numeric constants
Robert Stroud wrote: > However, I still think there's a bit of an inconsistency here. I > understand that if k had the type "Num a => a", then the expression > "show k" would be ambiguous, but unless I write that expression, > there's no ambiguity... Actually, you can give k that type, and thanks to defaulting you can then still use show k. > So it seems to me that the type checker is being a bit too eager to > prevent something that hasn't happened yet. Here it is the monomorphism restriction (Haskell report section 4.5.5) that enforces defaulting. > In contrast, in the case where I write "let k = 2 ...", the type > checker seems happy to resolve the polymorphic type within the > context of the let expression, and does what I expect. I hope my last mail explained this: defaulting for monomorphic types happens quite late. > So is the problem that the context is effectively unbounded when I > load the definition from a file, and hence the type checker has to be > very conservative about preventing the ambiguity? A file is (essentially) a module. This defaulting happens "when type inference for an entire module is complete" (rule 2 of the above mentioned section), because we don't want types to depend on arbitrary other modules - think of seperate compilation. > I'm afraid I'm also still not clear about why 2 doesn't default to > 2::Integer in the same way that k defaults to k::Integer, It does, that's why show 2 works. Hope that helps Christian Sievers ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Re: Implicit type of numeric constants
Arie Peterson wrote: > > However, if I type an apparently equivalent let expression into Hugs > > directly, then I get the value 4 as expected > > > > let k = 2 ; f :: Int -> Int -> Int ; f x y = x * y in f k k > > > > Why is there a difference in behaviour? > > Here, there is no defaulting, 'k' has the polymorphic type you expect, and > the use of 'k' as an argument to the monomorphically typed 'f' chooses the > right instance of 'Num'. Well, there is no defaulting at the stage of type checking when k is given type Num a => a, the monomorphism restriction applies and this type is not generalised to forall a . (Num a) => a, then the use of k forces the type variable a to be Int, and then there is no longer any need for defaulting. So k gets a monotype which is determined by its usage, you cannot do e.g. let k = 2 ; f :: Int -> Int -> Int ; f x y = x * y in (f k k, 1/k) whereas let k :: Num a => a; k = 2; ... is possible. Defaulting in Haskell 98 happens so late that this file k = 2 f :: Int -> Int -> Int f x y = x * y r = f k k is okay. Alas, Hugs does not comply in this respect, see http://cvs.haskell.org/Hugs/pages/users_guide/haskell98.html at the end of 5.1.3. All the best, Christian Sievers ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] GHC / Hugs Disagree on Constraints
Dominic Steinitz asked: > Is asTypeOf really Haskell 98? Yes, it is in the Prelude. And there is no special magic, it is Haskell-98-implementable, see http://haskell.org/onlinereport/standard-prelude.html#$vasTypeOf Bye Christian Sievers ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: In search of: [a->b] -> a -> [b]
Derek Elkins wrote: > > flist :: [a->b] -> a -> [b] > > flist fs a = map (flip ($) a) fs > or much nicer (IMO) > flist fs a = map ($ a) fs This is a case where I'd prefer a list comprehension: flist fs a = [ f a | f <- fs ] (and this could be a monad comprehension, if Haskell still had them...) > the generalized solution being simply, > f mf x = do > f <- mf > return (f x) Or just replace map by fmap in your flist from above. All the best Christian Sievers ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: avoiding cost of (++)
Hal Daume III asked: > > mapWithout :: ([a] -> b) -> [a] -> [b] > > mapWithout f = mapWith' [] > > where mapWith' pre [] = [] > > mapWith' pre (x:xs) = f (pre ++ xs) : mapWith' (x:pre) xs > > Unfortunately, this is very slow, due to the overhead of (++). > > Any way I could speed this up would be great. Note that order doesn't > matter to 'f', but I do need that the order in which the elements of the > list are processed be the same as in map. If f is associative, i.e. f (l1++l2) == f [f l1, f l2] (this forces a=b), you can do mapWithout :: ([a] -> a) -> [a] -> [a] mapWithout f l = let n = f [] -- neutral element b x y = f [x,y] -- binary version sl = scanl b n l sr = scanr b n l in zipWith b sl (tail sr) You'll probably rather use mapWithout' (a->a->a) -> a -> [a] -> [a] mapWithout' bin_op neutral l = ... If f is not defined for empty lists, you can combine (with a bit more work) the results of scanl1 and scanr1. HTH Christian Sievers ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: precedence bug with derived instances
Dean Herington wrote: > > Why is that expression not type-correct? > > [Answering my own question...] > > Duh. Because the type doesn't partake of Eq. Right. Of course, it's a different kind of error than for example [Orange] == Orange --- where no Eq Color instance decl would help, and I wonder if there is a special name for it. Bye Christian Sievers ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: precedence bug with derived instances
Simon Peyton-Jones wrote: > I can only make minimal changes now. I suspect the smallest change is > to require that > (x,"") `elem` readsPrec d (showsPrec d x "") > > This weakens the existing equation by not requiring (x,"") to be the > first parse returned. > > Dean writes: > | Perhaps we want: > | > | readsPrec should be able to parse the string produced by showsPrec, > and > | should deliver the value that showsPrec started with. That is, the > list > | result of > | > | readsPrec d (showsPrec d x "") > | > | should contain exactly one pair whose second element is "", and the > first > | element of that pair should be equivalent to x. > > I don't understand this. What does "equivalent" mean? And how does > this differ from the (incorrect) claim that > >readsPrec d (showsPrec d x "") == [(x,"")] That >> whose second element is "" << obviously means to apply filter (("" ==) . snd) to the list. Using list comprehension, that gives [ r | (r,"") <- readsPrec d (showsPrec d x "") ] == [x] This is nearly what you suggested, with the additional condition that there may only be one complete parse. I think this is what we want. I guess "equivalent" just means equality without suggesting that the type is an instance of Eq. There are other places where the report uses == in situations where you can't really apply it, for example, in D.2 it says "we would have [Orange ..] == [Orange, Yellow, Green]", which is true, but we can't use this expresion and expect it to reduce to True, because it is just not type correct. So I think we should ignore this problem now. All the best Christian Sievers ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: defining (-> Bool) as a set
Hal Daume III wrote: > I'd like to be able to define something like > single x = \y -> if x == y then True else False Just a note on style: it always hurts me to see something like if term then True else False -- this is just the same as 'term'. So you could say single x = \y -> x==y which is in turn just the same as single x = (x==) which is, amazingly, nothing more than single = (==) -- one can debatte whether this is still better style than the first variant, but it's surely interesting to realize. All the best, Christian Sievers ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Haskell 98 Report: October release
Simon Peyton-Jones wrote: > Feedback please... One typo: In the change for Page 93, Appendix A, Standard Prelude the comment should not talk about a "fixtity declaration". ^ Bye Christian Sievers ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: FW: Haskell 98 report problem re lexical structure.
Simon Peyton-Jones proposed: > 1. I will use "lexeme" consistently to mean what the "lexeme" > production means. That's good. > 2. The place that "lexeme" is currently used inconsistently is in 2.3 > (Comments) Here I propose to replace paras 2 and 3 thus: > > "An ordinary comment begins with a sequence of two or more consecutive > dashes (e.g. --) and extends to the following newline. The sequence of > dashes must not be the prefix of a legal lexeme. For example, Any number of dashes is a prefix of a legal lexeme. You want to talk about what follows, but this formulation is about what might follow. (Or at least, that's how I understand it.) How about something like: The sequence of dashes must not be followed by another symbol, for example --> or --| do not begin a comment, they are just ordinary lexemes. > 5. [Re Christian S's proposal, which I sent earlier, remove "opencom" > from "lexeme"] That is consisted with the other change you suggested in 2., and indeed a nicer way to be so. The second sentence in 5.5.1 reads Since qualifier names are part of the lexical syntax, no spaces are allowed between the qualifier and the name. I think this should be Since qualified names... ^ and could as well be Since qualified names are lexemes, no spaces are allowed... All the best Christian Sievers ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: lexical description problem in language report?
Thomas Hallgren wrote: > program -> {lexeme | whitespace } > lexeme -> varid | conid | varsym | consym | literal | special | > reservedop | reservedid > > There is no reference to qualified names here. I thought the purpose of > these productions were to say that a Haskell program is correct on the > lexical level iff there is a derivation of it in the lexical grammar, > starting from the nonterminal "program". Since qualified names are not > part of this grammar, they are not part of the lexical syntax, which > contradicts the text in section 5.5.1. > > So, I repeat my improvment suggestions: include qvarid, qconid, etc, in > the production for lexeme. Move the explanation of the lexical > properties of qualified names from section 5.5.1 to section 2.4. You could still parse a qualified name as three lexemes. Of course you don't want this, as this would allow white space between them. For the same reason, you want backquoted functions and constructors to be only one lexeme. In order to achieve this, just use qop instead of qvarsym and qconsym. And we need opencom, as the report says {- is a lexeme. So I suggest: lexeme -> qvarid | qconid | qop | literal | special | reservedop | reservedid | opencom It's all not new. See: http://www.dcs.gla.ac.uk/mail-www/haskell/msg01596.html http://www.dcs.gla.ac.uk/mail-www/haskell/msg01730.html All the best Christian Sievers ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Tetration operator in functional programming
I had some more ideas on Tim Sweeney's thoughts: First of all, I was releaved to see that the definition can be extended to b ^^ 0 = 1 (a functional programmer's favourite number must be zero!), or for types void --> t ~= unit > Now I am trying to understand the type-theory analogy to tetration. Given > "unit" as the one-valued type, "bool" as the two-valued type, "three" as the > three-valued type (isomorphic to "maybe bool"), etc., clearly: I find it hard to believe that the size of a flat domain can make such a difference. I find (), Maybe (), Maybe (Maybe ()), ..., which are not flat, more promising candidates. (Or Void, Maybe Void, ) Still I doubt there can be a type constructor Tetra with Tetra () t ~= t and Tetra (Maybe n) t ~= (Tetra n t) -> t, although I couldn't disprove it. It should reflect arithmetic laws of tetration, which for example relate (b ^^ (a1*a2)) with b^^a1 and b^^a2 or so, but are there any? So how should (a,b)-->t be defined? Nevertheless we can nearly do it in Haskell, it's not legal, but the intended meaning should be clear ;-) First of all, we use church numerals at the type constructor level - not my idea, must have seen it in some paper: Z :: (* -> *) -> * -> * type Z f x = x S :: ((* -> *) -> * -> *) -> (* -> *) -> * -> * type S n f x = f (n f x) Now we can define Tetra as type Tetra t n = n (->t) () just as we could define (^^) as b ^^ n = foldnat (b^) 1 n only that the fold is already built into the numerals. Tetra hasn't kind * -> * -> *, but has * -> ((* -> *) -> * -> *) -> *. Now we'd have Tetra t Z = (), Tetra t (S Z) = () -> t ~= t, Tetra t (S (S Z)) = (() -> t) -> t ~= t -> t and so on. The problems with this are: Haskell has no kind signatures, so Z gets kind * -> * -> *, you can't write (->t), and you can't use a type synonym without giving all its arguments. Still it could be instructive to ask yourself what other constructors of kind (*->*)->*->* you might use, and what you'd get. Most interessting should be Infinity: type Inf f x = f (Inf f x) (where we use x to get the correct kind) - this recursive type synonym is even more forbidden! > unit-->t ~= t > bool-->t ~= t->t > three-->t ~= (t->t)->t > four-->t ~= ((t->t)->t)->t > > So, what is going on here? "bool->t" is the type of identity functions on > t; "three-->t" is especially interesting because it is the type of fixpoint > operator from t->t to t. It's interesting (for those to which this wasn't obvious) to see that there exists a recursion- und bottom-free term (this is what type theory usually is about) of type n-->t (where n is a number) iff n is even: For n=2 there is id::t->t (or const id :: (() -> t) -> t, if you use this) - or if you take my advice and start with zero, there is ()::(). Now if you have f::n-->t, then ($f) has type (n-->t)->t'->t', which is even more general than (n+2)-->t. We know there is no term of type t = 1-->t. [For the following argument I first wanted to use the Curry-Howard-Isomorphism, but then I realized I could show it direct. Do I need it if I wanted to rigourously prove there is no term of type t?] Consider there were a term f of type n-->t = ((n-1)-->t) -> t with odd n>=3. We already know there is a term h of type (n-1)-->t, so the application f h would have type t, which is impossible. Of course it is different if you take a fixed non-void type for t. For example, ($0) has type (more general than) 3-->Int. Bye, Christian
Re: Tetration operator in functional programming
Tim Sweeney wrote: > In mathematics, there is a progression between the operators of addition, > multiplication, exponentiation, etc., known as the Ackermann hierarchy. > > The next operation in the sequence is often called "tetration" and refers to > iterated exponentiation. Let us write a^b for "a raised to the power of b", > and then a-->b for b raised to its own power a times, i.e.: > > 1-->b = b > 2-->b = b^b > 3-->b = (b^b)^b > ... This looks strange, as (b^b)^b = b^(b^2), or generally n-->b = b^(b^(n-1)). A quick web search showed me tetration as b ^^ 1 = b b ^^ (n+1) = b ^ (b ^^ n) so b^^3 = b^(b^b); clearly a more interesting (and faster growing) definition. > Now I am trying to understand the type-theory analogy to tetration. Given > "unit" as the one-valued type, "bool" as the two-valued type, "three" as the > three-valued type (isomorphic to "maybe bool"), etc., clearly: > > unit-->t ~= t > bool-->t ~= t->t > three-->t ~= (t->t)->t > four-->t ~= ((t->t)->t)->t As b^a ~= a->b, this is still correct. > So, what is going on here? "bool->t" is the type of identity functions on > t; "three-->t" is especially interesting because it is the type of fixpoint > operator from t->t to t. > > This hints that there may be some computational utility here. Is there a > useful type-theory interpretation of tetration? > > And is there a useful interpretation of tetration on infinitary types, like > lists, i.e. list(nat)-->nat? In particular, I am interested in defining the Hmm. Taking nat as fixpoint of maybe, we might reason t^^nat = t^^(fixp maybe) = t^^(1+fixp maybe) = t ^ t^^(fixp maybe) = t ^ (t^^nat) = (t^^nat) -> t, which reminds me vaguely to domains of untyped lambda calculus. HTH, Christian Sievers
Re: Typo in haskell98-report/standard-prelude.html
Marcin 'Qrczak' Kowalczyk wrote: > The name sum in the export list of PreludeList is spelled Sum > (uppercase). That's already mentioned on the Errata page at http://research.microsoft.com/~simonpj/haskell/haskell98-bugs.html It says: Page 105, Appendix A.1, line 11. In the module header for PreludeList replace "Sum" by "sum". Christian Sievers
Re: concurrency (was OO in Haskell)
Tim <[EMAIL PROTECTED]> wrote: > For example, consider a program where one thread prints a value from an MVar, > while another thread modifies it. The output of the program will vary from one > run to another, even though its input (none) is unchanged. This is not a result of using concurrency. You see the same no input/different output behaviour in a program as simple as this: > import Random > main = getStdRandom (randomR (False,True)) >>= print (Or use the Time library.) And nothing of this breakes referential transparency. For example, > main = randomints >>= print > randomints :: IO (Int,Int) > randomints = do a <- getStdRandom (randomR (1,100)) > b <- getStdRandom (randomR (1,100)) > return (a,b) has the same possible results as > main = randomints >>= print > randomints :: IO (Int,Int) > randomints = let rnd = getStdRandom (randomR (1,100)) in > do a <- rnd; b <- rnd > return (a,b) Each time a program is run it is given a different world to start with. C is as referentially transparent as you are willing to agree that each function has an implicit IO in its type, which won't gain you anything. Even that is not really enough. "volatile" variables are MVars, and what are non-volatile variables changed in signal handlers? Uncaught type errors? Enough of that. All the best, Christian Sievers
Re: Haskell Wish list: library documentation
Two poeple suggested to use Strings in the example for unzip, (and they even suggested the same strings!) > unzip [("a", 1), ("b", 2), ("c", 3)] = (["a", "b", "c"], [1, 2, 3]) This is better, but now beginners might get the impression that "c" is the way to name a Char, so I suggest to change this to unzip [("", 1), ("a", 2), ("aa", 3)] = (["", "a", "aa"], [1, 2, 3]) which even is no longer! All the best, Christian Sievers
Re: Haskell Wish list: library documentation
Jon Fairbairn wrote: > [3] I think this example is slightly easier, though on second thoughts > > unzip [('a', 1), ('b', 2), ('c', 3)] = (['a', 'b', 'c'], [1, 2, 3]) > > is better still. It's a good idea to use two different types in an example, but Char is not well chosen, because the canonical way to write the above result is ("abc",[1,2,3]). Bool might be a better choice, although it only has two values with quite long names. Christian Sievers
Re: Monads in plain english (Was: Re: Licenses and Libraries)
> > Indeed. But if you get this far, understanding (>>=) quite trivial > > (assuming you don't have problems with higher-order functions). > Yes, it would be quite trivial. But why bother? You only need (>>=) > if you want to declare your own instance of Monad, which probably doesn't > need to be in an introductory course. I think I would feel quite unsatisfied if I didn't know that 'do' is not some strange feature which seems to be unrelated to the rest, but only some syntactic sugar for very normal higher order combinators. And even if propably none ever needs it, I feel much happier to know that 'zipWith (>>=)' is there and doesn't have to be written in do-syntax. This is what reassures me that 'IO a' is an abstract, but otherwise normal data type. It may be useful, in the beginning of a course, to tell the students how to do some simple IO using 'do' in a recipe like manner. (But if they are using an interpreter and don't have to write a main function, you can as well leave this out.) But in order to explain monads even to someone who wouldn't define his own, I'd surely not conceal (>>=). Alll the best, Christian Sievers
Re: Units of measure
> > (Cayenne doesn't happen to have c*n-patterns?) [ ;-) forgotten.] > `c*n' and `n+k' are equally abominable. Cayenne has neither. I thought they might be nice to express the type of sqrt. When we have the type as > Unit (mass::Int) (length::Int) (time::Int) = Double it should be s.th. like Unit (2*m) (2*l) (2*t) -> Unit m l t. Now I realized that the type does indeed nearly look like that, but without using any doubtful pattern matching features: > sqrt :: (m::Int) |-> (l::Int) |-> (t::Int) |-> >Unit (2*m) (2*l) (2*t) -> Unit m l t (Will hidden arguments work in this case?) I really like Cayenne. All the best, Christian Sievers
Re: Units of measure
Anatoli Tubman wrote: > I once wrote a C++ template library that did exactly that. Arbitrary units, > rational exponents -- you can have (m^(3/2)/kg^(5/16)) dimensioned value. > All at compile time, without runtime checking whatsoever. Is there any sense physically in rational exponents? If not, we could use this extra information for less permissive type checking, for example only allowing a square root from an argument that has only even exponents. (Cayenne doesn't happen to have c*n-patterns?) Christian Sievers
Re: Haskell MIME types?
Alexander Jacobson wrote: > Postscript interpreters also have the ability to execute rm *. > The difference is that postscript interpreters have a command line option > to turn off file system access capabilities. > Is there a command line option in hugs to disallow import of System? I don't think disallowing some imports is the way to go. For example, you also have Directory.removeFile, but I'd rather not suggest to disallow importing Directory. Instead, operations that an untrusted code shouldn't execute could raise an exeption like isPermissionError or isIllegalOperationError. In *nix-land, we might chose to just run Hugs under its own UID, so it might even write its own files, and delete them, but only them. > > On Tue, 24 Aug 1999, Fritz K Ruehr wrote: > > > > | I just convinced my local sysadmin to attach a new MIME type to > > | outgoing Haskell programs sent by our web server, namely > > | "application/x-haskell". Maybe the Haskell-Version should also go into the MIME type name, as in "application/x-haskell98". All the best, Christian Sievers
Re: The dreaded layout rule
I wrote: > lexeme -> qvarid | qconid | qvarsym | qconsym > | literal | special | reservedop | reservedid > > Now we could replace qvarsym and qconsym by qop, and have both > examples parse in the same way. However, unlike the other change in > lexeme's definition, I don't suggest this, I only want to point out > that there is a (formally) simple way out of the present somewhat > inconsistent state. I changed my mind about this issue, I do suggest to change it as proposed, for if `elem` were three lexemes, any whitespace between them would be allowed. This might even be considered a typo, as I think no one intended to allow expressions like x ` {- look ma -} elem -- comments inside! ` l All the best, Christian Sievers
Re: The dreaded layout rule
Carl Witty wrote about layout horror and reasoned that >do { a `elem` b ` > is a legal prefix of the Haskell grammar: it could be completed by >do { a `elem` b `seq` c } > for instance. So no implicit close-brace gets inserted; and >a `elem` b `elem` c > is a syntax error. which seems right. It would be treated the same as the "a == b == c" case if `elem` were one lexeme, not three. I already argued (in http://www.dcs.gla.ac.uk/mail-www/haskell/msg01596.html, to which I'd really like to know your thoughts) that lexeme's definition is wrong and should be: lexeme -> qvarid | qconid | qvarsym | qconsym | literal | special | reservedop | reservedid Now we could replace qvarsym and qconsym by qop, and have both examples parse in the same way. However, unlike the other change in lexeme's definition, I don't suggest this, I only want to point out that there is a (formally) simple way out of the present somewhat inconsistent state. I like Simon Marlow's solution to have fixity resolution separated from parsing. Please don't let this trouble be a reason to abandon layout! Christian Sievers
Re: Strange lexical syntax
Simon Marlow wrote: > Quick quiz: how many Haskell lexemes are represented by the following > sequences of characters? > > 1) M.x > 2) M.let > 3)M.as > 4) M.. > 5) M... > 6) M.! > > answers: > > 1) 1. This is a qualified identifier. We all know what M.x means, but recently I wondered about how the report makes this sure. I'm afraid it doesn't. Of course, there is section "5.5.1 Qualified names" saying: A qualified name is written as modid.name. Since qualifier names are part of the lexical syntax, no spaces are allowed between the qualifier and the name. Sample parses are shown below. [I guess "qualifier names" should be "qualified names".] But this seems to be an explanation, not an additional information. The second sentence seems to say M.x is a lexeme, as they are the fundamental items of lexical analysis. (Section "2.2 Lexical Program Structure": At each point, the longest possible lexeme satisfying the lexeme production is read, using a context-independent deterministic lexical analysis ...) And if it weren't a lexeme, we're really in trouble, because: Any kind of whitespace is also a proper delimiter for lexemes. Still it isn't. It surely is a qvarid, but lexeme is defined like this: lexeme -> varid | conid | varsym | consym | literal | special | reservedop | reservedid A varid is unqualified, and it is also none of the others. So maybe this should be: lexeme -> qvarid | qconid | qvarsym | qconsym | literal | special | reservedop | reservedid And then I guess we should have qtyc{on,ls} -> qconid . Am I terribly missing something? > 2) 3. 'let' is a keyword, which excludes this string > from being a qualified identifier. That's really ugly. I never thought about such things. Good you finally uncovered it. > 3) 1. 'as' is a "specialid", not a "reservedid". > > 4) 1. This is a qualified symbol. > > 5) 2. '..' is a reserved operator, so a qualified symbol > is out. The sequence '...' is a valid operator and > according to the maximal munch rule this must be > the second lexeme. > > 6)1. '!' is a "specialop", not a "reservedop". > > > I especially like case 5 :-) Yes, it's amazing! Why didn't you go on? M is a qualified symbol? > This is pretty bogus. I suggest as a fix for Haskell 2 that all of the > above be treated as 1 lexeme, i.e. qualified identifiers/symbols. But what would M.let mean? Module M can't define let, neither this way M.let = ... -- qualiefied name not allowed nor that: let = ...-- let is reserved However, 'let' does mean something in module M, so a strange option is to let 'M.let' mean 'let'. Should we just disallow it? There is still another problem in the report. Section "2.3 Comments" says: A nested comment begins with the lexeme "{-" ... There is no such lexeme. We'd need lexeme -> ... | opencom What does M.-- mean? All the best, Christian Sievers -- Freeing Software is a good beginning. Now how about people?
Re: Haskell conventions (was: RE: how to write a simple cat)
> So, the name of a type is always at least a full word, as are the names of > specific functions. But type variables are almost always single > characters, and distinct from the names of any type. Conventionally, they > are also usually "a", "b", and "c", although "m" is for monad. > Conventionally also, generic function arguments are "f" and "g", the > conventional predicate is "p". Generic arguments are "x" and "y" (or "xs" > and "ys" if they are lists); arguments with specified types are usually > the first letter of their type name (e.g., "c" for Char, "i" for an Int; > "n" and "m" are indices)... that covers most of it, I think. I've never thought about a difference between i (and j) on the one hand and n and m on the other, besides I would use i, j more locally, if there were such a difference. So I might use i<-[1..n], but would nearly never use n<-[1..i]. If I don't do pattern matching on a list, I sometimes use l. Otherwise, I use (a:as) as well as (x:xs) for lists. I'm in trouble when it comes to @-patterns: is xs@(x:_) acceptable? For non-integral numbers, I often use x, y. > I think most of the Haskell code I've ever seen that *wasn't* written by > me follow these conventions pretty closely. But the strange thing is...I > haven't found a prominent place on, e.g., the Haskell home page where this > is spelled out. (Please tell me if I'm missing anything obvious.) In a > way, I guess this is trivial, but I know from hard experience it can often > take a long time to become completely aware of trivial things. I've seen the (x:xs) (or whatever letter you want, BTW I'd use (f:fs) for a list of functions) convention written somewhere. Most of the rest is what is usually used in mathematics or is done in any computer language (such as c for Char). Yes, a list of these things might be helpful. Christian Sievers
Re: Church numerals in Haskell
Jerzy Karczmarczuk wrote: > 6. Subtraction. Largo. >According to some folklore Church himself thought for some time >that it is not possible to define the subtraction using pure >lambdas. >In fact it is possible to subtract Church numerals (but never >getting negative numbers, of course) The following solution is >silly, but please find a *really* better one... > >First the incrementation: inc n s z = n s (s z) >(You may use it also to define the addition.) > >Then the iteration defining the decrement > dec n = d zer where > zer s z = z > v = n s z -- global constants > d m = let h = inc m > in if h s z == v then m else d (inc m) >and the subtraction is the iterated decrement. Its complexity >is really bad (n^2). Compared to using equality, I think the following is really better: dec n = fst (n (\(_,b)->(b,inc b)) (zer,zer)) where zer s z = z Of course, you wouldn't really use built-in pairing, would you? Christian Sievers
RE: non-linear patterns
Frank A. Christoph gave examples for unintended non-linear patterns, among them: > Or, even more more common: > > f (x@(x,y)) = ... --- oops! If I don't oversee something obvious, this just would fail to type-check, so this shouldn't be a problem. Christian Sievers
Re: Haskell-98 Quiz
Magnus Carlsson wrote: > Here are some questions for the Haskell-98 enthusiasts. I'm not sure if I'm a Haskell-98 enthusiast, I still call myself a Haskell enthusiast. > 1. Why is the following declaration group illegal? > > f :: String > f = g 1 ++ g True > > g :: Show a => a -> String > g x = fst (show x, show f) I don't see why it should be illegal, but then nor does Hugs 98. It is happy with this definition and gives "1True" for f. So if you found a subtle strange thing in Haskell 98, you also found a bug in Hugs. Christian Sievers
Re: Modifying the monomorphism restriction
John Hughes wrote: > Everybody agrees the monomorphism restriction is a pain: Hmm well, it's really not a nice thing. > Some suggest that it is enough for compilers to issue a warning when using > call-by-name. I disagree strongly. Such a warning may alert the programmer > at the time the overloaded definition is compiled. But programmers need to > understand programs at other times also. The person reading through the code > of a library, for example, trying to understand why a program using that > library is so slow or uses so much memory, will not be helped by warnings > issued when the library was compiled. The distinction between call-by-need > and call-by-name is vital for understanding programs operationally, and it > should be visible in the source. In a library I'd really expect to see a big comment when such a thing happens. > So, let's make it visible, in the simplest possible way. Let there be TWO > forms of binding: x = e, and x := e (say). A binding of the form `x = e' is > interpreted using call-by-name, and may of course be overloaded: it makes `x' > and `e' exactly equivalent. A binding of the form `x := e' is interpreted > using call-by-need, and is monomorphic; `x' behaves as though it were > lambda-bound. Now, for example, > > pi = 4*arcsin 1 > > is an overloaded definition which (visibly) risks duplicated computation, > while > > pi := 4*arcsin 1 > > is a monomorphic definition at a particular instance which (visibly) does not. But which instance? In this case the default mechanism can give the answer, but in general, you would have to give a type unless `e' already has a monotype. So you could use `x:=e' without a signature exactly when you now could use `x=e' without one. > Advantages of this idea over the existing MR: > > * Monomorphism is decoupled from the syntactic form of the definition. There > is no need to `eta-convert' definitions to get them into a form that the MR > does not apply to. The difference between `x=e' and `x:=e' is surely a syntactic one, though arguably one that is easier to justify. > * Monomorphism is decoupled from overloading. With this proposal, x := e is > always a monomorphic definition, whether the type of e is > overloaded or not. Again: how can this be? > Thus small changes to e cannot suddenly bring the MR into effect, perhaps > invalidating many uses of x. > > * Monomorphism is decoupled from type inference. One may leave the type of > a variable to be inferred regardless of whether it is bound by name or by > need. > > Disadvantages: > > * Requires another reserved symbol. > > * When converting Haskell 1.x to Haskell 2, many := would need to be inserted. > Failure to do so could make programs much less efficient. An (optional) > compiler warning could help here. I don't see this. Or do you want to always recalculate any value defined with `=' instead of `:=' ? > An alternative design would be to use := to indicate polymorphism/overloading > in pattern bindings, but retain = for polymorphic function bindings. That > would make conversion from Haskell 1 to Haskell 2 simpler (one would simply > replace = by := in pattern bindings with an overloaded type signature), but is > an unattractively inconsistent design. I don't like this idea (yet?), and would prefer the compiler-warning version, or even keep the MR - we could make our editors smarter and let them add the types if they change too often or are just too weird for us, rather than introduce new syntax only in order to be able to leave them out. Christian Sievers
Re: how to exploit existentials
Koen Classen explained how to do without existantials like this: > class Item i where > foo :: i -> Int > step :: i -> i [...] > data ITEM = MkItem { nStepsThenFoo :: [Int] } > > And a helper function: > > mkItem :: Item i => i -> ITEM > mkItem i = MkItem { nStepsThenFoo = map foo (iterate step i) } instaed of > | > data ITEM = forall i . Item i => MkItem i and says that > I have applied this method several times when I thought I needed > existential types, but I didn't need them at all. I think this might be > the case more often. I believe it is always possible, but it soon gets unmanagable. If class Item contained one more member step' :: i -> i you would already have to define a tree of extractable values. And if there are functions with types like i->i->i or i->[i], it gets really weird. Still I guess it should be possible... You 'only' need a structure that reflects the ways you can build a term of a type that does not contain the existantially qualified type variable. (See my handwaving?) So the moral seems to be that Koen is right in his introduction where he says: > Don't get me wrong, I think existential types are very useful, but in some > cases the answer is just around the corner in Haskell98, not needing > exisistential types at all. BTW: The examples here showed me that and how it is possible to constrain existantial types. This is something I already wished, but I didn't know it was in hugs yet. Christian Sievers
Re: Haskell 98 final stuff
Simon writes: > 2. The data and type constructors > (), (,), (,,), etc > [] > (->) > are all regarded as "syntax", not as identifiers. They always mean > their standard meaning (tuples, empty list or list type constructor). > [No change here.] > > The question is: what about the list constructor ":". In principle > we could regard it as an ordinary identifier, and therefore allow someone > to redefine it... but [there are problems.] > > I have concluded that it is simpler to treat ":" as syntax, exactly > uniformly with the others. It always means list construction, and > it cannot be hidden or redefined. > Section 2.4. Clarify that : is reserved solely for Haskell > list construction. What does this mean? Will there only be a remark, or will the syntax be changed? The other constructors are explicitely handled by the syntax, so I guess this should be done in this case also. Doing that 'exactly uniformly' would mean productions for expressions e:e, patterns (p:p) and the constructor (:). But we surely don't want to loose the sections (e:) and (:e). Please don't forget them! All the best, Christian Sievers
on underscores
This may be too late for Haskell 98, but who knows: I could always write functions like > f foo _ = ... and when I see such a lhs, I know that the second argument of f is not used. This is not a convention, but enforced. Even if it is not used, I might like to document what the second argument is, like this: > f foo _bar = ... This is the intended usage, if I remember right. Now the reader sees that the second argument is something the programmer would call bar, and the leading underscore gives a hint that it might not be used. But this time, this is not enforced, and the reader has to look through the rhs to be sure. Knowing that an argument is not used is an advantage, and knowing what it is is also an advantage, so to get both advantages we should disallow identifiers starting with an underscore on the rhs. The syntax could reflect this by not generating them as varid, but as apat. Does this make sense? Easier and less important: can't we allow _ as dummy type variable? It should have the usual 'each occurance is different' semantics, so that the most general type of > fst3 (a,_,_) = a could be expressed as > fst3 :: (a,_,_) -> a Or is it already allowed? I tried it with hugs right now, and it worked, but I don't see how this is justified by the syntax given in the 1.4 report. Merry Haskell 98 day, Christian Sievers
RE: MonadZero (concluded)
> > Yes, nuke MonadPlus. For Haskell 2 we can put these things in a > > wonderful Monad library. > > I had thought that too many functions depend on MonadZero/Plus, > but actually, it's the following: > > filterM :: MonadZero m => (a -> m Bool) -> [a] -> m [a] > guard :: MonadZero m => Bool -> m () > mfilter :: MonadZero m => (a -> Bool) -> m a -> m a > concatM :: MonadPlus m => [m a] -> m a > > These would all vanish, along with MonadZero/Plus. > The Monad library itself doesn't mention MonadZero/Plus, as it happens. > > Phil's proposal: > delete class MonadZero, MonadPlus > delete filterM, guard, mfilter, concatM > > This is ok by me. Does anyone object? In fact I don't know these functions, but when they were in the Prelude can they be less important than those in the Monad library? Why don't we move the classes and functions into a wonderful Monad library already now for Haskell 98? And, BTW, the library report defines types for zeroOrMore and oneOrMore, which both are (MonadPlus m) => m a -> m [a], but doesn't mention them later. Christian Sievers
Re: Two prelude/library matters
> 1. The Show class > ~~ [...] > class Show a where > showsPrec :: Int -> a -> ShowS > show:: a -> String -- NEW > showList :: [a] -> ShowS > > showsPrec _ x s = show x ++ s > show x = showsPrec 0 x "" > showList= ...existing default declaration This gives one more example of what I always wanted to suggest: The documentation of a class should clearly state which the minimal sets of definitions are that one has to give, rather than let the reader figure this out from the code. Default class definitions are very convenient, but these recursive ones that look like everything is already defined are a bit mysterious. I agree one might like to define one member function, another, or both, but tell them what to do at least. This change looks very good. The default for (==) however seems odd to me. Someone could like to define (==) alone or both (==) and (/=), but it seems strange to me to only define (/=). Or do you just want to give all expressible relations? And while you're still doing non-hurting class definition changes, let me repeat this: please let succ and pred be Enum class members. Christian Sievers
Re: MonadZero
Hi, it seems to be much too late after all the discussion but among the alternatives was > 3. Make tuples special, so that g would be in Monad, but > if we had a user-defined single-constructor type instead > then it would be in MonadZero about which was said > (3) seems dreadful. I'm not so sure. If we don't call it make them special, but let them be unlifted products (and hence irrefutable patterns), how would that sound? Why are they lifted, anyway? If it's only so that we can say tuples are nothing but syntactic sugar for something one might otherwise declare as a data definition oneself, I'd be happy to give that away. And I never liked the lifting of single-constructor types, so I don't use them. After all, there is still newtype. I also like (5) [status quo]. I don't feel happy with the proposed changings in the definition of Monad, but I can't give good (let alone new) reasons for that. Christian Sievers
let succ be an Enum class member
Hello, this is about a change in the prelude I'd like to suggest. The following is obviously not what one would expect: Prelude> succ 100::Integer Program error: {primIntegerToInt 100} However, with the prelude defining succ to be succ,:: Enum a => a -> a succ = toEnum . (+1) . fromEnum we can't hope for anything better. My suggestion is to make succ a member function of class Enum, with the old definition as default, so that the instance Enum Integer can define it to be simply (+1). Another example is data Nat = Zero | Succ Nat where succ=Succ is not only more natural, but also much more efficient. Of course the same holds for pred. What do you think? Are there any drawbacks? Could it be like this in standard haskell? Christian Sievers
Re: how about main :: IO Int
Thank you for pointing me to the System library. However, while I was indeed implying that there is no way of returning an exit code, my main question was which type main should have. You seem not to like IO Int (one even for several reasons ;-) but it still looks quite natural to me. Christian Sievers
Re: what's wrong with instance C a => D a. Reply
I wrote: Sergey Mechveliani wrote: : As to `instance D a', : it is not a loss. Because `instance D a' is the same as : `class D a' - supplied with the default definition. For example, : the illegal declaration pair : : classC a => D a where d :: a -> a : : instance C a => D a where d = : : : can be replaced with the legal and simpler declaration : : class C a => D a where d :: a -> a : d = : [...] You're equivalence is correct ... Buzzz. No, it's not. It does not actually give any instance of D. You have to declare all of them seperately, and you would rather want to just say instance C a => D a but you can't. It's much like the Textual example. Christian Sievers
Re: what's wrong with instance C a => D a. Reply
Sergey Mechveliani wrote: : As to `instance D a', : it is not a loss. Because `instance D a' is the same as : `class D a' - supplied with the default definition. For example, : the illegal declaration pair : :classC a => D a where d :: a -> a : :instance C a => D a where d = : : : can be replaced with the legal and simpler declaration : :class C a => D a where d :: a -> a : d = : : Correct me please, if this is a mistake, I am not much of an : expert in Haskell (though keep on programming for two years!) You may have learned from my other posting that I am also not an expert :-) -- quite enthusiastic though. You're equivalence is correct (as much as an illegal decl. can be equiv. to a legal one), but not general enough for me. I didn't want the class D to be a subclass of C. Maybe I should give the example that I have abstracted away from. It's a simple variation of an example from Mark Jones, given in "Fun. Prog. with overloading and higher-order polymorphism" in 1st Int. Spring School on Adv. Fun. Prog. Techniques, LNCS 925. There he defines > class Dual a where dual :: a -> a (dual is expected to satisfy dual . dual = id) > instance Dual Bool where dual = not > instance (Dual a, Dual b) => Dual (a->b) > where dual f = dual . f . dual > instance (Dual a) => Dual [a] where dual = reverse . map dual and has also > instance Dual Int where dual = negate which I tried to replace by the obvious generalisation ?> instance (Num a) => Dual a where dual = negate However, this is not legal in haskell (no problem for gofer). While this was just experimenting, there might be other examples where one would like to be able to have instance decls like this. The report suggests using class (Read a, Show a) => Textual a for which one would have to give explicit instance declarations as well. If I want to give it for all possible instances, I would want to write instance (Read a, Show a) => Textual a but I can't. : As to instance ... => C (a ,a) where ..., : ... => C (Int,a) where ..., : and such, : they might express a very meaningful mathematical sense, these : constructions are highly desirable. Actually, these worry me less. If they are meaningful, maybe they should be given meaningful names. For example, the one you left out, namely [[a]], if it has some special meaning, which [a] has not, then there is something really special about it, and it should be called Matrix a or so. Though less obvious, I think the same holds for the other examples. Still, I'd prefer if they were allowed... Christian Sievers
how about main :: IO Int
Hello, I just wondered if it was ever considered to let the main function have the type IO Int, in order to let the haskell programm be able to return an exit code to the calling environment, as C's int main(...) does. I think real programms sometimes want to exit(1) in some cases. Christian Sievers
what's wrong with instance C a => D a
The report says explicit that instance declarations like instance C (a,a) where ..., or for (Int,a) or for [[a]] are not allowed. I tried to understand this by thinking these types are too complex, but I had to learn that a type may also be too simple, i.e. just writinginstance D ais not allowed either. I had to look at the grammar to believe it. At least with a context as in the subject line, this should be useful. However, I don't suggest (only) this should be added, I rather hope that the people arguing for multi parameter type classes will make it (if not in Standard Haskell, then maybe in Curry:). I now only would like to know why this design decission was made, are there any problems with the instance declarations I have in mind? Christian Sievers