[Haskell-cafe] Re: Existentials and type var escaping
Roberto Zunino wrote: foo, as defined above does not work (lazy patterns not allowed), and in foo y = E (case y of E x - x) a variable escapes. I also tried with CPS with no success. Is foo definable at all? I'm starting to think that it is not, and that there must be a very good reason for that... It's not definable, and there is a good reason. Existential boxes in principle contain an extra field storing their hidden type, and the type language is strongly normalizing. If you make the type argument explicit, you have foo (E t x) = E t x foo _|_ = E ??? _|_ The ??? can't be a divergent type term, because there aren't any; it must be a type, but no suitable type is available (foo has no type argument). You can't even use some default dummy type like (), even though _|_ does have that type, because you'd have to solve the halting problem to tell when it's safe to default. I'm less clear on how important it is that type terms don't diverge. I think it may be possible to write cast :: a - b if this restriction is removed, but I don't actually know how to do it. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Visual Haskell 0.2 installer bug
The Visual Haskell 0.2 VS'03 installer, downloaded today from http://www.haskell.org/visualhaskell/release-0.2/VSHaskell71.msi doesn't work correctly when a nonstandard install root is specified. All of the root-folder files go into the correct place, but files in subfolders (like bin) go into Program Files\Visual Haskell. Then when it comes time to register bin/vs_haskell.dll the installer looks in the correct place, causing registration to fail since the file isn't there. ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: Fractional/negative fixity?
[EMAIL PROTECTED] wrote: I think that computable real fixity levels are useful, too. Only finitely many operators can be declared in a given Haskell program. Thus the strongest property you need in your set of precedence levels is that given arbitrary finite sets of precedences A and B, with no precedence in A being higher than any precedence in B, there should exist a precedence higher than any in A and lower than any in B. The rationals already satisfy this property, so there's no need for anything bigger (in the sense of being a superset). The rationals/reals with terminating decimal expansions also satisfy this property. The integers don't, of course. Thus there's a benefit to extending Haskell with fractional fixities, but no additional benefit to using any larger totally ordered set. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
Re: Fractional/negative fixity?
I'm surprised that no one has mentioned showsPrec and readsPrec. Anything more complicated than negative fixities would require their interfaces to be changed. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
[Haskell-cafe] Re: Fractional/negative fixity?
I'm surprised that no one has mentioned showsPrec and readsPrec. Anything more complicated than negative fixities would require their interfaces to be changed. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rank N type tutorial?
Greg Buchholz wrote: I'm not quite sure why this is illegal... foo :: Integer - (forall a. Show a = a) foo 2 = [foo] foo x = x ...while this is just fine... bar :: Integer - (forall a. Show a = a-b) - b bar 2 k = k [bar] bar x k = k x The way to think about it is that foralls are extra function arguments. Your first example is like foo :: Integer - (a::Type - Show a - a) so a is chosen by the caller, not by you. The second case is like bar :: Integer - (a::Type - Show a - a - b) - b In order for the first case to work as you expect, you'd need the type foo :: Integer - (a::Type, Show a, a) which is traditionally written foo :: Integer - (exists a. Show a = a) -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell] Lexically scoped type variables: new proposal
Hi, everyone. Long time no see. I have a specific proposal for scoped type variables, which is totally different from plans A and B, and which I'd like people to pick to pieces for me. (Especially you, Simon.) Type variable scoping in System F is simple: the type bindings are explicit and follow the same rules as the value bindings. Type variable scoping in Haskell is complicated only because the actual binding sites of the underlying System F type variables aren't visible. In particular, GHC's type signatures are never located at type variable binding sites; at best they're nearby. I'm convinced that the only way that type variable scoping will ever make sense is if scoped type variable bindings are written at their actual System F binding sites. That's what this proposal is about. We introduce anonymous type aliases, with the syntax decl - ... | 'type' tycon or perhaps more conveniently decl - ... | 'type' tycon1 ... tyconN These are like ordinary type aliases, except that instead of referring to a type specified by the programmer, they refer to a type to be inferred by the compiler. They can appear in local bindings; for example, let { type N ; x :: [N] ; x = hello } in ... results in N being an alias for (i.e. bound to) Char in the body of the let, just as x is bound to hello. And that's all. Well, that's not all, but I think the system above, as an extension of Haskell 98, has the power of traditional scoped type variables. Note that the problem of distinguishing between local type variables and nonlocal (scoped) type variables goes away in this proposal. The rule is the same as Haskell 98's: lowercase identifiers are local to a type expression, and uppercase identifiers scope like value bindings. Explicit foralls at the top level of a type are never necessary. Also note that in this proposal, the binding site of the type variable is decoupled from the specification of the type; the type signature that fixes N (by forcing unification with a rigid type) can be located anywhere in N's lexical scope. But that's not all! (I wish it were.) The problem with putting the anonymous type aliases in let/where decls is that System F type variables aren't bound there. (They could be, but I don't think they ever are in GHC.) Where they are bound is in lambda expressions, in function bindings (when the function is called), and in pattern matching on existential dcons. The let/where syntax does suffice for those cases, but it's awkward -- you end up having to write something like f x' y = let type N x :: [N] x = x' in ... It should be possible to bind type aliases everywhere that System F type variables can be bound, for which I propose the following syntax: f (type N) (x::[N]) y = ... and analogously \(type N) (x::[N]) y - ... case e of D (type N) (x::[N]) y - ... The parentheses around (type N) are mandatory. This syntax is sensible inasmuch as functions really do take type arguments and dcons really do have type fields, and we're simply writing them explicitly in the place where they've always been. This syntax also harmonizes fairly well with the existing type alias syntax, which can kinda sorta be seen as a pattern binding in this picture. The type variables thus introduced have the same scope as pattern variables, except that they also scope over the pattern type signatures in subsequent arguments or dcon fields. And that's all, for old-style scoped type variables. I realize that capitalized type variables might take some getting used to, but I really feel like this approach, or something like it, is much easier to understand and a significantly better candidate for standardization than what we've got now. It's always clear which variables are scoped and which aren't, and the scoping rules are exactly what you'd naively expect them to be. There are no difficult choices to make in the design (except for syntax; beware of Wadler's Law). Things that worry me: * Do constraint (dictionary) parameters threaten this proposal? They aren't explicit either, and so can't be given type signatures for the purpose of fixing a scoped tyvar. Fortunately in this proposal you needn't identify the meaning of a tyvar at its binding spot, and my intuition is that, if the scoped tyvar is useful at all, there will always be somewhere in its scope where its meaning can be disambiguated by a type signature. But I'm not sure. * Something else that's slipped my mind, but I want to post this before going to bed. * What about the GHC 6.6 changes? See below. I don't know how to make this proposal compatible with GHC 6.6 because I don't understand yet how type inference works with GADTs and impredicativity. My best guess is that the correct change is to require that an anonymous type variable only alias a rigid System F type variable [introduced in the same scope], where I'm not sure whether the part in
Re: [Haskell-cafe] Re: Existentially-quantified constructors: Hugs is fine, GHC is not?
Ross Paterson wrote: Why would a type variable be present at runtime, let alone bound to _|_? Well, it'd be present in jhc. And you want your intermediate language to typecheck even if the types disappear before you get to assembly language. And the same issue shows up with dictionaries, e.g. in data MyObj = forall a. MyInterface a = MyObj a f x = myFunc o where MyObj o = x In order to make this work, you have to support lifted dictionaries, which means a potential performance penalty on every dictionary lookup. Hugs does accept that code, so I assume it's paying that penalty, unless there's some other solution to this problem that I'm missing. -- Ben ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Class System current status
Johannes Waldmann wrote: class ( Show p, ToDoc i, Reader b, ToDoc b, Measure p i b ) = Partial p i b | p i - b where ... -- (*) (*) A funny visual aspect of FDs is the absurd syntax. On the left of |, the whitespace is (type arg) application, but on the right, it suddenly denotes sequencing (tupling) I think it's fine. The p i b on the left is effectively a tuple also. It could be a tuple---i.e. the MPTC syntax could be Partial (p,i,b) and it would still make sense. The class declaration syntax is totally screwy anyway. Functional dependencies are constraints, and should be grouped with the typeclass constraints, but instead they're on opposite sides of the head. Plus the = implication is backwards. And the method declarations are also constraints. We oughta have class Partial p i b where Foo p (p,i) - b grok :: p - i - b or class Partial p i b | Foo p, p i - b where grok :: p - i - b or something. But I'm not proposing anything of the sort. I'm in favor of standardizing the syntax we've got. Syntax changes are disruptive, and I don't think they're justified unless they free useful syntax for another use, which this wouldn't. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org//mailman/listinfo/haskell-prime
[Haskell-cafe] Re: develop new Haskell shell?
Brian Hulley wrote: Donn Cave wrote: (cd /etc/stuff; cat * result) Well the problem here is that the command leaves you in /etc/stuff so you have to remember this when you subsequently execute another command. No it doesn't. The parentheses around the command sequence cause it to run in a subshell with its own private working directory. Well someone had to define the meaning of basename so if we make the definition of renif similarly built-in the comparison is between ls = mapM_ (renif txt hs) and for a in *.txt; do mv $a $(basename $a .txt); done This comparison is unfair because basename is a much more generic operation than renif. The Haskell code should be something like glob *.txt = mapM_ (\a - mv a (basename a .txt ++ .hs)) So the Haskell command is shorter, easier to read, and more re-usable, because mapM_ (renif txt hs) can be used anywhere that supplies a list of files whereas for a in *.txt doesn't make the source of the list explicit. Do they come from the current directory? What if some other list of files should be used? This makes no sense. Bash has its own set of rules. The for statement iterates over a list, which in this case is generated by a glob. If you want something else, you use the appropriate construct. The body of the for loop is just as reusable as the corresponding Haskell code. My reaction to this thread is the same as Donn Cave's: even after reading through the whole thread, I don't understand what a Haskell shell is supposed to be. It feels like people are more interested in capturing territory for Haskell than in solving any actual problem. For simple commands and pipes, the bash syntax is perfect. For anything nontrivial, I use some other language anyway. I long ago wrote a Perl script to do a far more general form of the renaming example you gave above. As far as I know, the only reason people write nontrivial /bin/sh scripts is that it's the only scripting language that's universally available on Unix systems. Even Perl isn't deployed everywhere. A Haskell shell is never going to be ubiquitous, and Haskell syntax is inferior to bash syntax for 99% of the command lines I type. On the other hand, I'm entirely in favor of extending Haskell with functions like glob :: String - IO [String]. That would be useful. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: WordPtr,IntPtr,IntMax,WordMax
John Meacham wrote: also, incidentally, for anyone on x86 that cares about math performance, use -optc-fsse2 to make it use the much nicer math coprocessor available on modern x86 cpus. I object to its characterization as nicer. It's faster, but *lower precision*. It worries me that people are so blithely abandoning those extra bits in the name of speed. A few years from now there's going to be an expensive engineering failure, and months of investigation will reveal that it was because a math library was compiled for SSE2. Be careful out there. (And while I'm on the subject, Haskell should have a LongDouble type.) -- Ben ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: WordPtr,IntPtr,IntMax,WordMax
Simon Marlow wrote: I suppose you might argue that extra precision is always good. Well... I'm having a hard time thinking of a situation where it isn't. I realize that people want reproducibility, I'm just not convinced that they should. The situations where optimization flags make a significant difference in the result are situations where the original result wasn't trustworthy to begin with. Reproducible rounding gives you a false sense of security in those cases, and doesn't make a difference otherwise. If you know IEEE 754 inside out, and IEEE double-precision is exactly what you want, then it's nice if your programming language can cater to that, but along those lines it'd be nice if Haskell supported rounding modes, trap handlers, and so on. I suppose this problem could be solved the way the analogous Int problem is solved, with a machine-precision Float and portable/reproducible Float32 and Float64. The x87 isn't the only FPU with this problem. The PowerPC has a fused (double*double)+double operation that the optimizer can't use if you need reproducibility, because it doesn't round the intermediate product. LongDouble would be fine, but storing intermediate Doubles in 80 bits is bad. The x87 registers are actually 82 bits wide, so even using LongDouble doesn't guarantee reproducibility. Maybe there needs to be a Float80 also. (Available only on x86, presumably.) -- Ben ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: WordPtr,IntPtr,IntMax,WordMax
skaller wrote: On Fri, 2006-05-12 at 00:34 +0100, Ben Rudiak-Gould wrote: Simon Marlow wrote: I suppose you might argue that extra precision is always good. Well... I'm having a hard time thinking of a situation where it isn't. Wastes space in the cache tree, slowing down the program and limiting the max size problem that can be handled. But we were talking about flushing temporary values to memory to force rounding; in this case keeping the extra precision is cheaper than getting rid of it. When that's not true, I agree that less precision is sometimes better. -- Ben ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
[Haskell-cafe] Re: Existentially-quantified constructors: Hugs is fine, GHC is not?
Otakar Smrz wrote: data ... = ... | forall b . FMap (b - a) (Mapper s b) ... where FMap qf qc = stripFMap f q the GHC compiler as well as GHCi (6.4.2 and earlier) issue an error My brain just exploded. I can't handle pattern bindings for existentially-quantified constructors. The problem here is a tricky interaction between irrefutable pattern matching and existential tuples. In Core, the FMap constructor has a third field which stores the type b, and when you match against the pattern (FMap qf qc) you're really matching against (FMap b qf qc). (stripFMap f q) might evaluate to _|_, in which case, according to the rules for irrefutable matching, all of the pattern variables have to be bound to _|_. But type variables (like b) can't be bound to _|_. From an operational standpoint, the problem is that the (fully-evaluated) value of b has to be available in the body of the let statement, which means that (stripFMap f q) must be evaluated before the body, and the let statement must diverge without reaching the body if (stripFMap f q) diverges, since no value can be assigned to b in that case. But the semantics of let clearly require that execution always proceed to the body no matter what (stripFMap f q) evaluates to. So I'm not convinced that your program is well-typed, even though it looks fine at first. I'm not sure what happens to Haskell's semantics when you allow type variables to be bound to _|_. The fact that Hugs allows it may be a bug. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: deeqSeq proposal
Andy Gill wrote: - [various reasons for deepSeq] You left out the one that most interests me: ensuring that there are no exceptions hiding inside a data structure. deepSeq :: a - b - b This ties demand for the (fully evaluated) normal form of an expression to demand for the WHNF of a different expression, which is a bit weird. I think it's cleaner for the primitive to be your strict, which ties demand for the normal form of an expression to demand for the WHNF of the same expression. In fact I'd argue that deepSeq should not be provided at all (though of course it can be defined by the user). The analogy with seq is a bit misleading---deepSeq is a lot less symmetric than seq. The expressions (x `deepSeq` y `deepSeq` z) and (strict x `seq` strict y `seq` z) are equivalent, but only the latter makes it clear that z doesn't get fully evaluated. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
[Haskell-cafe] Re: how would this be done? type classes?existential types?
Brian Hulley wrote: Is there a reason for using instead of [exists a. Resource a=a] ? Only that = looks like a function arrow, looks like a tuple. I stole this notation from an unpublished paper by SimonPJ et al on adding existential quantification to Haskell. I'm not especially attached to it. Actually I rather like forall a | Resource a. a exists a | Resource a. a a) A value 'v' of type 'exists a. Resource a=a 'would have to be internally represented as something like (dictResource_t, value_t) Yes. b) Given such a value, there is no syntactic way to distinguish the pair from the value_t stored inside it, unlike the use of 'forall' where the syntax for the constructor conveniently represents any dictionaries that have been glued onto the value (ie pattern matching against R x gives us back the dictionaries R and the plain value x)? Yes, but that doesn't necessarily mean you can't work out when to construct and deconstruct these implicit tuples. That's exactly what the type inference process does with implicit type arguments, and implicit type returns are dual to that, so the process should be similar. It is tricky, though. E.g. given (f (g z)) where f :: forall a. [a] - Int g :: String - (exists b. [b]) in principle you should be able to call g first, getting a type b and a list [b], then instantiate f with the type b, then pass the list to it, ultimately getting an Int. But I don't know how to design a type inference algorithm that will find this typing. If on the other hand f :: (exists a. [a]) - Int then it's easy to do the right thing---which is a little odd since these two types for f are otherwise indistinguishable. Hope I'm not making this more confusing but I'm still trying to get my head around all these invisible happenings regarding dictionaries so I can visualise what's happening in terms of bytes and pointers in the runtime Once you understand where the types go in System F, the dictionaries are easy: they always follow the types around. Any time you have forall a b c. (C1 a b, C2 b c) = ... in the source, you have five corresponding parameters/arguments in GHC Core, one for each type variable and constraint. These are always passed around as a unit (at least prior to optimization). In principle you could box them in a 5-tuple. The dictionary values are nothing more or less than proofs that the corresponding constraints hold. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Positive integers
Daniel McAllansmith wrote: I can see the domain bounds check would be a problem in theory, but in practice doesn't the type enforce that? Keeping Word positive costs nothing because it just overflows. Wouldn't it be much the same? If you're planning wraparound semantics then you're better off with Int indexes. Passing an index congruent to -1 mod 2^32 is certainly an error, and (!!) may as well fail immediately rather than try to traverse 2^32-1 list nodes. I think both Int and Word are equally correct here, since both are proper supersets of the valid set of indexes. (If you're working with lists so long that Int may not be big enough, you shouldn't trust Word either.) Haskell 98's List module supplies generic versions of the list functions, like genericIndex :: Integral a = [b] - a - b, which will work with Word. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Strict tuples
John Meacham wrote: ghc's strictness analyzer is pretty darn good, If something is subtle enough for the compiler not to catch it, then the programmer probably won't right off the bat either. Even the best strictness analyzer can't determine that a function is strict when it really isn't. The main point of strictness annotations, I think, is to actually change the denotational semantics of the program. strictness does not belong in the type system in general. strictness annotations are attached to the data components and not type components in data declarations because they only affect the desugaring of the constructor, but not the run-time representation or the types in general. attaching strictness info to types is just the wrong thing to do in general I think. Your argument seems circular. Haskell 98 strictness annotations are just sugar, but they didn't *have* to be. You can say that f is strict if f _|_ = _|_, or you can say it's strict if its domain doesn't include _|_ at all. One feels more at home in the value language (seq, ! on constructor fields), the other feels more at home in the type language (! on the left of the function arrow, more generally ! on types to mean lack of _|_). -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Strict tuples
Bulat Ziganshin wrote: Taral wrote: T I don't see that more optimization follows from the availability T of information regarding the strictness of a function result's T subcomponents. ghc uses unboxed tuples just for such sort of optimizations. instead of returning possibly-unevaluated pair with possibly-unevaluated elements it just return, say, two doubles in registers - a huge win Mmm, not quite. Unboxed tuples are boxed tuples restricted such that they never have to be stored on the heap, but this has no effect on semantics at all. A function returning (# Double,Double #) may still return two thunks. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
[Haskell-cafe] Re: different code in different platforms
Neil Mitchell wrote: #ifdef __WIN32__ (Windows code) #else (Linux code) #endif In Yhc, we use a runtime test to check between Windows and Linux. I think the cleanest solution is to factor the OS-specific code into separate modules with OS-independent interfaces and names, and pull in the appropriate implementations at compile time by changing the module search path. That way you avoid the syntactic and semantic ugliness of cpp as well as most of the practical problems of a runtime test. You can also use any two or all three of these techniques together. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: how would this be done? type classes? existential types?
Matthias Fischmann wrote: now i want to create a list of a type similar to [r1, r2, r3] :: (Resource a) = [a] but with r1 being pizza, r2 being crude oil, and so on. The type you actually want here is [exists a. (Resource a) a], but no Haskell implementation supports that. data Rs = forall a . (Resource a) = Rs a unRs (Rs a) = a rsName :: Rs - String rsName = resourceName . unRs ... [...] but what is the type of unRs? Its type is (Rs - (exists a. (Resource a) a)), but again no Haskell implementation supports that. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: how would this be done? type classes? existentialtypes?
Matthias Fischmann wrote: is there any difference between these two? if they are equivalent, why the two different ways to say it? data X where X :: (Resource a) = a - X data Y = forall a . (Resource a) = Y a There's no difference. There are two ways to say it for historical reasons. The second notation dates back many years, while the first notation is new and experimental. Only the first notation supports GADTs, and only the second supports deriving declarations and strict fields and record syntax (though I think this is going to change). Also the second notation is more convenient when you're declaring an ordinary datatype---compare data List a = Nil | Cons a (List a) data List a where { Nil :: List a ; Cons :: a - List a - List a } and now it gets interesting: i need instances for Rs on Show, Read, Eq, Ord. Show is very simple, but Read? I think you're right: it's impossible to implement Read for Rs in an extensible way, because there's no way to obtain the necessary Resource dictionary at runtime. I've wished in the past for a family of functions, one for each single-parameter typeclass, with types something like Dynamic - (forall a. C a = a - b) - Maybe b and you'd need something similar here. Assuming this is indeed impossible and you have to close the world of Resources, you may as well do it by writing data Rs = RsRice Rice | RsCrudeOil CrudeOil | ... deriving (Show,Read,Eq,Ord) -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: how would this be done? type classes? existential types?
Matthias Fischmann wrote: On Thu, Mar 16, 2006 at 12:40:00PM +, Chris Kuklewicz wrote: (Why isn't it resourceName :: String ?) when i am trying this, ghc complains that the type of resourceName doesn't have any occurrance of 'a', and i feel that it must be harder for the type engine to figure things out if there isn't, so resourceName is still a mapping from resources to their names. Yes, if you had resourceName :: forall a. Resource a = String then there'd be nothing to prevent the expression (resourceName :: String) from evaluating to any resource name in any context. A trick you can pull is to define data Proxy a = Proxy and give resourceName's parameter the type Proxy a instead of a. This makes it clear that it's only the type you care about, not the value. The downside is that it tends to be less convenient to use, which is presumably why standard library functions with this problem (like floatRadix and sizeOf) don't use this solution. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: small extension to `...` notation
Philippa Cowderoy wrote: On Wed, 8 Mar 2006, Doaitse Swierstra wrote: xs `zipWith (+)` ys There is one problem with this: it doesn't nest [...] Another problem is that it's not clear how to declare the fixity of these things. Should they always have the default fixity? Should they be required to have the form `ident args` and use the fixity of `ident`? Neither approach seems very clean. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: relaxed instance rules spec (was: the MPTC Dilemma (please solve))
John Meacham wrote: On Thu, Mar 02, 2006 at 03:53:45AM -, Claus Reinke wrote: the problem is that we have somehow conjured up an infinite type for Mul to recurse on without end! Normally, such infinite types are ruled out by occurs-checks (unless you are working with Prolog III;-), so someone forgot to do that here. why? where? how? Polymorphic recursion allows the construction of infinite types if I understand what you mean. No, that's different. An infinite type can't be written in (legal) Haskell. It's something like type T = [T] -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
[Haskell-cafe] Re: Layout rule (was Re: PrefixMap: code review request)
I wrote: I just installed Visual Haskell 0.1, and when I type in the editor, CPU usage rises to about 70% and there's a noticeable delay before each character appears on the screen. This is no longer happening, so I guess I ran afoul of a bug. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell] Re: Visual Haskell: Could not find module `Control.Monad.Writer'
Replying to an old thread... Bernd Holzmüller wrote: Could not find module `Control.Monad.Writer': use -v to see a list of the files searched for I just installed Visual Haskell and ran into the same problem, and the solution I found was to right click on References in the project and add the mtl package. I also had to add the haskell98 package to get Happy-produced source code to work (even though Happy was called with --ghc). -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: overlapping instances and constraints
Niklas Broberg wrote: Ben Rudiak-Gould wrote: Are there uses of overlapping instances for which this isn't flexible enough? Certainly! Hmm... well, what about at least permitting intra-module overlap in Haskell' (and in GHC without -foverlapping-instances)? It's good enough for many things, and it's relatively well-behaved. instance (Show a) = IsXML a where toXML = toXML . show The intention of the latter is to be a default instance unless another instance is specified. I can see how this is useful, but I'm surprised that it's robust. None of the extensions people have suggested to avoid overlap would help here, clearly. Are there uses of overlapping instances for which the single-module restriction isn't flexible enough, but extensions that avoid overlap are flexible enough? -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
[Haskell-cafe] Re: Layout rule (was Re: PrefixMap: code review request)
Duncan Coutts wrote: hIDE and Visual Haskell use the ghc lexer and get near-instantaneous syntax highlighting. Hmm... I just installed Visual Haskell 0.1, and when I type in the editor, CPU usage rises to about 70% and there's a noticeable delay before each character appears on the screen. This is a very short module (~100 lines) and a Pentium M 1600 CPU. Am I doing something wrong? -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Layout rule (was Re: PrefixMap: code review request)
Benjamin Franksen wrote: TAB characters in program text should be forbidden by law. Well... they are quite useful for lining things up if you're using a proportional font, and I don't think proportionally-spaced code is a bad idea. I want them to be optional. But it would be nice if parsers would warn about (or even reject) programs whose meaning depends on tab width. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Layout rule
Ketil Malde wrote: Multi line comments are nice for commenting out blocks of code. They're also nice for comments within a line. E.g. haskell-src-exts contains the declaration data HsQualConDecl = HsQualConDecl SrcLoc {- forall -} [HsName] {- . -} HsContext {- = -} HsConDecl Probably half of my uses of {- -} begin and end on the same line. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: PrefixMap: code review request
Brian Hulley wrote: Whoever thought up the original Haskell layout rule assumed that people would be happy using a single fixed width font, tabs set to 8 spaces, and didn't care about the brittleness of the code (in the face of identifier renamings) it allowed one to write. Are you complaining that Haskell permits you to write code with these problems, or that it requires you to? The latter is not true. Instead of keyword clause1 clause2 you can always write keyword clause1 clause2 or keyword { clause1 ; clause2 } Both styles are insensitive to tab width and renaming of identifiers. The off-side rule only comes into play when you don't include an explicit {, so you can suppress it entirely if you prefer. If you have a different layout rule in mind I'd be interested in hearing it, but I think Haskell's is quite good overall. Lisp has similar indentation problems despite the lack of a layout rule, since people commonly write (foo (...) (...)) Renaming foo can't confuse the compiler, but I've never had a Haskell layout error change the meaning of my program. At worst it causes the program to be rejected. I do edit my source code in a fixed-width font, but it's a very pretty font (Bitstream Vera Sans Mono). It's a small price to pay for the convenience of being able to use 2D layout, even in languages where it's not significant, and in comments. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: rounding errors with real numbers.
Henning Thielemann wrote: Maybe you should use a kind of convex combination, that is (x-oldLower)*a + (oldUpper-x)*b Maybe lower*(1-z) + upper*z where z = (x-oldLower) / (oldUpper-oldLower). I think this will always map oldLower and oldUpper to lower and upper exactly, but I'm not sure it's monotonic. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Layout rule (was Re: PrefixMap: code review request)
Brian Hulley wrote: Here is my proposed layout rule: 1) All layout keywords (where, of, let, do) must either be followed by a single element of the corresponding block type, and explicit block introduced by '{', or a layout block whose first line starts on the *next* line I wouldn't have much trouble adapting to that. and whose indentation is accomplished *only* by tabs You can't be serious. This would cause far more problems than the current rule. I would also make it that explicit braces are not allowed to switch off the layout rule (ie they can be used within a layout), I don't understand. What does used within a layout mean? multiline strings would not be permitted, They aren't now, except with \ escapes. A stray will be caught on the same line unless the line happens to end with \ and the next line happens to begin with \, which is exceedingly unusual. and multiline comments would not be permitted (pragmas could easily be used just by using --#) But --# doesn't introduce a comment. And this would make UNPACK pragmas rather inconvenient to use. 1) When you see a ';' you could immediately tell which block it belongs to by looking backwards till the next '{' I guess that might be helpful, but it doesn't seem easier than looking left to the beginning of the current line and then up to the first less-indented line. 2) Variable width fonts can be used, They can be used now, if you adhere to a certain style, but not everyone likes that style. I wrote in C++ with a variable width font and tabs at one time, but eventually went back to fixed width. One reason was that I couldn't use comment layout conventions that tend (in my experience) to improve readability more than monospacing hurts it. Another reason was that glyph widths appropriate to natural languages didn't work all that well for source code. Spaces are much more important in source code than in natural language, for example. A proportional font designed for source code would be nice, but I haven't found one yet. Stroustrup used a mixture of proportional and monospaced glyphs in _The C++ Programming Language_ and it worked well. or different font faces to represent different sorts of identifier eg class names, tycons, value constructors, operators like `seq` as opposed to seq etc Lots of editors do this with monospaced fonts; I think it's orthogonal to the layout issue. 3) Using only tabs ensures that vertical alignment goes to the same position on the screen regardless of the font and tabs could even have different widths just like in a wordprocessor Requiring tabs is a really bad idea. Just forget it. Seriously. 4) Any keypress has a localised effect on the parse tree of the buffer as a whole ( { no longer kill everything which follows and there would be no {- ) I don't understand why this is an advantage. If you have an editor that highlights comments in green, then large sections of the program will flash green while you type a {- -} comment, which might be annoying, but it also means you'll never forget to close the comment, so the practical benefit of forbidding {- -}, as opposed to simply not typing it yourself, seems nil. 5) It paves the way for a much more immersive editing environment, but I can't say more about this at the moment because I haven't finished writing it yet and it will be a commercial product :-))) I guess everything has been leading up to this, but my reaction is that it renders the whole debate irrelevant. The only reason layout exists in the first place is to make source code look good in ordinary text editors. If you have a high-level source code editor that manipulates the AST, then you don't need layout, or tabs, or any of that silly ASCII stuff. The only time you need to worry about layout is when interoperating with implementations that use the concrete syntax, and then there's nothing to stop you from exporting in any style you like. And when importing, there's no reason to place restrictions on Haskell's layout rule, because the visual layout you display in the editor need have no connection to the layout of the imported file. Using my self-imposed layout rule I'm currently editing all my Haskell code in a standard text editor using tabs set to 4 spaces and a variable width font and have no problems. Which is the best argument for keeping the current rule! If it were changed as you propose, then someday Hugh Briley would come along and complain that Haskell's layout syntax squandered screen space---but he *wouldn't* be able to program in his preferred style, because it would no longer be allowed. Religious freedom is a good thing. {- Ben -} ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell] Re: strange behavior of Implicit Parameters
I'd advise against using implicit parameters, because (as you've seen) it's hard to reason about when they'll get passed to functions. Another example: http://www.haskell.org/pipermail/haskell-cafe/2005-January/008571.html -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell-cafe] Re: -fno-monomorphism-restriction makes type-inference ambiguous?
Eike Scholz wrote: mylength = synAttr listLength $ *Main :type synAttr $ synAttr :: (Data b) = ((?stack::[Dyn]) = b - a) - Attr a $ *Main :type listLength $ listLength :: (?stack::[Dyn]) = List - Float $ *Main :type (synAttr listLength) $ (synAttr listLength) :: Attr Float $ *Main :type mylength $ mylength :: (?stack::[Dyn]) = Dyn - Dyn - [Dyn] - Maybe Float where type Attr a = Dyn - Dyn - [Dyn]- Maybe a This may be a bug. But note that both interpretations are legitimate. One way of applying synAttr to listLength is first to apply ?stack to listLength, obtaining listLength' :: List - Float and creating a (?stack::[Dyn]) constraint on the application node, then specializing listLength' to the type (?stack::a) = List - Float, then passing that to synAttr. Again, I recommend that you not try to use implicit parameters. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: inside the GHC code generator
Rene de Visser wrote: Integer is about 30 times slower than it needs to be on GHC if you have over half the values between 2^-31 and 2^31. On i386 can you basically can test the low bit for free (it runs in parallel to the integer add instruction). This would allow only values outside this range to required calling the long integer code. Such an optimization is not easily done in C. Currently GHC defines data Integer = S# Int# | J# Int# ByteArray# So it already avoids using GMP for small integers. There's a will this multiplication overflow primitive, but I'm not sure how it's implemented. I think that changing this to use magic pointers would be pretty easy. You'd need to introduce a new primitive type, say Int31#, and then: 1. anytime you previously constructed a WHNF S# on the heap, make a magic pointer instead 2. anytime you dereference a pointer that might be an S#, check for a magic pointer first. Even if a lot of code needs to be changed, it's straightforward because the changes are local. You're just changing the meaning of a pointer such that there's a statically allocated S# n at address 2n+1. It would also be worth trying this for Char#, which is already a 31-bit type, to see if it would speed up text-processing code. If only simple loops are optimized it will encourage people to always code loops in their haskell rather than perhaps using more appropriate constructs. You could say that about any language. When your code needs to be fast it needs to be fast. I'd rather write ugly Haskell code than ugly C code, if it comes to that. Also take the Maybe data type with Nothing and Just ... or any other datatypes with 0 and 1 variable constructors. Here these could be represent by special values for the 0 variable case and bit marking on the single constructor values. I'm not sure this would help much. Nullary constructors are already allocated statically, so they're already represented by special values. You could check for those values instead of dereferencing the pointer, but in time-critical code the static object will presumably be in L1 cache anyway. I could be wrong of course, and it would be easy enough to extend the Int31# idea to nullary constructors (Int0#). -- Ben ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: inside the GHC code generator
Simon Peyton-Jones wrote: | [...] put a static table in the executable with | information about register and stack usage indexed by procedure return | point, and use that to unwind the stack and find roots. Every accurate garbage collector (including GHC's) uses a technique like this, but the solution is invariably tightly-coupled to the garbage collector, compiler and run-time system. Okay, I don't know what I was thinking when I wrote that no languages that compile via C use compacting collectors, since obviously lots of them do. But they do it by using various hacks to force local heap pointers into locations where the GC can find them. Most of this effort is wasted, because the local variables disappear before the GC runs. What I'm talking about is idiomatic C code which manipulates heap pointers like any other object, and which can be optimized as usual (e.g. holding heap pointers in callee-saved registers across function calls) without causing GC problems. There's no reason in principle that this couldn't be done. -- Ben ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
[Haskell] Re: Compilation of big, static tables
John Meacham wrote: On Thu, Feb 23, 2006 at 10:40:31AM +, Malcolm Wallace wrote: What I would really like is a syntax to statically construct an array, without having to compute it from a list. This is exactly what my ForeignData proposal on the haskell-prime wiki is meant to address [...] though, I only have it specified for creating pointers to data, it wouldn't be much trickier to make it work for haskell unboxed arrays too (though, you can just make a StorableArray out of them easily as stands) What about boxed arrays? A static Array of thunks makes as much sense to me as a static UArray of CInts. This doesn't really feel like an FFI feature. (Not that foreign data wouldn't be useful too.) -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: inside the GHC code generator
[EMAIL PROTECTED] wrote: * multiple results can be returned via C++ paira,b template, if this is efficiently implemented in gcc There's a -freg-struct-return option in 2.x, 3.x and 4.x. I think it's off by default on many architectures. * recursive definitions translated into the for/while loops if possible I think recent versions of GCC do a good job of this. See http://home.in.tum.de/~baueran/thesis/ All of this efficiency stuff aside, there's a big problem you're neglecting: GARBAGE COLLECTION. For a language that allocates as much as Haskell I think a conservative collector is absolutely out of the question, because they can't compact the heap and so allocation becomes very expensive. A copying collector has to be able to walk the stack and find all the roots, and that interacts very badly with optimization. All the languages I've seen that compile via C either aren't garbage collected or use a conservative or reference-count collector. The closest thing I've seen to a solution is the technique used in Urban Boquist's thesis, which is to put a static table in the executable with information about register and stack usage indexed by procedure return point, and use that to unwind the stack and find roots. Some C compilers (including gcc) support debugging of optimized code, so it might be possible to parse the debugging tables and extract this information. As far as I know, no one has ever looked into the feasibility of doing this, which is kind of surprising since root-finding is probably the single biggest obstacle to compiling functional languages via C. -- Ben ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Export lists in modules
Malcolm Wallace wrote: An explicit interface would be useful for many purposes besides machine-checked documentation. For instance, it could be used to eliminate the hs-boot or hi-boot files used by some compilers when dealing with recursive modules. Why *does* ghc require hs-boot files? What can be gleaned from an hs-boot file that couldn't be expressed in the corresponding hs file? For example, why doesn't ghc simply require that at least one module in a recursive group contain an explicit export list mentioning only explicitly typed symbols? -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Capitalized type variables (was Re: Scoped type variables)
I wrote: What I don't like is that given a signature like x :: a - a there's no way to tell, looking at it in isolation, whether a is free or bound in the type. [...] Here's a completely different idea for solving this. It occurs to me that there isn't all that much difference between capitalized and lowercase identifiers in the type language. One set is for type constants and the other for type variables, but one man's variable is another man's constant, as the epigram goes. In Haskell 98 type signatures, the difference between them is precisely that type variables are bound within the type, and type constants are bound in the environment. Maybe scoped type variables should be capitalized. At the usage point this definitely makes sense: you really shouldn't care whether the thing you're pulling in from the environment was bound at the top level or in a nested scope. And implicit quantification does the right thing. As for binding, I suppose the simplest solution would be explicit quantification of the capitalized variables, e.g. f :: forall N. [N] - ... f x = ... or f (x :: exists N. [N]) = ... Really, the latter binding should be in the pattern, not in the type signature, but that's trickier (from a purely syntactic standpoint). What do people think of this? I've never seen anyone suggest capitalized type variables before, but it seems to make sense. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Module System
Simon Marlow wrote: there's a lack of modularity in the current design, such that renaming the root of a module hierarchy requires editing every single source file in the hierarchy. The only good reason for this is the separation between language and implementation. I don't see how this is related to implementation. Surely all the language spec has to say is that the implementation has some unspecified way of finding the code for a module given only its canonical name, along with (if desired) a way of expanding a glob to a list of canonical names. Then the module namespace reform boils down to rules for converting partial names into canonical names. I can't see how any useful functionality in the module system could depend on a particular way of organizing code on disk. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: The worst piece of syntax in Haskell
Ashley Yakeley wrote: foo :: (Monad m) = [m a] - m [a] instance Integral a = Eq (Ratio a) class Monad m = MonadPlus m I think the most consistent (not most convenient!) syntax would be foo :: forall m a. (Monad m) = [m a] - m [a] instance forall a. (Integral a) = Eq (Ratio a) where {...} class MonadPlus m. (Monad m) {...} There's implicit forall quantification in instance declarations. It's currently never necessary to make it explicit because there are never type variables in scope at an instance declaration, but there's no theoretical reason that there couldn't be. There's no implicit quantification in class declarations---if you added a quantifier, it would always introduce exactly the type variables that follow the class name. I think it's better to treat the class itself as the quantifier. (And it's more like existential quantification than universal, hence the instead of =.) As far as syntax goes, I like foo :: forall m a | Monad m. [m a] - m [a] class MonadPlus m | Monad m where {...} but I'm not sure what to do about the instance case, since I agree with the OP that the interesting part ought to come first instead of last. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
[Haskell] Re: IO == ST RealWorld
John Meacham wrote: ST doesn't have exceptions which IO does. It would be no good to make ST pay for the cost of exception handling. GHC handles them behind the scenes (I think?) but in jhc they are explicit and IO is defined as follows: data World__ data IOResult a = FailIO World__ IOError | JustIO World__ a newtype IO a = IO (World__ - IOResult a) Supposing you had data STResult s a where FailIO :: World__ IOWorld__ - IOError - STResult IOWorld__ a JustST :: World__ s - a - STResult s a could static analysis then eliminate the test for FailIO in ST code? It would be pretty cool if the answer was yes, since it would mean that merging IO and ST would be an optimization instead of a pessimization (the test could also be omitted in IO code that uses only the ST subset). In jhc I suppose this would have to happen late in compilation, when you eliminate unused type parameters. Actually, won't the test for FailIO always be eliminated by the existing points-to analysis? -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] Re: Question for the haskell implementors: Arrays, unsafePerformIO, runST
Data.Array.ST has runSTArray :: Ix i = (forall s . ST s (STArray s i e)) - Array i e I think if you can implement that, then all your problems will be solved. -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: ExistentialQuantifier
Ross Paterson wrote: I don't think the original name is inappropriate: the feature described is certainly existential quantification, albeit restricted to alternatives of data definitions. I think that existential quantification should mean, well, existential quantification, in the sense that term is used in logic. I don't like the idea of using it for the feature currently implemented with forall in front of the data constructor, given that these type variables are universally quantified in the data constructor's type. How about changing the name to existential product types or existential tuples? I would even suggest boxed types, but that's already taken. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
[Haskell] compares :: Ord a = a - a - Ordering - Ordering
I just realized that the class Ord should have an additional method: class Eq a = Ord a where compares :: a - a - Ordering - Ordering compares x y d = case compare x y of { EQ - d ; o - o } ... This would make writing Ord instances much easier: instance (Ord a, Ord b, Ord c, Ord d) = Ord (a,b,c,d) where compares (a1,b1,c1,d1) (a2,b2,c2,d2) = compares a1 a2 . compares b1 b2 . compares c1 c2 . compares d1 d2 -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: forall a (Ord a = a- a) - Int is an illegal type???
David Menendez wrote: Ben Rudiak-Gould writes: | forall a. (forall b. Foo a b = a - b) - Int | | is a legal type, for example. Is it? GHCi gives me an error if I try typing a function like that. This works: f :: forall a. (forall b. Foo a b = a - b) - Int f _ = 3 I interpret this type as meaning that you can call the argument provided you can come up with an appropriate b. If you can't come up with one then you can't call the argument, but you can still ignore it and type check. If you had, for example, instance Foo a Char instance Foo a Int then you would be able to use the argument polymorphically at b=Char and b=Int. f = undefined also works if you have instance Foo a b (which is only allowed with -fallow-undecidable-instances). I think it's because of predicativity that it fails without it. Presumably forall a. (Ord a = a- a) - Int could be allowed as well, but if you're called with a = IO () then you can't call your argument, therefore you can never call your argument, therefore it's not a useful type in practice. -- Ben ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
[Haskell-cafe] Re: Matching constructors
Mark T.B. Carroll wrote: Creighton Hogg [EMAIL PROTECTED] writes: data Patootie = Pa Int | Tootie Int and I want to pull out the indices of all elements of a list that have type constructor Tootie, how would I do that? x = [Pa 3, Tootie 5, Pa 7, Tootie 9, Pa 11] y = [ i |Tootie i - x ] z = [ i | i@(Tootie _) - x ] I think this is what the OP wanted: [ i | (i,Tootie _) - zip [0..] x ] -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: forall a (Ord a = a- a) - Int is an illegal type???
Brian Hulley wrote: I'm puzzled why GHC chooses to create illegal types instead of finding the innermost quantification point ie I would think that (Ord a= a-a) - Int should then obviously be shorthand for (forall a. Ord a= a-a) - Int and surely this could easily be implemented by just prepending forall a b c onto any context restricting a b c... (?) I agree that it's strange to add an implicit quantifier and then complain that it's in the wrong place. I suspect Simon would change this behavior if you complained about it. My preferred behavior, though, would be to reject any type that has a forall-less type class constraint anywhere but at the very beginning. I don't think it's a good idea to expand implicit quantification. Also, the rule would not be quite as simple as you make it out to be, since forall a. (forall b. Foo a b = a - b) - Int is a legal type, for example. -- Ben ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: exported pattern matching
Philippa Cowderoy wrote: Myself I'm of the view transformational patterns (as described in http://citeseer.ist.psu.edu/299277.html) are more interesting - I can't help wondering why they were never implemented? Maybe because of tricky semantics. I'm not quite sure what case x of (y,z)!f - ... where f _ = (z,3) should desugar to. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Passing a matrix from C to Haskell
Cyril Schmidt wrote: I was thinking of something like passing the array as Ptr Int#, but how do I fetch the elements that I am interested in? I think you want Ptr CInt and peekElemOff. If the array is declared in C as int a[100][20] and p :: Ptr CInt is a Haskell pointer to it, then a[y][x] can be accessed as peekElemOff p (y * 20 + x). This should be 100% portable. -- Ben ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Restricted Data Types
John Hughes wrote: That means that the Monad class is not allowed to declare return :: a - m a because there's no guarantee that the type m a would be well-formed. The type declared for return has to become return :: wft (m a) = a - m a I'm confused. It seems like the type (a - m a) can't be permitted in any context, because it would make the type system unsound. If so, there's no reason to require the constraint (wft (m a)) to be explicit in the type signature, since you can infer its existence from the body of the type (or the fields of a datatype declaration). Okay, simplify, simplify. How about the following: For every datatype in the program, imagine that there's a class declaration with the same name. In the case of data Maybe a = ... it's class Maybe a where {} In the case of data Ord a = Map a b = ... it's class Ord a = Map a b where {} It's illegal to refer to these classes in the source code; they're only for internal bookkeeping. Now, for every type signature in the program (counting the type signatures of data constructors, though they have a different syntax), for every type application within the type of the form ((tcon|tvar) type+), add a corresponding constraint to the type context. E.g. singleton :: a - Set a becomes (internally) singleton :: (Set a) = a - Set a and fmapM :: (Functor f, Monad m) = (a - m b) - f a - m (f b) becomes fmapM :: (Functor f, Monad m, m b, f a, m (f b), f b) = (a - m b) - f a - m (f b) You also have to do this for the contexts of type constructors, I guess, e.g. data Foo a = Foo (a Int) becomes data (a Int) = Foo a = Foo (a Int). Now you do type inference as normal, dealing with constraints of the form (tvar type+) pretty much like any other constraint. Does that correctly handle every case? -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Scoped type variables
Simon PJ thinks that Haskell' should include scoped type variables, and I tend to agree. But I'm unhappy with one aspect of the way they're implemented in GHC. What I don't like is that given a signature like x :: a - a there's no way to tell, looking at it in isolation, whether a is free or bound in the type. Even looking at the context it can be hard to tell, because GHC's scoping rules for type variables are fairly complicated and subject to change. This situation never arises in the expression language or in Haskell 98's type language, and I don't think it should arise in Haskell at all. What I'd like to propose is that if Haskell' adopts scoped type variables, they work this way instead: 1. Implicit forall-quantification happens if and only if the type does not begin with an explicit forall. GHC almost follows this rule, except that forall. (with no variables listed) doesn't suppress implicit quantification---but Simon informs me that this is a bug that will be fixed. 2. Implicit quantification quantifies over all free variables in the type, thus closing it. GHC's current behavior is to quantify over a type variable iff there isn't a type variable with that name in scope. Some care is needed in the case of class method signatures: (return :: a - m a) is the same as (return :: forall a. a - m a) but not the same as (return :: forall a m. a - m a). On the other hand the practical type of return as a top-level function is (Monad m = a - m a), which is the same as (forall m a. Monad m = a - m a), so this isn't quite an exception depending on how you look at it. I suppose it is a counterexample to my claim that Haskell 98's type language doesn't confuse free and bound variables, though. If rule 2 were accepted into Haskell' and/or GHC, then code which uses implicit quantification and GHC scoped type variables in the same type would have to be changed to explicitly quantify those types; other programs (including all valid Haskell 98 programs) would continue to work unchanged. Note that the signature x :: a, where a refers to a scoped type variable, would have to be changed to x :: forall. a, which is potentially confusable with x :: forall a. a; maybe the syntax forall _. a should be introduced to make this clearer. The cleanest solution would be to abandon implicit quantification, but I don't suppose anyone would go for that. With these two rules in effect, there's a pretty good case for adopting rule 3: 3. Every type signature brings all its bound type variables into scope. Currently GHC has fairly complicated rules regarding what gets placed into scope: e.g. f :: [a] - [a] f = ... brings nothing into scope, f :: forall a. [a] - [a] f = ... brings a into scope, f :: forall a. [a] - [a] (f,g) = ... brings nothing into scope (for reasons explained in [1]), and f :: forall a. (forall b. b - b) - a f = ... brings a but not b into scope. Of course, b doesn't correspond to any type that's accessible in its lexical scope, but that doesn't matter; it's probably better that attempting to use b fail with a not available here error message than that it fail with a no such type variable message, or succeed and pull in another b from an enclosing scope. There are some interesting corner cases. For example, rank-3 types: f :: ((forall a. a - X) - Y) - Z f g = g (\x - exp) should a denote x's type within exp? It's a bit strange if it does, since the internal System F type variable that a refers to isn't bound in the same place as a itself. It's also a bit strange if it doesn't, since the identification is unambiguous. What about shadowing within a type: f :: forall a. (forall a. a - a) - a I can't see any reason to allow such expressions in the first place. What about type synonyms with bound variables? Probably they should be alpha-renamed into something inaccessible. It seems too confusing to bring them into scope, especially since they may belong to another module and this would introduce a new notion of exporting type variables. I like rule 3 because of its simplicity, but a rule that, say, brought only rank-1 explicitly quantified type variables into scope would probably be good enough. Rules 1 and 2 seem more important. I feel like a new language standard should specify something cleaner and more orthogonal than GHC's current system. -- Ben [1]http://www.mail-archive.com/glasgow-haskell-users@haskell.org/msg09117.html ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Java-like
Bulat Ziganshin wrote: {-# OPTIONS_GHC -fglasgow-exts #-} main = do return xx = ((\x - print x) :: Show a = a - IO ()) main2 = do return xx = (\(x:: (forall a . (Show a) = a)) - print x) main3 = do (x :: forall a . Show a = a) - return xx print x in this module, only main compiles ok The other two need exists rather than forall, which isn't supported by GHC. As written, they say that x can produce a value of any type that's an instance of Show, but the value you're binding to x has type String, which can only produce a value via Show String. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Restricted Data Types
Simon Peyton-Jones wrote: Another reasonable alternative is data Set a = Eq a = Set (List a) The type of member would become member :: a - Set a - Bool (with no Eq constraint). John Hughes mentions this in section 5.2 of the paper, and points out a problem: a function like (singleton :: a - Set a) would have to construct a dictionary out of nowhere. I think you need an Eq constraint on singleton, which means that you still can't make Set an instance of Monad. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
[Haskell-cafe] Re: extending bang proposal Re: strict Haskell dialect
Brian Hulley wrote: One motivation seems to be that in the absence of whole program optimization, the strictness annotations on a function's type can allow the compiler to avoid creating thunks at the call site for cross-module calls whereas using seq in the function body itself means that the thunk still has to be created at the call site because the compiler can't possibly know that it's going to be immediately evaluated by seq. GHC solves this with the worker-wrapper transformation: the code for the wrapper is exported as part of the module's interface and inlined at external call sites. It handles seq, unboxing, and so on and calls the worker via a private interface. Not that I think strictness information in the type system is a bad idea. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Bang patterns
Pursuant to a recent conversation with Simon, my previous post to this thread is now obsolete. So please ignore it, and see the updated wiki page instead. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Restricted Data Types
Jim Apple wrote: Have we considered Restricted Data Types? http://www.cs.chalmers.se/~rjmh/Papers/restricted-datatypes.ps I'd never seen this paper before. This would be a really nice extension to have. The dictionary wrangling looks nasty, but I think it would be easy to implement it in jhc. John, how about coding us up a prototype? :-) -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
[Haskell-cafe] Re: extending bang proposal Re: strict Haskell dialect
Bulat Ziganshin wrote: Hello Ketil, KM (Is the second ! actually meaningful?) yes! it means that the function is strict in its result - i.e. can't return undefined value when strict arguments are given. Unfortunately this interpretation runs pretty quickly into theoretical difficulties. A ! on the right hand side of a function arrow isn't like a ! on the left hand side. If you used this notation for this purpose, it would have to be special-cased. Note that in GHC at present, a function of type Int# - Int# can diverge. KM foo :: [!a] - ![a] - a ![a] means strict list, it is the same as defining list with next field strict: data List2 a = Nil2 | List2 a !(List2 a) This isn't consistent with the general rule that ! means absence of _|_. The semantics that you want could be implemented as a special case for the [] constructor, but polymorphism breaks this, e.g. data Foo a = MkFoo Int !a data Bar a = MkFoo Int a Foo [Bool] /= Bar ![Bool] for example, the following definition type Map a b = [(a,b)] will be instantiated to Map !Int String == [(!Int, String)] As long as you're only specializing datatypes this works fine, but when you try to do the same with polymorphic functions acting on those datatypes, you run into serious problems. E.g. f :: forall a. a - Maybe a f _ = Just undefined Now we have (f :: Int - Maybe Int) 3 == Just _|_, but (f :: !Int - Maybe !Int) 3 == _|_. This means that either f and all of its callers must be specialized at compile time (despite having no type class constraints) or f must inspect its implicit type argument at run time. such proposal already exists and supported by implementing this in GHC HEAD As Robert Dockins said, it's not implemented, and it isn't clear how to implement it. At this point it's looking fairly likely that my PhD thesis will be on this very topic, so stay tuned. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: FilePath as ADT
Marcin 'Qrczak' Kowalczyk wrote: Encouraged by Mono, for my language Kogut I adopted a hack that Unicode people hate: the possibility to use a modified UTF-8 variant where byte sequences which are illegal in UTF-8 are decoded into U+ followed by another character. I don't like the idea of using U+, because it looks like an ASCII control character, and in any case has a long tradition of being used for something else. Why not use a code point that can't result from decoding a valid UTF-8 string? U+ (EF BF BF) is illegal in UTF-8, for example, and I don't think it's legal UTF-16 either. This would give you round-tripping for all legal UTF-8 and UTF-16 strings. Or you could use values from U+DC00 to U+DFFF, which definitely aren't legal UTF-8 or UTF-16. There's plenty of room there to encode each invalid UTF-8 byte in a single word, instead of a sequence of two words. A much cleaner solution would be to reserve part of the private use area, say U+109780 through U+1097FF (DBE5 DF80 through DBE5 DFFF). There's a pretty good chance you won't collide with anyone. It's too bad Unicode hasn't set aside 128 code points for this purpose. Maybe we should grab some unassigned code points, document them, and hope it catches on. There's a lot to be said for any encoding, however nasty, that at least takes ASCII to ASCII. Often people just want to inspect the ASCII portions of a string while leaving the rest untouched (e.g. when parsing --output-file=¡£ª±ïñ¹!.txt), and any encoding that permits this is good enough. Alternatives were: * Use byte strings and character strings in different places, sometimes using a different type depending on the OS (Windows filenames would be character strings). * Fail when encountering byte strings which can't be decoded. Another alternative is to simulate the existence of a UTF-8 locale on Win32. Represent filenames as byte strings on both platforms; on NT convert between UTF-8 and UTF-16 when interfacing with the outside; on 9x either use the ANSI/OEM encoding internally or convert between UTF-8 and the ANSI/OEM encoding. I suppose NT probably doesn't check that the filenames you pass to the kernel are valid UTF-16, so there's some possibility that files with illegal names might be accessible to other applications but not to Haskell applications. But I imagine such files are much rarer than Unix filenames that aren't legal in the current locale. And you could still use the private-encoding trick if not. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
[Haskell-cafe] Re: Why is $ right associative instead ofleftassociative?
Paul Hudak wrote: Minor point, perhaps, but I should mention that : is not special syntax -- it is a perfectly valid infix constructor. But Haskell 98 does treat it specially: you can't import Prelude hiding ((:)), or rebind it locally, or refer to it as Prelude.:. In fact I've always wondered why it was done this way. Can anyone enlighten me? Of course it might be confusing if it were rebound locally, but no more confusing than the fact that [f x | x - xs] is not the same as (map f xs). It might be kind of nice if the list type were actually defined in the Prelude as data List a = Nil | a : List a and all of the special [] syntax defined by a desugaring to this (entirely ordinary) datatype, e.g. [1,2] - 1 Prelude.: 2 Prelude.: Prelude.Nil. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why is $ right associative instead of leftassociative?
Tomasz Zielonka wrote: On Sun, Feb 05, 2006 at 01:14:42PM -, Brian Hulley wrote: How about: f x y . g x $ z But then you have a problem when you when you want to add something at the beginning ;-) How about: id . f x y . g x $ z -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: strict Haskell dialect
Chris Kuklewicz wrote: Weak uses seq to achieve WHNF for it's argument newtype Weak a = WeakCon {runWeak :: a} mkWeak x = seq x (WeakCon x) unsafeMkWeak x = WeakCon x This doesn't actually do what you think it does. mkWeak and unsafeMkWeak are the same function. mkWeak 123 = seq 123 (WeakCon 123) = WeakCon 123 unsafeMkWeak 123 = WeakCon 123 mkWeak _|_ = seq _|_ (WeakCon _|_) = _|_ unsafeMkWeak _|_ = WeakCon _|_ = _|_ To quote John Meacham: | A quick note, | x `seq` x | is always exactly equivalant to x. the reason being that your seq | would never be called to force x unless x was needed anyway. | | I only mention it because for some reason this realization did not hit | me for a long time and once it did a zen-like understanding of seq | (relative to the random placement and guessing method I had used | previously) suddenly was bestowed upon me. I remember this anecdote because when I first read it, a zen-like understanding of seq suddenly was bestowed upon /me/. Maybe it should be in the docs. :-) -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
[Haskell-cafe] Re: strict Haskell dialect
Chris Kuklewicz wrote: Weak uses seq to achieve WHNF for it's argument newtype Weak a = WeakCon {runWeak :: a} mkWeak x = seq x (WeakCon x) unsafeMkWeak x = WeakCon x This doesn't actually do what you think it does. mkWeak and unsafeMkWeak are the same function. mkWeak 123 = seq 123 (WeakCon 123) = WeakCon 123 unsafeMkWeak 123 = WeakCon 123 mkWeak _|_ = seq _|_ (WeakCon _|_) = _|_ unsafeMkWeak _|_ = WeakCon _|_ = _|_ To quote John Meacham: | A quick note, | x `seq` x | is always exactly equivalant to x. the reason being that your seq | would never be called to force x unless x was needed anyway. | | I only mention it because for some reason this realization did not hit | me for a long time and once it did a zen-like understanding of seq | (relative to the random placement and guessing method I had used | previously) suddenly was bestowed upon me. I remember this anecdote because when I first read it, a zen-like understanding of seq suddenly was bestowed upon /me/. Maybe it should be in the docs. :-) -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why is $ right associative instead of left associative?
No one has mentioned yet that it's easy to change the associativity of $ within a module in Haskell 98: import Prelude hiding (($)) infixl 0 $ f$x = f x or, for the purists, import Prelude hiding (($)) import qualified Prelude (($)) infixl 0 $ ($) = (Prelude.$) -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: The dreaded M-R
John Meacham wrote: interestingly enough, the monomorphism restriction in jhc actually should apply to all polymorphic values, independently of the type class system. x :: a x = x will transform into something that takes a type parameter and is hence not shared. Interesting. I'd been wondering how you dealt with this case, and now it turns out that you don't. :-) I doubt this will cause a problem in practice since there arn't really any useful values of type forall a . a other than bottom. It could become an issue with something like churchNumerals :: [(a - a) - (a - a)] churchNumerals = ... Maybe you could use a worker-wrapper transformation. churchNumerals' :: [(T - T) - (T - T)] churchNumerals' = ... churchNumerals :: [(a - a) - (a - a)] churchNumerals = /\ a . unsafeCoerce churchNumerals' The unsafeCoerce is scary, but it feels right to me. There is something genuinely unsavory about this kind of sharing, in Haskell or any other ML dialect. At least here it's out in the open. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: [Haskell] IO == ST RealWorld
Ross Paterson wrote: But IO isn't a state monad: others are concurrently changing the world without waiting for my Haskell program to terminate. I think that closed-world behavior should be treated as a property of runST, not of the ST monad operations. Otherwise your IORef = STRef IORegion proposal doesn't work either, because e.g. myId :: STRef s a - a - ST s a myId r x = writeSTRef r x readSTRef r doesn't necessarily return its second argument when lifted to IO, in the presence of multithreading. This philosophical objection to IO = ST IORegion has come up before, and I think it's approaching the problem exactly backwards. If IO = ST IORegion works in practice and is useful in practice, then we ought to be coming up with a theory of IO/ST that supports it, not rejecting it on the basis of a theory that doesn't support it. -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Guess what ... Tutorial uploaded! :)
Dmitry Astapov wrote: http://www.haskell.org/hawiki/HitchhickersGuideToTheHaskell I like the approach too, but the section on IO actions, which I'm reading now, is not correct. It's not true that a - someAction has the effect of associating a with someAction, with the actual work deferred until later. All of the IO associated with someAction happens at the program point where a - someAction appears, whether or not it's needed later. getContents is a rare exception to this rule. It works by using unsafeInterleaveIO behind the scenes, which muddies Haskell's generally clean semantics and leads to odd impure behavior. I wish getContents were a good example of nonstrictness or laziness, but I don't think it is. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Shootout favouring C
Isaac Gouy wrote: Please keep to the true spirit of fictional crime writing and provide a motive for these evil characters who will stop at nothing to make Haskell seem some worse than C. Erm, fictional? It strikes me that this particular brand of evil is more the norm than the exception. I think Bjarne Stroustrup put it quite well: http://public.research.att.com/~bs/bs_faq.html#compare That said, I see nothing to suggest that such is happening here. I do have objections to the shootout, but they're objections to the whole concept of benchmarks in general, not to these particular ones. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Existentially-quantified constructors, Eq and Show
John Meacham wrote: PS. many, including me, feel 'forall' is a misnomer there and should be the keyword 'exists' instead. so just read 'foralls' that come _before_ the type name as 'exists' in your head and it will make more sense. I disagree. When you write forall a. D (P a) (Q a) it means that there's a variant of D for all types a. It's as though you had D (P Bool) (Q Bool) | D (P String) (Q String) | ... Writing exists instead would mean that there's only one version of D for some a, and you don't know what that a is; in that case you could only safely apply D to arguments of type (forall b. P b) and (forall b. Q b). I think the problem is not with the use of forall, but with the use of the term existential type. The fact that existential quantification shows up in discussions of this language extension is a red herring. Even Haskell 98 has existential types in this sense, since (forall a. ([a] - Int)) and ((exists a. [a]) - Int) are isomorphic. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Two questions: lazy evaluation and Church-Rosser
Gregory Woodhouse wrote: I've been trying to do some background reading on lambda calculus, and have found discussions of strict evaluation strategies (call-by-value and call-by-name) but have yet to find an appropriate framework for modeling lazy evaluation Just wanted to point out that call-by-name is non-strict. Lazy evaluation is basically just call-by-name with extra sharing; if you only care about semantics and not time/space behavior, it's the same as call-by-name. (much less infinite lists and comprehensions). In a lazy or call-by-name operational semantics, you never get infinite lists, just lists with unevaluated tails which get unwrapped as needed. List comprehensions in Haskell are syntactic sugar. The Haskell 98 report explains how to transform them away. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Monads vs. continuations
I don't know if this helps, but there's a straightforward way to understand the IO monad in terms of continuation passing. You can think of a value of type IO a as being a CPS expression with a hole in it; the hole is to be filled with a continuation which expects a value of type a. The only way to fill the hole is by using =, whose second argument is a continuation with another (nested) hole in it. So effectively with = you build a CPS expression from the outside in. The final continuation, which takes () and aborts the program, is ultimately filled in by the runtime system. This viewpoint doesn't work for other monads, since they always provide some sort of destructuring operations on monadic values, e.g. runState or the standard list deconstructors. But it works fine for IO provided you ignore the existence of unsafePerformIO and friends. -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] newtype is superfluous
Wolfgang Jeltsch wrote: This is not true. With newtype, A _|_ is _|_, with data, A _|_ is not _|_. It's probably more helpful to explain this in terms of a program that exhibits different behavior in the two cases: case error data of A x - newtype But as far as I know, the above newtype declaration is equivalent to this: data A = A !Int Nope: case A (error data!) of A x - data or newtype -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question on Haskell type
Cale Gibbard wrote: As an example of this sort of thing, I know that there are only 4 values of type a - Bool (without the class context). They are the constant functions (\x - True), (\x - False), and two kinds of failure (\x - _|_), and _|_, where _|_ is pronounced bottom and represents something along the lines of nontermination (aborting the program also counts). Don't forget (\x - x `seq` True) and (\x - x `seq` False). -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Growing Trees
[Previously sent only to the OP -- oops] Tom Hawkins wrote: data Tree a = TreeRoot { stuff:: a , children :: [Tree] } | TreeNode { stuff:: a , parent :: Tree , children :: [Tree] } But because of these bidirectional links, every time I add a node I must reconstructing the entire tree. If you don't want to use IORefs or STRefs, you could try The Zipper: http://www.haskell.org/hawiki/TheZipper or you could represent the tree as type Tree a = Data.Map.Map Int (Node a) data Node a = TreeRoot { stuff :: a, children :: [Int] } | TreeNode { stuff :: a, parent :: Int, children :: [Int] } -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Mixing monadic and non-monadic functions
Bjorn Lisper wrote: However, there is a way to resolve the ambiguity that can be claimed to be the most natural one, and that is to always choose the least possible lifting. In the example above, this would mean to interpret [[1]]++[[2]] precisely as [[1]]++[[2]] (lift 0 levels) rather than [[1]++[2]] (lift 1 level). It's not the mathematics I'm worried about, it's the people. Consider the time flies like an arrow; fruit flies like a banana example. What's interesting about it is not just the existence of more than one parse, but the fact that it's hard to even notice the other parses exist unless you're looking for them, because people are so good at unconsciously resolving this kind of ambiguity from context. I'm afraid that once people get used to the idea that they can write xs `op` ys and get implicit lifting, they will write xs ++ ys and never notice that it has an unlifted interpretation which will take precedence. This isn't the nastiest class of bug, but it's pretty nasty. -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Mixing monadic and non-monadic functions
Frederik Eaton wrote: I think this is a good idea. I like the inline -, or maybe something like @. The operator-section notation (- expr) has the big advantage of being unlikely to collide with any other syntax proposals. I'm not sure what you intend to do about nested do statements, though. If they correspond to different monads, I might want to have a 'borrow' in the inner do statement create a lifted expression in the outer do statement. In such cases you almost certainly wouldn't want to use this notation anyway. It's confusing enough with a single monad. As an experiment I tried rewriting some monadic code from one of my projects (Reform) using the (- expr) syntax. It was interesting. Some points: * Most of my uses of - could be replaced with the inline form. In some cases it seemed like a bad idea, because the intermediate variable name was useful as documentation. In the other cases I'd obviously chosen a meaningless intermediate variable name just to get around the lack of a feature like this one. * I found myself writing do return a lot, which isn't a combination you usually see in Haskell code. It felt odd, but perhaps you'd get used to it. * The new syntax is really nice as a replacement for the annoyingly common x - foo ; case x of... idiom that I've always disliked. * The increased similarity to programming in an eager language was startling at times. I'm just not used to thinking eagerly when I write Haskell, even though I do it all the time in other languages. * There are tricky corner cases. For example, x - getByte if x 128 then return x else return (x - 128) * 256 + (- getByte) doesn't do what it's probably intended to do: the second byte will be read even if x 128. You have to write else do return instead of else return. I'm afraid this would be easy to get wrong. It wouldn't be hard to make the translation assume an implicit do at the branches of if and case statements, but this wouldn't always be what you'd want. Even worse is that short- circuiting and || don't work as they do in eager languages. So on reflection I'm not sure I think this proposal is a good idea. I probably wouldn't be able to write or read code in this style without doing manual desugaring in my head, which takes away much of the appeal. But it might be worth adding if people can be trusted to use it judiciously. -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Mixing monadic and non-monadic functions
Frederik Eaton wrote: I want the type system to be able to do automatic lifting of monads, i.e., since [] is a monad, I should be able to write the following: [1,2]+[3,4] and have it interpreted as do {a-[1,2]; b-[3,4]; return (a+b)}. The main problem is ambiguity: [[1]]++[[2]] could be [[1],[2]] or [[1,2]], for example. If your proposal resolves this ambiguity in favor of one result or the other, then I'm opposed to it -- it's far too easy in practice to write code like this, expecting it to be lifted, and failing to notice that it also has an interpretation without lifting (or the other way around). This is the Perl FWIM disease[1] -- not that I dislike Perl, but people are quite rightly leery about bringing this sort of thing into Haskell. I have another proposal, though. Introduce a new keyword, which I'll call borrow (the opposite of return), that behaves like a function of type (Monad m) = m a - a inside of do statements. More precisely, a do expression of the form do { ... ; ... borrow E ... ; ... } is transformed into do { ... ; x - E ; ... x ... ; ... } where x is a fresh variable. If more than one borrow form appears in the same do statement, they are pulled out from left to right, which matches the convention already used in liftM2, ap, mapM, etc. Pros: + Pure sugar; no tricky interactions with the type system. + Nice symmetry between putting a value in a monad and taking it out. + Potentially helpful for beginners who ask how do I get a String from an IO String? Cons: - Needs a new keyword. - Pretends to be an expression but really isn't; perhaps distinctive syntax would be better. (Inline -?) - Depends on enclosing do keyword: in particular, do { stmt } would no longer be equivalent to stmt, if stmt contains borrow. Potential confusion. - Potentially misleading for beginners (but then so is do notation, and the keyword class, and n+k patterns, and so on...) -- Ben [1] http://www.dcs.gla.ac.uk/~partain/haskerl/partain-1.html ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Parity of the number of inversions of a permutation
Henning Thielemann wrote: I' searching for a function which sorts the numbers and determines the parity of the number of inversions. I assume that there are elegant and fast algorithms for this problem (n * log n time steps), e.g. a merge sort algorithm. This is a rather nice little problem. I think this works: countInversions :: (Ord a) = [a] - Int countInversions [] = 0 countInversions xs = snd $ foldb merge [([x],0) | x - xs] merge :: (Ord a) = ([a],Int) - ([a],Int) - ([a],Int) merge (xs,a) (ys,b) = case merge' (length xs) xs ys of (zs,c) - (zs,a+b+c) merge' 0 [] ys = (ys,0) merge' n xs [] = (xs,0) merge' n (x:xs) (y:ys) = case compare x y of LT - case merge' (n-1) xs (y:ys) of (zs,c) - (x:zs,c) GT - case merge' n (x:xs) ys of (zs,c) - (y:zs,c+n) EQ - undefined foldb :: (a - a - a) - [a] - a foldb f [] = undefined foldb f [x] = x foldb f xs = foldb f (foldb' f xs) foldb' f (x1:x2:xs) = f x1 x2 : foldb' f xs foldb' f xs = xs -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Proposal: Allow \= for field update in record update syntax
Benjamin Franksen wrote: On Thursday 24 February 2005 23:27, Keean Schupke wrote: Well, not quite true, because the type of the label is used to index the value, the selection happens at compile time. So at run time there is no instance selection left... it is simply the value. At least in theory! Hmm. I haven't seen it from this perspective, yet! At first reading, I thought this is simply too good to be true. I mean, there is some sort of list structured thing representing the whole record, right? Then how can the function that selects an element *not* traverse through the list? It does. An HList of Int,Bool,Char is isomorphic to the type (Int,(Bool,(Char,(, and selecting the Bool element will ultimately compile to code like this: case list of (_,(x,_)) - ... It doesn't need to search for the right element at runtime, and it doesn't need to check for end-of-list at runtime, but it does need to deconstruct O(n) pairs at runtime. A statically balanced tree structure would reduce that the O(log n), but I doubt it would improve performance for typical record sizes. Of course, inlining may well lead to something like case (a,(b,(c,( of (_,(x,_)) - ... which can be optimized away. -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Type of y f = f . f
Pedro Vasconcelos wrote: Jim Apple [EMAIL PROTECTED] wrote: Is there a type we can give to y f = f . f y id y head y fst are all typeable? Using ghci: Prelude let y f = f.f Prelude :t y y :: forall c. (c - c) - c - c So it admits principal type (a-a) - a-a. From this you can see that (y head) and (y fst) cannot be typed, whereas (y id) can. I think the OP's point is that all three of his examples make sense, and the resulting functions would have Haskell types, yet there doesn't seem to be a Haskell type which permits all three uses of y. I can come up with types which permit any one of the three: y :: forall a. (a - a) - a - a y :: forall a f. (forall x. f x - x) - f (f a) - a y :: forall a b c f. (forall x y. f x y - x) - f (f a b) c - a but I can't find a type which permits more than one. It can probably be done with type classes. -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Typing in haskell and mathematics
Jeremy Gibbons wrote: If you want a b c to mean (a b) (b c) but a + b + c to mean (a + b) + c, you're going to have to treat differently from +, which goes against the spirit of considering them both simply functions. I've wanted to chime in here for a while now. I strongly disagree with the idea that there's something wrong with a b c, in math or in programming languages. Infix operator parsing happens in two independent stages: first operators are grouped according to precedence, and then according to associativity. In the second stage we only consider expressions that look like (e1 `op1` e2 `op2` ... `opn` en), where all operators are in the same precedence class. In most languages this stage looks for three cases: * all operators are left-associative * all operators are right-associative * n==1 and `op1` is nonassociative Now, the first two of these are hacks, when applied to associative operators. A mathematician would never say that a+b+c is shorthand for (a+b)+c -- that smacks of evaluation order. a+b+c is shorthand for parenthesize it however you like, because it *doesn't matter*. It's just a list of things to be added up. This applies equally to a+b-c-d+e, which is a notational abbreviation for a+b+(-c)+(-d)+e. And no mathematician would write a*b/c/d*e. The idea that this would be evaluated from left to right is an error of grade-school students. (Henning Thielemann's paper has an example of this: the student who writes something like 7 * 3 + 1 = 22 / 2 = 11 * 3 + 1 = 34...) Left-associativity and right-associativity are useful hacks, granted -- but then why limit ourselves to foldl1 and foldr1? What about foldl and foldr (specifying a zero element in the infix declaration) or foldc where foldc takes ([EMAIL PROTECTED]@[EMAIL PROTECTED]@[EMAIL PROTECTED]@[EMAIL PROTECTED]) to ((([EMAIL PROTECTED])@([EMAIL PROTECTED]))@(([EMAIL PROTECTED])@([EMAIL PROTECTED])))? This is a better way of parenthesizing `merge`, for example. (=) can't be right-associative and so ends up left-associative, even though that leads to inefficient code. It ought to produce (e1 = (\x1 - e2 x1 = (...))), but we have no way to express that. The following two cases seem much less hacky to me: * all operators are the same and the operator is (declared as) variadic * all operators are (declared as) inequalities (giving (e1 `op1` e2) (e2 `op2` e3) ...) Such operators are commonly seen in mathematics, unlike true left-associative or right-associative operators, which are rare and usually merit a special explanation to avoid confusing the reader. Even the first stage (precedence) is broken in every computer language I've encountered. How should (a .. b * c) group? Clearly it shouldn't -- it should be rejected. But there's no way to do that except to give (..) and (*) equal precedence and opposite associativities. Aside from the fact that that's clearly a hack, I don't see any reason to expect that the graph of operator clashes can be two-colored in general, or that every connected subgraph can sensibly have a single precedence. The problem is the silly imposition of a linear order on precedence classes, a convention which seems to date to the dawn of high-level programming languages, but was never found in mathematics. Even languages which could easily specify a partial order (because they have a fixed set of operators) don't do it. I've never understood why. There's a strong case to be made for getting rid of infix operators entirely (I personally think that complex arithmetic/logical expressions are much more comprehensible in Scheme), but if you're going to have them, variadic operators make more sense than left-associative operators. -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Re: File path programme
Peter Simons wrote: The module currently knows only _relative_ paths. I am still experimenting with absolute paths because I have recently learned that on Windows something like C:foo.txt is actually relative -- not absolute. Very weird. \foo.txt is also relative on Win32. And con.txt is absolute. There also is a function which changes a path specification into its canonic form, meaning that all redundant segments are stripped. So although two paths which designate the same target may not be equal, they can be tested for equivalence. Again, while this transformation may be useful in some cases, it is not a canonicalization operation. foo/../bar and bar do not in general refer to the same file, and foo and foo/. are not in general equivalent. We shouldn't encourage these misconceptions in the library, even if we do provide a path-collapsing transformation along these lines. Other comments: The Read and Show instances aren't inverses of each other. I don't think we should be using Read for path parsing, for this reason. I don't understand why the path ADT is parameterized by segment representation, but then the Posix and Windows parameter types are both wrappers for String. It seems artificial to distinguish read :: String - RelPath Windows from read :: String - RelPath Posix in this way. In general, this library doesn't seem to deal with any of the hard cases. The devil's in the details. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] space behaviour of lazy recursive lists
Axel Jantsch wrote: Consider: gibs = 1 : 1 : (zipWith f gibs (tail gibs)) where f x y = min (x + y) 10 [...] how can I force the garbage collector to reclaim the memory of the head of the list after I have processed it, since I will never ever reference it again? There's no entirely satisfactory way to do this. The language standard doesn't specify caching behavior, so you have to rely on the way that actual implementations handle caching. I think it's safe in practice to assume that a binding inside a function won't be cached across call boundaries, even if the value of the binding doesn't depend on the function argument. I.e. you should be able to solve your problem with makeGibs () = gibs where gibs = 1 : 1 : (zipWith f gibs (tail gibs)) f x y = min (x + y) 10 In principle a compiler could float the definition of gibs outside the function makeGibs and cache it across calls, but I don't think any compiler will actually do this, precisely because it makes this trick stop working. A more elegant variation which definitely won't be cached is gibsFrom a b = gibs where gibs = a : b : (zipWith f gibs (tail gibs)) f x y = min (x + y) 10 -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] The Nature of Char and String
John Goerzen wrote: Char in Haskell represents a Unicode character. I don't know exactly what its size is, but it must be at least 16 bits and maybe more. String would then share those properties. However, usually I'm accustomed to dealing with data in 8-bit words. So I have some questions: Char and String handling in Haskell is deeply broken. There's a discussion ongoing on this very list about fixing it (in the context of pathnames). But for now, Haskell's Char behaves like C's char with respect to I/O. This is unlikely ever to change (in the existing I/O interface) because it would break too much code. So the answers to your questions are: * If I use hPutStr on a string, is it guaranteed that the number of 8-bit bytes written equals (length stringWritten)? Yes, if the handle is opened in binary mode. No if not. + If yes, what happens to the upper 8 bits? Are they simply stripped off? Yes. * If I run hGetChar, is it possible that it would consume more than one byte of input? No in binary mode, yes in text mode. * Does Haskell treat the this is a Unicode file marker special in any way? No. * Same questions on withCString and related String-CString conversions. They all behave as if reading/writing a file in binary mode. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] File path programme
robert dockins wrote: After the discussion about file paths over the last several days I went home and put together a quick trial implementation for unix file paths, with the idea of adding windows, SMB and maybe VMS (why not?) paths. This is great. Comments below. data PathRoot = UnixFilesystemRoot | WindowsDrive Char | SMBShare String String | VMSDevice String | ... -- whatever else we need I would say that all paths are relative to something, whether it's the Unix root, or the current directory, or whatever. Therefore I would call this something like PathStart, and add: | CurrentDirectory | CurrentDirectoryOfWindowsDrive Char | RootOfCurrentWindowsDrive What is a pathname, broadly speaking? Answer: it's a description of a path in a directed graph with labeled edges. It consists of a single node designator (the starting point) and a sequence of edge designators, i.e. data Pathname = Pathname { pathStart :: PathStart, pathEdges :: [String] } Most of the time all we care about is either the final node or the final edge that we reach by following the path. The only reason we specify the rest of the path is that there are only a few nodes that we can name directly; to refer to any other location on the graph we have to give driving directions from one of those nodes. There's no reason the OS couldn't make nodes and edges first-class entities--it would solve a multitude of problems--but most don't, so forget that. On Unix, there are two nodes we can name directly, the root and the current directory. On Windows, there are 26 roots and 26 current directories which we can name directly; additionally we can name the root or current directory of the current drive, which is one of those 26, and there are an arbitrary number of network share roots, and \\.\, and perhaps some other stuff I don't know about. Symbolic links complicate things a bit, since they are followed like edges but are actually paths (so they may be affected by seemingly unrelated changes to the graph). They're rather like VPNs, actually, though I'm not sure how far I want to push that analogy. Whether we're talking about the final node or the final edge depends on the OS call; this is the usual pointer-vs-pointee confusion that's also found in most programming languages outside the ML family. Probably we can ignore it, with the exception of the /foo vs /foo/ distinction, which we must preserve. This can probably be handled by parsing the latter as Pathname { pathStart = UnixFilesystemRoot, pathEdges = [foo,.] }. class (Show p) = Path p where Okay, I'm not convinced that a Path class is the right approach. For the reasons given above, I think I'd rather have a single Path datatype, probably with its data constructors exported. What do we gain with the class approach? Well... (A) Functions that accept paths can be polymorphic on the path type (where String is a path type). (B) We can have different datatypes for the paths of different operating systems. It seems like these are two very different problems which should be solved with different typeclasses, if they're to be solved with typeclasses at all. I think (A) can be solved very simply, and independently of the specification of a path-handling library: class IsPath a where withCPath :: a - (Ptr CChar - IO b) - IO b instance IsPath String where withCPath = withCString -- tricky i18n issues! instance IsPath [CChar] where withCPath = withArray0 0 instance IsPath PathADT where withCPath = withCString . pathToString instance IsPath (Ptr CChar) where withCPath = flip ($) openFile :: (IsPath p) = p - ... I'm tentatively opposed to (B), since I think that the only interesting difference between Win32 and Posix paths is in the set of starting points you can name. (The path separator isn't very interesting.) But maybe it does make sense to have separate starting-point ADTs for each operating system. Then of course there's the issue that Win32 edge labels are Unicode, while Posix edge labels are [Word8]. Hmm. isAbsolute :: p - Bool Definition: a path is absolute if its meaning is independent of (Posix: the current directory) (Win32: all current directories and the current drive). pathCleanup :: p - p -- remove .. and suchlike This can't be done safely except in a few special cases (e.g. /.. - /). I'm not sure it should be here. hasExtension :: p - String - Bool This is really an operation on a single component of the path. I think it would make more sense to make it an ordinary function with type String - String - Bool and use the basename method to get the appropriate path component. pathToForeign :: p - IO (Ptr CChar) pathFromForeign :: Ptr CChar - IO p This interface is problematic. Is the pointer returned by pathToForeign a heap pointer which the caller is supposed to free? If so, a Ptr CChar instance would have to
Re: [Haskell-cafe] Haskell programs in C
Mark Carroll wrote: Wasn't there someone mentioning here a little while ago some project where they strip most of System.* from the libraries and get something that might be suitable for embedded applications? What was that called? Anyone remember? hOp: http://www.macs.hw.ac.uk/~sebc/hOp/ -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] File path programme
Jules Bean wrote: [...] it is an extension of the notion that /foo/ and /foo refer to the same directory. (Except, apparently, in the presence of symbolic links... or so I have some vague memory) Yes, /foo/ is equivalent to /foo/., which is not always the same as /foo. If /foo is a symlink, then lstat(/foo/, ...) will stat the directory at the other end, not the symlink. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] File path programme
Isaac Jones wrote: You might be interested in the new FilePath module that's in the works. There's been a lot of work to make these functions portable. http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/libraries/base/System/FilePath.hs I didn't realize this was in CVS. IMHO this library is deeply broken, and should not be in GHC 6.4. We should be replacing ill-specified hacks with a carefully designed library, not an official collection of ill-specified hacks. It took me only a few minutes to find a bunch of cases which the CVS code mishandles, ranging from simple bugs, to cases where the existing behavior might be okay if documented, to cases where I'm not convinced there's any sensible behavior consistent with the function's type. (Win32) splitFileName server\\share == (server,share) (should probably be (server\\share,)) splitFileName foo:xyz == (foo:.,xyz) (should be (.,foo:xyz) -- this refers to the named stream xyz of foo) joinPaths c:\\ \\foo == \\foo (should be c:\\foo. I realize that cd c:\\ on Windows doesn't actually make c:\\ the current directory, but ; doesn't separate shell commands either.) (Posix) splitFileName /foo == (/,foo), splitFileName /foo/ == (/foo,) (arguably makes sense, but why isn't it documented?) splitFileName /foo/bar == (/foo,bar) splitFileName /foo//bar == (/foo/,bar) (definitely a bug) pathParents /foo///bar == [/,/foo,/foo,/foo,/foo/bar] pathParents foo/../bar == [.,foo/../bar] (what if foo doesn't exist and we wanted to create it?) Add to those the fundamental problems with splitFileExt which were already mentioned on this thread. I don't even think the broad approach taken by the library interface is right. Manipulating pathnames with FilePath-FilePath functions is like refactoring a Haskell module with String-String functions. There should be parsing and serialization functions which convert between the external FilePath representation and an internal ADT, and the manipulation should happen on the ADT. Please, let's not ship this with the hierarchical libraries. It's not ready for prime time. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Top Level etc.
Jim Apple wrote: Does anyone have examples of these? This one scares the foo out of me: * It's not even safe in general to add a signature giving the same type that the compiler would infer anyway Here's an example: len :: [a] - Int len xs = let ?accum = 0 in len' xs len' [] = ?accum len' (x:xs) = let ?accum = ?accum + (1::Int) in len' xs *Main :t len' len' :: forall a. (?accum :: Int) = [a] - Int *Main len hello 0 len :: [a] - Int len xs = let ?accum = 0 in len' xs len' :: forall a. (?accum :: Int) = [a] - Int len' [] = ?accum len' (x:xs) = let ?accum = ?accum + (1::Int) in len' xs *Main :t len' len' :: forall a. (?accum :: Int) = [a] - Int *Main len hello 5 This happens as a side effect of the way that type inference currently works on recursive binding groups. It happens with typeclass dictionaries too, but it isn't observable because they can't be rebound in a local scope. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
Glynn Clements wrote: Keean Schupke wrote: Why is disk a special case? With slow streams, where there may be an indefinite delay before the data is available, you can use non-blocking I/O, asynchronous I/O, select(), poll() etc to determine if the data is available. [...] With files or block devices, the data is always deemed to be available, even if the data isn't in physical memory. I don't think this really captures the reason for the difference. It's not that select chooses not to do anything on the assumption that file access is fast. It's that it /can't/ do anything, because (drum roll) disk files are totally different from streams. The data you read from an input stream is being actively written by someone else. As the producer keeps writing, data will end up buffered in local memory until you read it. select() tells you when there's buffered data to read. If you're reading from a random-access file, there's no way it can tell you when the file data is buffered, because it doesn't know which part of the file you plan to read. The OS may try to guess for readahead purposes, but select()'s behavior can't depend on that guess. If streams were distinguished from random-access files at the OS level, the situation would be different. The fact that you create an input stream on top of a disk file indicates to the OS that you plan to read the file sequentially from that point. It's natural to use the same buffering model that's used for sockets, and select() can tell you when that buffer is non-empty. This is just like readahead, except predictable and under app control to some extent. Since you can create an arbitrary number of streams on a file, this mechanism provides all the functionality of NT's overlapped I/O model and quite a bit more. This is another example of why the world would be better off with the file/stream model. Have I convinced anyone? -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: Why is getArgs in the IO monad?
Conal Elliott wrote: The meaning of length getArgs would then have to be a value whose type is the meaning of Haskell's Int, i.e. either bottom or a 32-bit integer. I'm guessing that none of those 2^32+1 values is what you'd mean by length getArgs. On the other hand, the IO monad is a much roomier type. I'm not strongly convinced by this argument. I don't think you can tell me which particular Char value you mean by the expression (maxBound :: Char) either, yet you probably wouldn't argue for changing maxBound's type. I think Jim's claim is that there's no clear dividing line between these cases, and I tend to agree. Even if you want to disallow explicit recompilation (and how do you define compilation denotationally?), an automatic rollout of a new version of Hugs could lead to successive invocations of a script using different values of (maxBound :: Char) (or, more plausibly, some constant defined in the library) without user intervention. How is this different from any other environmental change, such as a change in the program arguments? I think this is what Jim meant when he wrote It seems that, looking out at the world from main, the args passed to main and the compilation happen at the same time (before, long long ago). What motivation would we have for treating them differently? -- Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Re: Hugs vs GHC (again)was: Re: Somerandomnewbiequestions
John Meacham wrote: Actually, If I were writing new haskell libraries, I would use mmap whenever I could for accessing files. not only does it make the file pointer problem go away, but it can be drastically more efficient. I'm not sure this is a good idea, because GHC really needs non-blocking I/O to support its thread model, and memory-mapped I/O always blocks. In fact this is a problem even if we only memory-map files at the programmer's request. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] I/O interface
Marcin 'Qrczak' Kowalczyk wrote: Convenience. I'm worried that it uses separate types for various kinds of streams: files, pipes, arrays (private memory), and sockets. Haskell is statically typed and lacks subsumption. This means that even though streams are unified by using a class, code which uses a stream of an unknown kind must be either polymorphic or use existential quantification. Yes, this is a problem. In my original proposal InputStream and OutputStream were types, but I enthusiastically embraced Simon M's idea of turning them into classes. As you say, it's not without its disadvantages. I see several possibilities here. * We could adopt Avery Lee's suggestion (from the discussion in 2003) to use field labels instead of methods. Advantages: InputStream and OutputStream behave more like their OOP equivalents, with no loss of extensibility. Disadvantages: potentially less efficient (no specialization possible); loses some static type information. * We could use a single type for all input and output streams in the standard library, but retain the type classes also. * We could provide existential wrappers: data IStream = (InputStream a) = MkIStream !a instance InputStream IStream where ... A nice thing about the last approach is that it supports dynamic downcasting: case (x :: IStream) of MkIStream x - case (Data.Dynamic.cast x :: UArrayInputStream) of Just x - (getUArray x, getCurrentIndex x) Nothing - ... Completeness. Unless File{Input,Output}Stream uses {read,write}() rather than file{Read,Write}, openFile provides only a subset of the functionality of open(): it works only with seekable files, e.g. not with /dev/tty. What is the type of stdin/stdout? They may be devices or pipes (not seekable), regular files (seekable), sockets... Simon M's current interface is incomplete, but the concept is fine. Again, to try to avoid confusion, what you call a seekable file the library calls a file, and what you call a file I would call a Posix filehandle. Roughly. It's hard to be precise because file is such a heavily overloaded term. (For example, is /dev/tty a file? Is the (major,minor) device number it might correspond to on a particular filesystem at a particular moment a file? Is the integer that's returned from open(/dev/tty, ...) a file? Is the tty device itself a file? I think you've used file in all four senses.) When I talk about a stream, I mean one end of a unidirectional pneumatic tube. If it's the ingoing end, you stick some data in the tube and it's carried away. If it's the outgoing end, you wait for some data to arrive and then take it. Tubes all look the same. No pneumatic tube is a storage device, but you may happen to know that it leads to a Frobozz Magic Storage Device at the other end. By the same token, stdin is never a file, but the data which appears through stdin may ultimately be coming from a file, and it's sometimes useful, in that case, to bypass stdin and access the file directly. The way to handle this is to have a separate stdinFile :: Maybe File. As for openFile: in the context of a certain filesystem at a certain time, a certain pathname may refer to * Nothing * A directory * A file (in the library sense); this might include things like /dev/hda and /dev/kmem * Both ends of a (named) pipe * A data source and a data sink which are related in some qualitative way (for example, keyboard and screen, or stdin and stdout) * A data source only * A data sink only * ... How to provide an interface to this zoo? The dynamic-typing approach is to return some sort of Thing with a complicated interface which is approximately the union of the interfaces for each thing in the above list. Unsupported methods fail when called. This is roughly what Posix does, except that directories are a special case, and Nothing is very special (as perhaps it should be, but I'm not sure). The Haskell approach is, I guess, to use an algebraic datatype, e.g. data FilesystemObject = Directory Directory | File File | InputOutput PosixInputStream PosixOutputStream | Input PosixInputStream | Output PosixOutputStream Here I'm using Posix*Stream for all streams backed by Posix filehandles. I'm unsure whether NoSuchPath should be in there too. You might say that this is annoyingly complicated. My first reaction is tough--it's exactly as complicated as the reality it models. But there should presumably be helper functions of types FilesystemObject-IStream and FilesystemObject-OStream. The other complication is that Posix makes you specify access rights when you look up a path in the filesystem. This makes no sense, but it's something we have to live with. So I'd argue for replacing openFile with something like data FilesystemObject = ... openPath :: FilePath - IOMode - IO FilesystemObject filesystemInputStream :: FilesystemObject - (IO?) IStream data
Re: [Haskell-cafe] performance question
Stijn De Saeger wrote: data Bound = I Double | E Double deriving (Eq, Show, Ord) data Interval = Il Bound Bound | Nil Bound Bound deriving (Eq,Ord) isIn :: Double - Interval - Bool isIn r (Nil x y) = not (isIn r (Il x y)) isIn r (Il (I x) (I y)) = r = x r = y isIn r (Il (I x) (E y)) = r = x r y isIn r (Il (E x) (I y)) = r x r = y isIn r (Il (E x) (E y)) = r x r y If performance is the main concern, I would flatten the data structure: data Interval = IlII Double Double | IlIE Double Double | IlEI Double Double | IlEE Double Double | NilII Double Double | NilIE Double Double | NilEI Double Double | NilEE Double Double isIn :: Double - Interval - Bool isIn r (IlII x y) = r = x r = y isIn r (IlIE x y) = r = x r y isIn r (IlEI x y) = r x r = y isIn r (IlEE x y) = r x r y isIn r (NilII x y) = r x || r y isIn r (NilIE x y) = r x || r = y isIn r (NilEI x y) = r = x || r y isIn r (NilEE x y) = r = x || r = y Depending on your application you might not need all of those cases. Another neat trick you can pull is to take advantage of the fact that Double is actually a discrete type, like Int, and you can therefore get away with closed intervals only: data Interval = Il Double Double | Nil Double Double isIn :: Double - Interval - Bool isIn r (Il x y) = r = x r = y isIn r (Nil x y) = r x || r y But this requires nextLargestDouble and nextSmallestDouble functions. I don't know if Haskell provides them. Also, you could run into trouble with wider-than-Double intermediate values. Finally, if you never do anything with intervals except pass them to isIn, you can do this: type Interval = Double - Bool isIn r i = i r -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Marcin 'Qrczak' Kowalczyk wrote: Henning Thielemann [EMAIL PROTECTED] writes: I did some shuffling based on mergesort [...] I think it doesn't guarantee equal probabilities of all permutations. It doesn't (proof: it has a bounded runtime, which can't be true of a perfect shuffling algorithm based on coin flips). But it looks pretty good. I think that iterating this algorithm n times is equivalent to assigning a random n-bit number to each list element and sorting, which is equivalent to Chris Okasaki's approach with one iteration and an array of size 2^n. Henning Thielemann [EMAIL PROTECTED] writes: It even works for infinite lists. In the sense that it doesn't diverge if you evaluate any finite prefix of the list, yes. In the sense that it does a good job of shuffling the list, no. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Scott Turner wrote: Analogous to quicksort's bad behavior in the worst case, an invocation of 'partition' is not guaranteed to make any progress with the shuffling, because one of the output lists might receive all of the input items. It's worse than quicksort, because there's no guarantee that the algorithm will ever terminate. But this is actually optimal--there's no way to perfectly shuffle a list using a bounded number of coin flips, because n! doesn't divide any power of 2 for n=3. I posted this algorithm on comp.lang.functional a while ago: http://groups-beta.google.com/group/comp.lang.functional/browse_frm/thread/570615e64e3e4fc0 -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: I/O interface
Marcin 'Qrczak' Kowalczyk wrote: Ben Rudiak-Gould [EMAIL PROTECTED] writes: The file interface in this library is only used for files, which are always seekable (by definition). What do you mean by files? What you get from open() is not always seekable [...] This was all discussed a year ago, and rather than reiterate it I'll try to expand the wiki page when I have a chance. Maybe all of this new discussion should be on the wiki also. -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe