June 2002 - Glasgow-haskell-users

mergesort. Reply
by Serge D. Mechveliani 21 Oct '02

21 Oct '02

Ketil Z. Malde <ketil(a)ii.uib.no> writes > I'll hereby argue for using a quicksort implementation akin to > >> sortBy' _ [] = [] >> sortBy' pc (x:xs) = let (l,e,g) = part3 (`pc` x) xs >> in sortBy' pc l ++ (x:e) ++ sortBy' pc g >> where >> part3 comp xs = p3 [] [] [] comp xs >> p3 ls es gs _ [] = (ls,es,gs) >> p3 ls es gs comp (x:xs) = case comp x of >> LT -> p3 (x:ls) es gs comp xs >> EQ -> p3 ls (x:es) gs comp xs >> GT -> p3 ls es (x:gs) comp xs > > (hopefully this is fairly bug-free) At least for my data (lots of > values, limited range), it appears to speed things up tremendously. I > haven't measured more general cases in any detail, though. And one > obvious drawback may be that it's not stable, which I think can be > alleviated by a few well placed 'reverse's. > > Comments welcome! But sortBy' (compare) [1 .. n] costs too much, even for n = 11000. It costs (on worst data) many times more than mergeSort. ----------------- Serge Mechveliani mechvel(a)botik.ru

8 11

RE: Weird profiling behaviour
by Simon Marlow 15 Jul '02

15 Jul '02

> >> The default definition of sortBy uses insertion sort > > > I have vague recollection of the wisdom of this choice being > > questioned > > And now I think I'm about question it as well... 5.02 uses quicksort, but 5.04 will use mergesort instead which has much more predictable performance behaviour. Cheers, Simon

6 6

�ǯu��X�X��
by vnm_2gk1fvlycqk5＠amvescap.com 30 Jun '02

30 Jun '02

¶Ç¯už¹œX¥X°â §ÚŠ³¥_°Ï02_¶}ÀY¶Ç¯už¹œX¡AŠ@¬°77270µ§ ¬O§Ú±qŠUÓŠP·~€œ·|¡B¹qžÜÃ¯¡B¶À¶¡BŒx«H©Ò¡B ºô»Úºôžô¡A¥úºÐ€ù...µ¥µ¥¡A žgŠ~²Ö€ë€@µ§€@µ§¥Ž€JŠ¬¶°€UšÓªº¡A¶O€F«Ü€jªº¥\€Ò¡C ¥úªá¿ú¶RŒx«H©Ò¥Xªºªº¥U€l¡AŽNªá€F€£€Ö¿ú¡A ŠAžg¹L²Îp€èªkŸã²z¡A©Ò¥HšSŠ³¥ôŠó€@µ§¬O«œÆªº¡A šÃžg¹L¹ê»Úµo°eŽúžÕ¡AŠAç°£±ŒµL®Äªºž¹œX¡A ©Ò¥HšC€@µ§šì4€ë©³¬°€î¡A³£¥i¥Hµo°e¡C ®ÚŸÚžgÅç¡AŽX¥G©ÒŠ³02_¶}ÀYªº¶Ç¯u¡A ³£€wŠ¬¶°Šb³ožÌ€F¡A±qšä¥LšÓ·œ¡A€]€£€Ó®e©öŠA§äšì·sªº¡C ŠpªG±zŠ³¿³œìÁÊ¶R¡A§ÚÄ@·N¥H3000€ž€ÀšÉ¡C ŸH€p©j tel: 02-27492314

1 0

Existential Datatypes
by Jeremy Shaw 30 Jun '02

30 Jun '02

