- Haskell - Haskell.org

Non-determinism in newline in the Haskell report
by Ian Lynagh 02 Feb '02

02 Feb '02

Hi all, The report says whitechar -> newline | return | linefeed | vertab | formfeed | space | tab | uniWhite newline -> a newline (system dependent) return -> a carriage return linefeed -> a line feed so, if your system defines a newline to be a line feed, an implementation is free to choose whether to lex a line feed as a whitechar or a newline, which makes quite a difference when you consider the layout rule! newline can't be arbitrarily determined by the system - certainly "x" or "let" would not be acceptable - and having it system dependent means that Haskell scripts are not portable between different systems. I haven't looked but I would be surprised if current implementations behaved differently on different platforms - I assume they all look for something matching (<CR><LF>?)|<LF> everywhere. I propose replacing the above with the following. It does mean that <CR><LF> creates 2 newlines, but I don't believe this should be a problem. whitechar -> newline | vertab | formfeed | space | tab | uniWhite newline -> return | linefeed return -> a carriage return linefeed -> a line feed Thanks Ian, who really should have noticed this months ago

1 0

Re: (no subject)
by John Hughes 25 Jan '02

25 Jan '02

> Those two constructs are not the same > Compare > newtype T1 = C1 Bool > data T2 = C2 !Bool As for as I can tell, the only difference in the Report between a newtype and a tuple type with a completely strict constructor is in the rules for pattern matching. So I am trying to find someone who can explain the reason for the difference in the rules! Right. case x of C2 b -> ... forces x, of course: matching on a datatype is always strict, and a strictness annotation on a component certainly shouldn't change that. case x of b -> ... does NOT force x: binding something to a variable is lazy. case x of C1 b -> ... does not force x either: the point of newtype is JUST to introduce a new type isomorphic to, but different from, the old, and therefore the presence or absence of the newtype constructor should have no effect at all on the evaluation of the program. Otherwise you couldn't refactor a program to distinguish between two types previously identified, without potentially changing its semantics. Of course this was a design choice, but you can't get away from the fact that the "natural" matching on T1 is lazy, and on T2 is strict. Given that, I think it's a cleaner design to have two constructs, than to make do with just data and settle for "nearly" preserving semantics when making a new type distinction. John Hughes

1 0

RE: Explicit Universal Quantification Bug?
by John Hughes 25 Jan '02

25 Jan '02

| I'm trying to learn more about Explicit Universal | Quantification so I decide to run the following supposedly | correct code from the ghc user | guide: | | >module Dummy where | > | >import ST | > | >newtype TIM s a = TIM (ST s (Maybe a)) | > | >runTIM :: (forall s. TIM s a) -> Maybe a | >runTIM t = case t of {TIM l -> runST l} Just to explain this a little more, the problem with the above is not the type of t (which is generic, as the type signature says), it's the type of l. The type of t is instantiated at the "case t of ...", let's say to TIM s' a, and the type of l is thus ST s' (Maybe a), which is NOT generic. Hence l cannot be passed to runST. The type of l cannot be generalised at the occurrence in runST l, because the type variable s' appears in the environment at that point (in the type of l itself). As you discovered, the correct way to say it is runTIM t = runST (case t of {TIM l -> l}) In this case, the (generic) type of t is instantiated as before, and the entire case expression has type ST s' (Maybe a). But this time l is not in scope (outside the case), and so the type variable s' can be generalised. Hence the case can be passed to runST. Here's another variation for you: runTIM :: (forall s. TIM s a) -> Maybe a runTIM t = let TIM l = t in runST l This one is OK, because a let binding generalises the type of the bound variable. Thus l is given the type forall s'. ST s' (Maybe a), and the call of runST types. Thus the problem with the first form above is just that a case binding doesn't generalise the types of the bound variables. As far as I know, there's no reason why it shouldn't, but that's just the way Haskell is. It's a pain, but there we are. John Hughes

1 0

RE: Explicit Universal Quantification Bug?
by Simon Peyton-Jones 25 Jan '02

