March 2003 - Haskell - Haskell.org

broken "Research Letters" link
by b.i.mills＠massey.ac.nz 09 Mar '03

09 Mar '03

>> ``Algebraic Conversions'', A mathematical paper introducing >> a generalisation of homomorphism of universal algebras. >> In Research Letters in the Information and Mathematical >> Sciences Vol 2, May 2001. (pub by Massey University New Zealand). >> see also, \verb|http://www.massey.ac.nz/~wwiims/rlims| >This web link is broken. My apologies ... http://iims.massey.ac.nz/research/letters/volume2number1/02mills.pdf will get you there. I tested it just now, it works fine. Regards, Bruce.

1 0

ANNOUNCE: nhc98-1.16
by Malcolm Wallace 09 Mar '03

09 Mar '03

nhc98-1.16 ---------- http://www.haskell.org/nhc98 We announce a new release, 1.16, of the Haskell compiler nhc98, with the following new features and bugfixes of note. * nhc98 once again builds on Windows (Cygwin) with ghc. * nhc98 now works correctly in the presence of gcc-3.x. * A large subset of the 'base' package of hierarchical libraries is now included in the build. * The primitive FFI mechanism has been updated to match the latest official spec, and the full Foreign libraries are also included (in hierarchical form). * The library function List.sortBy now uses a stable O(n log n) mergesort. * Numerous other small fixes, including revisions to the Haskell'98 standard. * The website is now hosted at haskell.org * Our CVS repository is also now hosted at cvs.haskell.org Regards, The nhc98 team at York

1 0

Problem with hierarchical libraries in Hugs compared to ghc/nhc98
by Olaf Chitil 07 Mar '03

07 Mar '03

When trying to make our Haskell tracer Hat work with Hugs (November 2002) I noticed that * Hugs' implementation of hierarchical libraries differs from those of ghc and nhc98, and * Hugs' implementation choice makes it more restrictive than ghc/nhc98 A simple example: There is module B in file B.hs There is module Test.B in file Test/B.hs There is module Test.A in file Test/A.hs Module Test.A contains "import B". When compiling module Test.A both nhc98 and ghc imports module B from file B.hs. In contrast, Hugs imports module Test.B from file Test/B.hs and then stops with an error, because the module name is wrong. The simple reason why Hugs behaves so is that when searching a module it *always* searches the current directory (* where the import was demanded *) first. Only afterwards the paths set with the -P option are searched. I know that we generally try to avoid specifying filename and directory issues. However, this is not really a filename issue, but a problem of relative and absolute module names (wrt possibly several hierarchies). An "import B" in module Test.A could mean either module B or module Test.B. I suggest that the absolute module name takes precedence, because otherwise there is no way to import module B from module Test.A, whereas you can always import module Test.B from module Test.A by saying "import Test.B". I admit that this has the slight disadvantage that moving a set of modules into the hierarchical library will require not only changing all module names at the top but also in every import declaration, to not inadvertedly import the wrong module. So in the end this suggests that we should not allow relative module names at all. Note that this proposal still allows the current directory (of Hugs or in which the compiler was started) to be the root of the hierarchy that is searched first. In fact, this is probably the desirable default behaviour. Currently the hierarchical library proposal http://www.haskell.org/~simonmar/libraries/libraries.html does not say much about the semantics of the hierarchical module names. It really should. I'd very much like to hear other people's opinion on this (especially the Hugs maintainers'). The current behaviour of Hugs makes it impossible for Hat to work with Hugs. Hat creates a shadow hierarchy of transformed libraries: the transformed variant of Prelude is Hat.Prelude, the transformed variant of Control.Arrow is Hat.Control.Arrow etc. Nearly all of the transformed modules import both Prelude and Hat.Prelude ... Olaf -- OLAF CHITIL, Dept. of Computer Science, The University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767

4 4

Re: Random Permutations
by oleg＠pobox.com 07 Mar '03

07 Mar '03

