- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] Limits of deduction
by Matthew Brecknell 15 May '07

15 May '07

Roberto Zunino: > Yes, you are right, I didn't want to involve type classes and assumed > 3::Int. A better example would be: > > polyf :: Int -> a -> Int > polyf x y = if x==0 then 0 > else if x==1 then polyf (x-1) (\z->z) > else polyf (x-2) () > > Here, passing both () and (\z->z) _does_ make inference fail. Alternatively, type inference succeeds in rejecting an illegal program [1,2]. :-) So I think we need to be a little more precise about exactly what is undecideable in this example. Yes, the explicit type signature you've given is valid, and the Hindley-Milner type inference algorithm is not able to assign that type without an explicit signature. But that doesn't make Hindley-Milner type inference undecideable. On the contrary, Hindley-Milner type inference is deliberately designed to be decideable. To achieve that, it assumes monomorphic types in certain identifiable contexts, and therefore rejects some functions for which valid types exist. So I think the point you were making is that the problem of inferring the types of all functions for which valid types exist is, in general, undecideable. Hindley-Milner inference ensures decideability by choosing a somewhat less general (but still useful) problem. For what it's worth (not much), it might be possible to invent a decideable type inference which could infer types for a slightly larger set of functions (including polyf), by automatically generalising the types of arguments which are not inspected. Of course, doing so would presuppose the decideability of the subproblem of identifying unused arguments, and achieving that would undoubtedly require certain restrictions on the subproblem definition, analogous to the ones employed by Hindley-Milner. [1] http://haskell.org/onlinereport/decls.html#sect4.1.4 [2] http://haskell.org/onlinereport/decls.html#sect4.5

1 0

Limits of deduction
by Andrew Coppin 14 May '07

14 May '07

Suppose I have you the source code to some arbitrary function that takes a list and returns another list. It is possible to determine whether the function always examins the entire input list? Or would that be equivilent to solving the Halting Problem? (Last time I checked, the Halting Problem is unsolvable.)

9 14

How to decrease ghc link time
by Georg Sauthoff 14 May '07

14 May '07

Hi, well, I work with a Haskell project which I regulary compile with ghc. I am a bit unhappy with the link time of the project (i.e. the time ghc needs to link everyting). The project consinst of ~60 Haskell and ~25 foreign files. Some parts of the project are organized like a 'cluster', i.e. the foreign part has only one function, which is used from Haskell-Code. What could I do to improve the link time? Does some concept of 'Packages' exists in Haskell, which helps with the link time? If someone does it before, does it help to link against shared foreign libraries instead of static ones (if this is possible)? Best regards Georg

2 3

CUFP
by Simon Peyton-Jones 14 May '07

14 May '07

The CUFP website is working again now. http://cufp.galois.com/ Thanks for pointing it out. Simon

1 0

More mystery with existentials and fundeps
by Matthew Sackman 14 May '07

14 May '07