25 Jan '02

| I'm trying to learn more about Explicit Universal | Quantification so I decide to run the following supposedly | correct code from the ghc user | guide: | | >module Dummy where | > | >import ST | > | >newtype TIM s a = TIM (ST s (Maybe a)) | > | >runTIM :: (forall s. TIM s a) -> Maybe a | >runTIM t = case t of {TIM l -> runST l} This is a hopeless bug in the user manual. Sorry about that. It's not there any more in any case. As you discovered, the correct way to say it is runTIM t = runST (case t of {TIM l -> l}) Simon

1 0

Re: Explicit Universal Quantification Bug?
by Rijk-Jan van Haaften 25 Jan '02

25 Jan '02

Jay Cox wrote: >I'm trying to learn more about Explicit Universal Quantification so I >decide to run the following supposedly correct code from the ghc user >guide: > > >module Dummy where > > > >import ST > > > >newtype TIM s a = TIM (ST s (Maybe a)) > > > >runTIM :: (forall s. TIM s a) -> Maybe a > >runTIM t = case t of {TIM l -> runST l} <...> >so, is this a bug? No, it is correct and expected behaviour, as I will explain below. >I noticed also the following code compiles fine. (slightly modified >from a message on this list titled "Re: Type problem with ST monad" >dating April 23, 1999 > > >module Dummy where > > > >import ST > > > >newtype TIM s a = TIM (ST s (Maybe a)) > > > >runTIM :: (forall s. TIM s a) -> Maybe a > >runTIM t = runST (deTIM t) > > > >deTIM (TIM t) = t Perfect example for explanation of the problem. The difference is between > >runTIM t = case t of {TIM l -> runST l} and > >runTIM t = runST (deTIM t) > >deTIM (TIM t) = t In the last one, after the type checker has verified that deTIM is type-correct, it can safely generalize the type of deTIM, because it is a top-level function. This means that if we have f :: a -> String f x = "Hello, world" we are allowed to apply f to an Int in one place, and to an Char in another place: g :: (String, String) g = (f 3, f 'a') This is common and well-known behaviour, and it's possible to prove that this never gives problems. However, in > >runTIM t = case t of {TIM l -> runST l} the argument 't' is non-generic. If we have the function g :: (a -> String) -> (String, String) g f = (f 3, f 'a') a problem appears. 'f' is used in a generic way, being applied to arguments of different types, which is not allowed because if we have h = f (\x -> show (x + 1)) the second part of the tupel is undefined, though this would be type-correct. This is clearly undesirable. So we have to restrict f to be non-generic. Consequently, types of variables which are derived from it must be non-generic as well. In particular this applies to 'l'. Thus, 'l' can't be generalized to fit in the type of runST. With this burden of information about generic and non-generic, we can say in short: > >runTIM t = case t of {TIM l -> runST l} is wrong because l CANNOT be generalized to fit the type of runST. > >runTIM t = runST (deTIM t) > >deTIM (TIM t) = t is correct because deTIM CAN be generalized, so it fits the type of runST Rijk-Jan van Haaften

2 1

ANNOUNCE: popenhs-1.00.0 released
by Jens Petersen 25 Jan '02

25 Jan '02

Version 1.00.0 of popenhs is out. You can get it from: http://www.01.246.ne.jp/~juhp/haskell/popenhs/ popenhs is a small library providing lazy string output from and input to a subprocess. The interface provided by "popen" now differs from the "popen3" offered in 0.00 by taking an input string argument instead of returning an input handle. Thanks to Uwe Schmidt for reporting the problem in the previous release of popen3 hanging on a closed input pipe, that led to this new implmentation, which I believe fixes the problem. Jens

1 0

(no subject)
by David Feuer 25 Jan '02

25 Jan '02