> 1. Generate N random numbers r_k, say, uniform between 0 and 1. > 2. Form N pairs (1,r_1), (2,r_2), (3, r_3) ... (N,r_n). > 3. Sort this list/vector wrt the *secon* (random) number. > 4. In the sorted list the firs values (indices) give you the result. > This is of course quite general, not restricted to any Haskell > peculiarities. I'm sorry but this algorithm does NOT in general provide the perfect random permutation. Here's an excerpt from http://pobox.com/~oleg/ftp/Haskell/perfect-shuffle.txt that deals extensively with this issue: A commonly used shuffle algorithm attaches random tags to elements of a sequence and then sorts the sequence by the tags. Although this algorithm performs well in practice, it does not achieve the perfect shuffling. Let us consider the simplest example (which happens to be the worst case): a sequence of two elements, [a b]. According to the shuffle-by-random-keys algorithm, we pick two binary random numbers, and associate the first number with the 'a' element, and the second number with the 'b' element. The two numbers are the tags (keys) for the elements of the sequence. We then sort the keyed sequence in the ascending order of the keys. We assume a stable sort algorithm. There are only 4 possible combinations of two binary random numbers. Therefore, there are only four possible tagged sequences: [(0,a) (0,b)] [(0,a) (1,b)] [(1,a) (0,b)] [(1,a) (1,b)] After the sorting, the sequences become: [(0,a) (0,b)] [(0,a) (1,b)] [(0,b) (1,a)] [(1,a) (1,b)] As we can see, after the sorting, the sequence [a, b] is three times more likely than the sequence [b, a]. That can't be a perfect shuffle. Furthermore, if we have a sequence of N elements and associate with each element a key -- a random number uniformly distributed within [0, M-1] (where N!>M>=N), we have the configurational space of size M^N (i.e., M^N ways to key the sequence). There are N! possible permutations of the sequence. Alas, for N>2 and M<N!, M^N is not evenly divisible by N!. Therefore, certain permutations are bound to be a bit more likely than the others. The referred article presents two algorithms -- a naive one and a more advanced one. The latter has a complexity O(n log(N)) and is _proven_ to give the perfect shuffling. The complexity is also proven.

3 2

GHCi 5.04.2 segfaults on expression evaluation
by Carlos Eduardo Scheidegger 07 Mar '03

07 Mar '03