Hi, > {-# OPTIONS_GHC -fglasgow-exts #-} > > class F a b | b -> a where > > data G :: * -> * where > GC :: (F a b) => a -> G b > > foo :: (F a b) => G b -> a > foo g = case g of > (GC a) -> a I may be being dumb, but I think this should work. Any value of G using the GC constructor will be able to define a from G b given F a b due to the functional dependency. In the above 'case' statement version I get: Couldn't match expected type `a' (a rigid variable) against inferred type `a1' (a rigid variable) `a' is bound by the type signature for `foo' at Test.lhs:10:11 `a1' is bound by the pattern for `GC' at Test.lhs:12:12-15 In the expression: a In a case alternative: (GC a) -> a In the expression: case g of (GC a) -> a > foo2 :: (F a b) => G b -> a > foo2 g = let (GC a) = g in a And this 'let' statement version explodes with: My brain just exploded. I can't handle pattern bindings for existentially-quantified constructors. In the binding group for (GC a) In a pattern binding: (GC a) = g In the expression: let (GC a) = g in a In the definition of `foo2': foo2 g = let (GC a) = g in a So is this a missing feature of GHC or am I (more likely) utterly mistaken about what should be possible here? Many thanks, Matthew

1 1

Disadvantages of de Bruijn indicies?
by Neil Mitchell 14 May '07

14 May '07

Hi, de Bruijn indicies look quite nice, and seem to eliminate a lot of complexity when dealing with free variables: http://en.wikipedia.org/wiki/De_Bruijn_index So I was wondering, are they suitable for use in a compiler? If so, what are their disadvantages/advantages? Is there any particular reason that GHC (as an example) doesn't use them in its Core? I'm trying to decide if I should use them in my compilers data type - and would like some recommendations before I start. Thanks Neil

7 9

hash of a lazy bytestring?
by David Roundy 13 May '07

13 May '07

I was just contemplating hashes, and it occurred to me that it would be nice to be able to compute the hash of a lazily constructed bytestring and lazily consume its output without requiring the whole string to ever be in memory. Or in general, it'd be nice to be able to perform two simultaneous consumptions of a lazy list without requiring that the entire list be stored. Another example would be computing the length of an ordinary list: do l <- readFile "foo" let len = length l writeFile "bar" l putStrLn $ "Length is " ++ show l It would be nice if one could write length such that the above function doesn't require the entire file be stored in memory. Are there any approaches that would make this possible? The only approach I can imagine would involve something like weak pointers and finalizers. It seems like it'd be a useful paradigm, if it's possible. Basically to be able to write a lazy consumer that doesn't hold onto its input, but instead is computed as the garbage collector frees the input. Something like: length' :: [a] -> Integer length' !xs = l' 0 `safeInterleave` xs where l' n [] = n l' !n (y:ys) = l' (n+1) `safeInterleave` ys safeInterleave :: (a -> b) -> a -> b safeInterleave f !x = -- create weak reference to x, associate finalizer, -- so that if x is GCed, then we'll immediately -- evaluate f x before we lose the value of x. Is this possible? Would it be reasonable? I imagine we'd run into trouble with laziness keeping safeInterleave from being called, with the result that we'd hang onto x even though the safeInterleave would have hoped to allow x to be GCed. -- David Roundy http://www.darcs.net

4 4

Compilling GHC on Vista
by Monique Monteiro 13 May '07

13 May '07

Hi all, I'm trying to compile GHC on Windows Vista, but I encountered the following error when running ./configure --host=i386-unknown-mingw32 --with-gcc=c:/MinGW/bin/gcc: configure: error: C compiler cannot create executables See `config.log' for more details. ./configure: line 3404: cannot create temp file for here document: No such file or directory ./configure: line 3441: cannot create temp file for here document: No such file or directory Has anyone any idea about what may be happening? Thanks in advance, Monique -- __________________________________________________________ Monique Monteiro, MSc MCP .NET Framework 2.0 / SCJP / IBM OOAD Project Manager Recife Microsoft Innovation Center +55 81 34198137 http://www.cin.ufpe.br/~mlbm http://thespoke.net/blogs/moniquelouise/default.aspx monique(a)qualiti.com.br MSN: monique_louise(a)msn.com

5 23

ambiguous type variables at MPTC
by Nicolas Frisby 13 May '07

13 May '07

This is a question about some interesting behaviors in GHC's typechecker regarding MPTCs. The brief code is at the bottom of the message. By the way, the types can be inferred but not declared without the forall and ascription in the where clause. f1 below is illegal because we don't know what type the result of read should be: it's type is ambigious. Why isn't f2 illegal as well? If C had a functional dependency of a -> b, then I could understand accepting the type. However, without the functional dependency, b might not necessarily be determined from a. i) The above reasoning encroaches on the magic of TypeCast, which effectively allows local functional dependencies to be declared at the instance-level. Because of this, the typeclass mechanism might effectively have a means of determining b from a without the class being explicitly decorated with the functional dependency. ii) Type errors where b really isn't determined by a are caught by the typechecker wherever f2's arguments are instantiated (at some usage site). This is convenient at times (it admits the uncertainty of the "might not necessarily") and annoying at others (debugging): perhaps there's a ghc switch to disallow this? If f2 is legal, why if f3 illegal? For some usage site of f3, the constraint C String b might allow b to be resolved given whatever instances of C are in effect. Is there a motivation for these behaviors? Are these sorts of cases discussed in the CHR/FD paper that motivated the coverage condition (which I have yet to read)? If ATs or GADTs would handle these situations differently, why so? Should FDs also handle these situations differently? Thanks for your time. class C a b where method :: a -> b {- illegal due to ambiguous variable f1 :: forall a . (Read a) => String -> () f1 x = () where _ = read x :: a -} -- legal, despite the lack of an FD (a -> b) on C f2 :: forall a b . (C a b) => a -> () f2 x = () where _ = method x :: b {- illegal due to none of the forall'd variables being "reachable" from the type proper f3 :: forall b . (C String b) => String -> () f3 x = () where _ = method x :: b -}

2 1

Re: [Haskell-cafe] GHC Hangs
by Josiah Manson 12 May '07

12 May '07

When the intermediate files are removed, GHC still hangs. In fact, the intermediate files do not seem to be corrupt in any way, as the only way to get a working executable is to run GHC more than once. First to produce the intermediate files, then to link them into an executable. On 5/7/07, Cale Gibbard <cgibbard(a)gmail.com> wrote: > > On 07/05/07, Josiah Manson <josiahmanson(a)gmail.com> wrote: > > There is still a problem when I use the version you linked to. At first > I > > was hopeful, because the first time I tried compiling bisect.hs it > worked. > > All subsequent attempts, however, have failed. > > Maybe try getting rid of all the intermediate (*.hi *.o) files created > when compiling it? Not that this is necessarily a permanent > solution... > > - Cale >

3 4