Hello, I have a question regarding named fields and existential data types. I want to extend this example from the User's guide to use named fields: data Foo = forall a. MkFoo a (a->Bool) | Nil foo = MkFoo 'g' isUpper I tried: data Foo2 = forall a. MkFoo2 { val2 :: a , func2 :: a -> Bool } But the compiler said: Can't combine named fields with locally-quantified type variables In the declaration of data constructor MkFoo2 In the data type declaration for `Foo2' Then I tried: data Foo3 = MkFoo3 { val3 :: forall a. a , func3 :: forall a. (a -> Bool) } foo3 = MkFoo3 'g' isUpper And the compiler said: Inferred type is less polymorphic than expected Quantified type variable `a' is unified with `Char' Signature type: forall a. a Type to generalise: Char When checking an expression type signature In the first argument of `MkFoo3', namely 'g' In the definition of `foo3': MkFoo3 'g' isUpper Am I doing something wrong, or can GHC just not do what I want yet? >From what I gathered looking through the mailing list, existential types are still a bit hacked up? Thanks! Jeremy Shaw.

2 1

functional dependencies - bug?
by Christian Maeder 28 Jun '02

28 Jun '02

Hi, does anybody have experiences with "Type Classes with Functional Dependencies" (LNCS 1782, ESOP 2000, March 200, by Mark P. Jones)? I've tried the example in the above paper: class Collects e ce | ce -> e where empty :: ce insert :: e -> ce -> ce member :: e -> ce -> Bool This works correctly for: instance Eq a => Collects a [a] where instance Collects Char Int where and complains correctly for: instance Collects Char Int where instance Collects Bool Int where with "Functional dependencies conflict between instance declarations" Now to my problem with a context in the class declaration: class Eq ce => Collects e ce | ce -> e where empty :: ce ... This works as above, but correctly complains for: data Stupid = Stupid -- without equality instance Collects Bool Stupid where with "No instance for (Eq Stupid)". However, if I supply an (admittingly stupid) default definition for "empty" within the class declaration: class Eq ce => Collects e ce | ce -> e where empty :: ce empty = error("empty") ... I no longer get the above "No instance for (Eq Stupid)"-Message, and I guess that is a bug (or a feature that I don't understand). When I change the context to "Eq e" everything is fine again: instance Collects Stupid Int where complains as above. I don't know when (even meaningful) default definitions cause that context conditions are not checked. In fact I noticed this error only after I've removed a default definition just to find out that my instance declaration were wrong that seemed to be correct before (but instances for contexts were missing). Are there any other (known) pitfalls with functional dependencies? Regards Christian

1 0

Re: GHC and Win32 API - help wanted
by C.Reinke 28 Jun '02

28 Jun '02