Hello. I think I've come across a GHCi bug. Using the following module, GHCi version 5.04.2 segfaults, apparently trying to compute a type using functional dependencies. The segfault happens when I try to calculate (v1 .> v2). I tried the code on Hugs, and it answers Main> v1 .> v2 V [] :: PSOp (Pop a Id) as expected. I think the problem is occuring in the line > instance Reverse a b c => CheckPS Id a b c because if I remove the line > instance Reverse a (Pop t b) c => Reverse (Pop t a) b c instead of segfaulting, GHCi rightfully complains: <interactive>:1: No instance for (Reverse (Pop a Id) Id c) arising from use of `.>' at <interactive>:1 In the definition of `it': v1 .> v2 GHC compiles the program just fine and runs it without any issues. I installed GHC 5.04.2 using the RedHat 8.0 RPM's. If there's any important information you may need from me, please, tell me and I will be glad to help. I've also cross-posted this to the bug section at sourceforge.net, and there the module file can be found as a separate file. Thank you, Carlos -------------------------------------------------------------------------------- > class ComposePS a b c | a b -> c where > (.>) :: PSOp a -> PSOp b -> PSOp c > (V a) .> (V b) = V (a ++ b) > instance (ConcatPS a b c, CheckPS c Id Id d) => ComposePS a b d -------------------------------------------------------------------------------- > data PSOp a = V [String] deriving Show > data Id > data Push t rest > data Pop t rest > class Reverse a b c | a b -> c > instance Reverse Id b b > instance Reverse a (Pop t b) c => Reverse (Pop t a) b c > instance Reverse a (Push t b) c => Reverse (Push t a) b c -------------------------------------------------------------------------------- > class ConcatPS a b c | a b -> c where > ccat :: a -> b -> c > instance ConcatPS Id a a > instance ConcatPS a b c => ConcatPS (Pop t a) b (Pop t c) > instance ConcatPS a b c => ConcatPS (Push t a) b (Push t c) -------------------------------------------------------------------------------- > class CheckPS a b c d | a b c -> d where > check :: a -> b -> c -> d > check _ _ _ = error "oki" > instance Reverse a b c => CheckPS Id a b c -- instance CheckPS a b (Push t c) d => CheckPS (Push t a) b c d > instance CheckPS a (Pop t b) Id d => CheckPS (Pop t a) b Id d -- instance CheckPS a b c d => CheckPS (Pop t a) b (Push t c) d -- instance (SameType t1 t2, CheckPS a b c d) => CheckPS (Pop t1 a) b (Push t2 c) d > u = undefined > v1 :: PSOp (Pop a Id) > v1 = V [] > v2 :: PSOp Id > v2 = V []

1 0

Fundeps question
by Carlos Eduardo Scheidegger 07 Mar '03

07 Mar '03

Hello, I am currently toying with the idea of implementing a PostScript library in Haskell, and I am currently implementing a static, simplified version of the Postscript type checker using phantom types and functional dependencies. I am enriching the Postscript definitions with types so that as many typing mistakes as possible are detected, as early as possible. The implementation is not very fancy, but some of the functional dependency issues I've come across are a bit confusing, so I am hoping some of the knowledgeable people in the list can lend me a hand in solving the problems. My first attempt at solving the problem involved something similar to this: > data Nil > data Cons t l > u = undefined > class EqList a b c | a b -> c where > comp :: a -> b -> c > comp _ _ = error "" > instance EqList Nil Nil Nil > instance EqList l1 l2 r => EqList (Cons t l1) (Cons t l2) r This works if there are no type variables involved: *Main> :t comp (u :: Cons Int Nil) (u :: Cons Float Nil) No instance for (EqList (Cons Int Nil) (Cons Float Nil) c) arising from use of `comp' at <No locn> *Main> :t comp (u :: Cons Int Nil) (u :: Cons Int Nil) Nil *Main> :t comp (u :: Cons Int (Cons Float Nil)) (u :: Cons Int (Cons Float Nil)) Nil *Main> :t comp (u :: Cons Int (Cons Float Nil)) (u :: Cons Int (Cons Int Nil)) No instance for (EqList (Cons Float Nil) (Cons Int Nil) c) arising from use of `comp' at <No locn> Now, in my application, the types had type variables in them, and I wanted to unify, for example, (Cons Int Nil) with (Cons a Nil). As most of you smart folks must have already deduced from reading the above code alone, this won't work. I suppose it is because the old confusion between a type variable being universally quantified and existentially quantified (is it?). Thinking that there should be a way to do this, I decided to try a different approach, using a helper class: > class SameType a b | a -> b, b -> a where > instance SameType a a > instance EqList Nil Nil Nil > instance EqList (SameType t1 t2, EqList l1 l2 r) => > EqList (Cons t1 l1) (Cons t2 l2) r But, this time, the typechecker gives me attitude: Inferred type is less polymorphic than expected Quantified type variable `t2' is unified with another quantified type variable `t1' When trying to generalise the type inferred for `comp' Signature type: forall t1 l1 t2 l2 r. (SameType t1 t2, EqList l1 l2 r) => Cons t1 l1 -> Cons t2 l2 -> r Type to generalise: Cons t1 l1 -> Cons t1 l2 -> r In the instance declaration for `EqList (Cons t1 l1) (Cons t2 l2) r' I don't quite understand the error. If I figured it out correctly, the compiler is examining the SameType fundep and concluding that in order two enforce the constraint (SameType t1 t2), t1 and t2 must be the same type, and since I'm telling him they possibly aren't, he's complaining. I may be grossly misunderstanding the issue here, but what I expected would happen is that instead of failing the typecheck, I would simply not be allowed to have instances of EqList of t1 and t2 not being the same class, because that would fail the fundep check later. And, more interestingly, if I use a definition of SameType like this: > instance SameType Int Int > instance SameType Float Float > instance SameType a b => Sametype [a] [b] > instance (SameType a b, SameType c d) > => SameType (Either a c) (Either b d) ... Both my original program and this example work properly. For example, (Cons Int Nil) (Cons a Nil) becomes a proper instance of EqList. This approach works in the case of my library, because there's a limited number of types in Postscript, but I was looking fore a more elegant solution. I do not know if I'm doing something utterly stupid, or if there are more serious underlying issues that I am not aware of, but I would be very grateful for any information or pointers to papers that discuss the issues involved. And if by any chance anyone is interested in the library, I'd be more than happy to put it somewhere public. I think it's turning out to be a rather nice application of fundeps and type computations. Thank you very much in advance, Carlos