Martin Said: > Those two constructs are not the same > Compare > newtype T1 = C1 Bool > data T2 = C2 !Bool > the difference is that the constructor C1 does not exist, so only the following values exist for T1: > C1 True (which is the represented as True) > C1 False (which is the represented as False) > C1 _|_ (which is represented as non-termination or error) > however, for T2, another value exist, namely _|_. > So, pattern matching on (T2 x) may fail it the value is > _|_. You are > right that semantically newtype is the same as always matching lazily on the constructor. The report says clearly that for a newtype like T1, C1 _|_ = _|_ This is the same as for T2 and C2. As for as I can tell, the only difference in the Report between a newtype and a tuple type with a completely strict constructor is in the rules for pattern matching. So I am trying to find someone who can explain the reason for the difference in the rules! I really want to know, because I think/hope that it will help me understand certain things about how to write efficient code. > The case for a tuple type (a,b,c) for instance, is different. Here there > is a constructor, you can even type it by itself, it is > (,,), try ":t > (,,)" in hugs or ghci. I don't understand what you're talking about here.... Of course there's a constructor... This message has been brought to you by the letter alpha and the number pi.

2 1

newtype pattern matching
by Feuer 25 Jan '02

25 Jan '02

Why is pattern matching on newtypes lazy? Does this add to efficiency somehow? If not, it seems to be just another rule to keep straight.

2 3

vim syntax highlighting file for TeX and Haskell in the same file
by Ian Lynagh 25 Jan '02

25 Jan '02

Hi all I have written a vim syntax highlighting file which, given a literate script with TeX markup surrounding the Haskell code, will highlight both the TeX and Haskell. lhaskell.vim is at http://c93.keble.ox.ac.uk/~ian/haskell-vim/lhaskell.vim along with haskell.vim and tex.vim, but you should not need these as they should come with vim. lhaskell.vim should go in ~/.vim/syntax/ or somewhere else in your runtimepath (type ":set runtimepath" in vim to see it) A demo of what it should look like is at http://c93.keble.ox.ac.uk/~ian/haskell-vim/Demo.png I'm not sure how well it will work (if at all) in versions of vim prior to 6.0. Enjoy! Ian

2 1

RE: ideas for compiler project
by George Russell 24 Jan '02

24 Jan '02

One thing I would very much like to see done in a functional language is fault-tree analysis. A fault tree has as nodes various undesirable events, with as top node some disaster (for example, nuclear reactor meltdown) and as leaves various faults which can occur, with their probabilities (valve fails, operator doesn't notice red flashing light, and so on). Each internal node has a logical operator (often just AND or OR) associated with it; the fault associated with that node cannot happen unless the operator applied to the children nodes occurs; EG ("the water pressure won't get too high unless the valve fails AND the operator doesn't notice the red flashing light"). Thus you can (assuming all the faults at the leaves are independent) bound the probability of the top node happening by bounding the probability of a particularly horrendous logical expression in a number of independent binary variables being true. Unfortunately working out the probability is extremely hard to do (it's #P-complete) and simulation (running it lots of times) is not accurate since the top probability is (hopefully) extremely low, and so hard to estimate accurately without an awful lot of tests. So the commercial software for this (extremely important) problem has to adopt a very large number of heuristic approaches, for example trying to split the problem into smaller parts which only have a few nodes in common, trying to come up with a set of "cut sets" of faults, such that the top event cannot occur unless at least one of the cut sets has all faults occurring, and so on. There are lots of potential logical reorderings you can attempt on the tree to try to simplify things. The challenge is to come up with a reasonable way of finding a good upper bound for the top probability, while keeping your code sufficiently simple that those of us who live near nuclear reactors can trust it. I think my approach would be to regard this as a graph transformation problem where the aim is to transform the input fault tree into one of a simpler form (where it is not too hard to bound the top probability) by a number of well-defined operations guaranteed not to decrease the top probability. The heuristic part of the program (the largest part) would use a number of ad hoc methods (such as simulations and attempting to compute partial derivatives in terms of node probabilities) to search for the reduction which increases the top probability the least; it would hand over the result of its search to a verification part which would compute the actual bound, so that only the verification part would have to be guaranteed bug-free. Has anyone done anything like this already, by the way? There ought to be money in it . . .

1 0