> | * Could anyone with cvs/fptools/makefile-expertise lend me a hand > | * if I try again to build only hslibs/win32 from cvs? Or is it --------------------------------^^^^ (only) > a) No it is not unreasonable to expect it to build, cleanly, > starting from scratch. It jolly well ought to. Ah, but (perhaps unlike Mike) I don't want to build from scratch, but *only* the hslibs/win32 directory. For older packages like win32, there is no inherent reason why it should need to be build with a freshly-built ghc by default (although ffi-bindings rule out older ghcs), and there are lots of extra things that can go wrong when one tries to build ghc from sources. Not that those new problems couldn't be sorted as well, with some further recursive levels of debugging, but that's far away from the original problem.. To wit, here's recursive story so far: user1: I'd like to compile my hgl project with ghc on windows, but it doesn't work user2: I can reproduce the effects, one of the problems seems to be in a call to the win32 api that behaves differently using hugs or ghc user3: yes, there was a problem with greencard's output, greencard is now fixed user2: is that the released greencard? user3: no, only cvs user2: how do I get an updated win32 package? user3: it's only in cvs user4: but the cvs win32 sources are no longer regenerated automatically user3: I've regreencarded the win32 sources in cvs, but I can't test that here, so that may not make it into the next release user2: I could try testing them here. how do I make only the hslibs/win32 package, without building everything? user5: you don't - you always build ghc from source first, then build the package with the freshly-built ghc; or rather: you build lots of packages, one of which is the one you want.. user2: sigh.. I don't really want that.. but let's see.. user2: ..what is this odd effect?.. ... It should be easy to see that this makes it harder than necessary for cvs-outsiders to contribute anything small, such as an offer to test a change on their system. May I suggest to have, either as part of the local Makefiles, or at least as a separate ascii file, the information about which version of ghc is minimally needed to build each package? Given that the package.conf-files already record dependencies, that may be a good place to put this info (just checking... no, they don't seem to do that yet, not even a package version number?). That would go some way towards a more modular system. > b) I strongly recommend that you build it by checking out > fptools/mk, glafp-utils (you get these with fpconfig) > fptools/ghc, libraries, hslibs > > Then build GHC, using practically any installed GHC (later than > about 4.02 I think). Then build 'libraries'. Then build 'hslibs', > which includes win32. But libraries and hslibs include lots of other stuff as well, most of which is a lot bigger than win32, and unlikely to be needed in newest form just to rebuild win32. That is a lot of extra time in downloading and building, and a lot more room for new problems. At least the unnecessary building should be avoidable (that's what Makefiles are used for, no?). > The point here is that we update 'libraries' and 'hslibs' to track > the GHC in the tree, so there's no guarantee that it'll work if you > compile it with some older GHC. It may, but it may not. But cvs contributors should know whether or not they need to bump up the needs-ghc-version-x number in a package to make their changes build? > c) I use the standard build.mk (build.mk.sample). I don't try to > install anything, at least not to start with. Just say use the > standard build.mk (or even an empty one) and say 'make'. > > I did this today, and happily built a HSwin32.o package from > scratch. Great, so perhaps you could check quickly whether that solves some of the HGL problems?-) HGL is in hslibs/graphics, which you've just built anyway, or you could use Sigbjorn's nice msi-package from the Hugs download page. Then take the following small example file: import GraphicsUtils main = runGraphics $ do w <- openWindow "testing" (200,200) drawInWindow w $ text (100,100) "1,2,3" drawInWindow w $ polygon [(50,50),(100,100),(50,100)] getKey w closeWindow w and compile with something like: ghc --make -i<path to your graphics bundle>/lib/win32 --package concurrent --package win32 example.hs If the result runs without error (using your newly-built win32 package), things have improved a lot. If there's an error about Polygon and storage, there's still something unexpected wrong, but if you comment out the second "drawInWindow"-line, the program should run, and the window should be of reasonable size (not a full-screen titlebar-only thing, as with the current version of win32). It may still have to be stopped with ctrl-c, but that would be enough improvement to suggest that Alastair's changes should be included in the upcoming ghc. Given this simple test, you'll agree that having to compile ghc and objectIO and ... from CVS just to get there is somewhat unexpected (of course, you might wonder whether having to install HGL is an expected side-effect of your own email;-). Sorry to be so obstinate, Claus PS. Just to show that I'm a good netizen, I've tried what you suggested. The problems are unlikely to be big, but I'm not tempted to follow the recursion any deeper (for the usual reasons: work is waiting): cvs co fpconfig cd fptools; cvs co ghc libraries hslibs autoconf; cd ghc; autoconf; cd .. configure configure: error: Happy version 1.13 or later is required to compile GHC. [delete exit in configure's happy test] configure cd ghc make $ cd ghc Administrator@CR3-PC /tmp/tmp/fptools/ghc $ make ------------------------------------------------------------------------ ===fptools== Recursively making `all' in includes utils driver docs compiler rts ... PWD = /tmp/tmp/fptools/ghc ------------------------------------------------------------------------ ------------------------------------------------------------------------ ==fptools== make all - --unix -r; in /tmp/tmp/fptools/ghc/includes ------------------------------------------------------------------------ Creating config.h... Done. gcc -O -c mkDerivedConstants.c -o mkDerivedConstants.o In file included from Rts.h:20, from mkDerivedConstants.c:10: Stg.h:210: gmp.h: No such file or directory make[1]: *** [mkDerivedConstants.o] Error 1 make: *** [all] Error 1 $ uname -a CYGWIN_NT-5.0 CR3-PC 1.3.10(0.51/3/2) 2002-02-25 11:14 i686 unknown $ ghc --version The Glorious Glasgow Haskell Compilation System, version 5.02.2

1 0

Happy 1.11 binaries for OpenBSD i386
by dons＠cse.unsw.edu.au 28 Jun '02

28 Jun '02

Hi, I've finished a binary package and a port of Happy-1.11 to OpenBSD i386. The binary package (296k) can be ftp'd from: ftp://ftp.cse.unsw.edu.au/pub/users/dons/happy/happy-1.11.tgz This can be installed with the command (as root): pkg_add happy-1.11.tgz You can remove the package with: pkg_delete happy-1.11 If you want to see how the package was built, or just like building from source, an OpenBSD ports system "port" is also available: ftp://ftp.cse.unsw.edu.au/pub/users/dons/happy/happy-1.11-port.tgz Making sure you have a reasonably recent OpenBSD ports tree on the system, and a recent version of GHC installed, download the port to a convenient place and: tar xvzf happy-1.11-port.tgz cd happy then, as root: make && make install You can uninstall this with pkg_delete, as above. Note that you will need gmake to do the build. If you need GHC there is a binary package of GHC 4.08.2 available from: ftp://ftp.cse.unsw.edu.au/pub/users/dons/ghc/ghc-4.08.2.tgz Send any bugs or suggestions to me at <dons(a)cse.unsw.edu.au>. Thanks, Don

1 1

RE: GHC and Win32 API - help wanted
by Simon Peyton-Jones 28 Jun '02

28 Jun '02

| We suspect that Alastairs fixes may still leave some issues | with concurrency / potentially blocking threads / ffi (at | least in GHC's default configuration on windows), but we'd | like to see just how far the improvements go, as the next | stable release of GHC is imminent. | | * Could anyone with cvs/fptools/makefile-expertise lend me a hand | * if I try again to build only hslibs/win32 from cvs? Or is it | * completely unreasonable to expect this to work? Claus, and Mike, I'm very grateful to you for having a go at this. Esp now that Julian and Reuben have moved on to pastures new, we rely increasingly on help from other people to keep GHC flying. It's just too broad a system for Simon M and me to maintain every library. I'm no expert on the Win32 library, but: a) No it is not unreasonable to expect it to build, cleanly, starting from scratch. It jolly well ought to. b) I strongly recommend that you build it by checking out fptools/mk, glafp-utils (you get these with fpconfig) fptools/ghc, libraries, hslibs Then build GHC, using practically any installed GHC (later than about 4.02 I think). Then build 'libraries'. Then build 'hslibs', which includes win32. The point here is that we update 'libraries' and 'hslibs' to track the GHC in the tree, so there's no guarantee that it'll work if you compile it with some older GHC. It may, but it may not. c) I use the standard build.mk (build.mk.sample). I don't try to install anything, at least not to start with. Just say use the standard build.mk (or even an empty one) and say 'make'. I did this today, and happily built a HSwin32.o package from scratch. Mike Thomas says he can't build GHC from scratch on Windows. I'm sure you've reported this, Mike, but can you say again what happens to you. (Assuming the setup I outline above.) It's puzzling that it works for me but not for you. Make sure you start from a totally clean tree. Lots of stuff has been changing in the HEAD. Simon

1 0

GHC and Win32 API - help wanted
by C.Reinke 28 Jun '02

28 Jun '02

A while ago (in connection with HGL problems, some of which were traced to incorrect greencard output), I asked here: > Alternatively, is anyone out there using ghc's win32 binding? As noone has responded so far, I have to conclude that this is quite an infrequently used package.. - noone using ghc + win32 API? - noone using ghc + hgl on windows? Alastair provided updated greencard outputs for win32, but neither he nor I tend to build ghc from source on our windows machines, and I found it non-obvious how to build hslibs/win32 from cvs in isolation (without building most everything else), so I asked here: > I still have to figure out how to make hslibs/win32 in > isolation, so I won't be able to test & confirm whether this > solves all the HGL/GHC/Win32 problems for a while (e.g., there > was the problem of polygon creation running out of resources, > see Friday's email; that could easily be related to the same > ffi problem, but it would be good to check) - anyone else in > a better position for testing? Again, no response, so I have to conclude that either noone is building ghc from cvs on windows here, or none of those who do have any interest in HGL.. no users, no testers:-( We suspect that Alastairs fixes may still leave some issues with concurrency / potentially blocking threads / ffi (at least in GHC's default configuration on windows), but we'd like to see just how far the improvements go, as the next stable release of GHC is imminent. * Could anyone with cvs/fptools/makefile-expertise lend me a hand * if I try again to build only hslibs/win32 from cvs? Or is it * completely unreasonable to expect this to work? The fresh greencard output seems to depend on parts of the ffi syntax that weren't supported in ghc-5.02.2, so I'd have to try with ghc-5.03.20020208 (the latest windows installer snapshot). Here's what I've got now, re-configured for the new ghc version: - checked out cvs sources - cd fptools; autoconf; configure --with-ghc=ghc-5.03.... - create mk/build.mk: GHC_INPLACE = $(GHC) GHC_PKG_INPLACE = echo 'GHC_PKG_INPLACE' - cd hslibs/win32 $ make gcc -E -undef -traditional -I../../ghc/includes -x c win32.conf.in \ | sed 's/^#.*$//g' >win32.conf.inplace win32.conf.in:1: config.h: No such file or directory gcc -E -undef -traditional -I../../ghc/includes -DINSTALLING -x c win32.conf.in \ | sed 's/^#.*$//g' >win32.conf.installed win32.conf.in:1: config.h: No such file or directory ../../ghc/utils/ghc-pkg/ghc-pkg-inplace --update-package <win32.conf.inplace ../../ghc/utils/ghc-pkg/ghc-pkg-inplace: not found make: *** [all] Error 127 I don't really see why a simple make should start installing things, even if it's just package configurations, so in my first attempt, a few days ago, I just replaced set GHC_PKG_INPLACE to a dummy (in fptools/mk/build.mk), and got on to the next problem (a splitting-object-file headache, iirc). Alternatively, if this is necessary to keep the installed win32 package from messing things up during the build (how could it??), I could re-route that to use the installed ghc-pkg? But if I try setting GHC_PKG_INPLACE today, there's absolutely no change! The setting in fptools/mk/build.mk seems to be ignored now? Any helpful souls out there, who could lead me through the jungle of bewildering makefiles tomorrow (target date for feature completeness for the next release)? If not, I'll just drop the issue (those who reported the problem earlier seem to have given up? and Simon Thompson, who last ran into it, does now get acceptable performance from Hugs/HGL for his app). Lost, Claus

2 1

RE: GHCI Can't Find Module But GHC Can
by Simon Marlow 27 Jun '02

27 Jun '02

> The hmake parser specifically doesn't depend on layout. A > module doing > crazy stuff like > > module M where > import qualified {- " -} > N > > is perfectly fine, and all it takes to implement is the addition of a > `concatMap' over and above the version which expects the whole import > on one line. (FWIW, the hmake parser is ~200 lines, of which ~150 > lines deals with cpp, ~30 lines deals with comments, and ~20 lines > actually reads the imports.) But the point is you *can* construct valid modules which will confuse hmake (I just did). Our experience with GHC has told us, if nothing else, that the obscure cases always crop up eventually :-) > > But ghci already contains a Haskell parser - so it should > be much less > > work. > > Agreed, except that you don't want to fully-parse each module > twice, nor in general do you want to report all parse errors on the > import-gathering pass! Yes, that is indeed a problem. Cheers, Simon

1 0