2 1

HTTP protocol libraries
by Johannes Waldmann 07 Mar '03

07 Mar '03

Dear all, I am looking for a Haskell library for the HTTP/1.1 protocol, i. e. data types for Requests and Responses, and functions to read chunked bodies etc. Is there such a thing? -- -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ -- -- joe(a)informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/207 --

2 1

Re: int to float problem
by Matthew Donadio 07 Mar '03

07 Mar '03

>Thank does sound like a pain, but it's better than putting fromIntegral >all over my code. Why can't Haskell unify a an expected float with an >infered int? It seems that this would make life alot easier. This is my biggest gripe with Haskell, at least for what I do. The numeric class system is good, but it assumes that the sub-classes are distict, where in fact integers are a proper subset of reals, which are a proper subset of complex numbers. Personally, I would like to see module level explicit coersion, similar to the way the default numeric type is handled. Something like: > module Blah where > coerce Int to Double > in mean with fromInt > mean :: [Double] -> Double > mean x = sum x / length x So, if the typesystem infers a Double, but finds an Int, the function would be rewritten as if it had been specified as > mean x = sum x / (fromInt.length) x If you want a global declaration then you could specify > coerce Int to Double > with fromInt --Matthew Donadio (m.p.donadio(a)ieee.org)

4 6

help please
by muskaan asdfg 06 Mar '03

06 Mar '03

hi there, i am attending university of new orleans and for my 4501 class i picked haskell language to do my project. rite now i am dealing with a lot of problems because there are no books avaliable in bookstore on haskell, and i dont find online information any helpfull. so please help. i am trying to find what are the compliation units for a complete program in haskell. is the answer seperate compliation in modules is the answer. please lead in right direction thanks tina __________________________________________________ Do you Yahoo!? Yahoo! Tax Center - forms, calculators, tips, more http://taxes.yahoo.com/

1 0

Re: random permutations
by Dimitre Novatchev 06 Mar '03

06 Mar '03

--- George Russell <ger(a)tzi.de> wrote: > I think Ralf Hinze's method is the best presented so far. I would > write > it slightly differently though. In pseudo-code I would proceed as > follows: > (1) write the values to an array a[1]..a[n] > (2) for i from n to 2 > do > j <- random integer between 1 and i > swap a[i] and a[j] > At the end the elements of a will be a random permutation. In > Haskell > you can of course use an STArray for this. > > Ralf Hinze's method requires you to do n multiplications and n > divisions > to compute the factorial and then compute a random number. I have > to compute n random numbers rather than a single random number, on > the > other hand I don't have to do the multiplications and divisions. > Indeed, since you need more random bits to compute a random big > number > than a random little number, I don't think in theory my method > requires > much more work from the random number generator than Ralf Hinze's. This is exactly how I did it in producing a randomised node-set in XSLT: "Randomization of node-sets or node-lists" http://www.topxml.com/code/default.asp?p=3&id=v20020504013704 ===== Cheers, Dimitre Novatchev. http://fxsl.sourceforge.net/ -- the home of FXSL __________________________________________________ Do you Yahoo!? Yahoo! Tax Center - forms, calculators, tips, more http://taxes.yahoo.com/

1 0