- Glasgow-haskell-users

Data.List permutations
by Slavomir Kaslev 05 Aug '09

05 Aug '09

A friend mine, new to functional programming, was entertaining himself by writing different combinatorial algorithms in Haskell. He asked me for some help so I sent him my quick and dirty solutions for generating variations and permutations: > inter x [] = [[x]] > inter x yys@(y:ys) = [x:yys] ++ map (y:) (inter x ys) > perm [] = [[]] > perm (x:xs) = concatMap (inter x) (perm xs) > vari 0 _ = [[]] > vari _ [] = [] > vari k (x:xs) = concatMap (inter x) (vari (k-1) xs) ++ vari k xs After that I found out that nowadays there is a permutation function in the Data.List module: > permutations :: [a] -> [[a]] > permutations xs0 = xs0 : perms xs0 [] > where > perms [] _ = [] > perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is) > where interleave xs r = let (_,zs) = interleave' id xs r in zs > interleave' _ [] r = (ts, r) > interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r > in (y:us, f (t:y:us) : zs) I was surprised to find that not only my version is much simpler from the one in Data.List but it also performs better. Here are some numbers from my rather old ghc 6.8.1 running ubuntu on my box: *Main> length $ permutations [1..10] 3628800 (10.80 secs, 2391647384 bytes) *Main> length $ perm [1..10] 3628800 (8.58 secs, 3156902672 bytes) I would like to suggest to change the current implementation in Data.List with the simpler one. Also, it would be nice to add variations and combinations in the Data.List module. Cheers. -- Slavomir Kaslev

5 8

Working with GHC HEAD
by Antoine Latter 04 Aug '09

04 Aug '09

Folks, I was trying to see what GHC head was like, but I've run into a few snags compiling packages. My existing binary for cabal-install can install quite a few packages, but then starts giving me strange errors eventually: >>> $ cabal --version cabal-install version 0.6.2 using version 1.6.0.1 of the Cabal library $ ghc --version The Glorious Glasgow Haskell Compilation System, version 6.11.20090724 $ cabal install zlib Resolving dependencies... Configuring zlib-0.5.2.0... ghc-stage2: /home/alatter/.ghc/x86_64-linux-6.11.20090724/package.conf:6:163: parse error on input `Nothing' cabal: Error: some packages failed to install: zlib-0.5.2.0 failed during the configure step. The exception was: exit: ExitFailure 1 <<< If I then do: >>> $ mv /home/alatter/.ghc/x86_64-linux-6.11.20090724/package.conf /home/alatter/.ghc/x86_64-linux-6.11.20090724/package.conf.back $ cabal install zlib <<< Everything works great. After looking at the package.conf being complained about, the last line looks like so: >>> InstalledPackageInfo {package = PackageIdentifier {pkgName = PackageName "cpphs", pkgVersion = Version {versionBranch = [1,7], versionTags = []}}, license = LGPL Nothing, copyright = "2004-8, Malcolm Wallace", maintainer = "Malcolm Wallace <Malcolm.Wallace(a)cs.york.ac.uk>", author = ... <<< Not the license field of the package info - we have "license = LGPL Nothing, copright ...". I thought that maybe since GHC head ships with the new dev version of Cabal, I need the dev version of cabal-install to properly install packages. However cabal-install (and most of the things I want to test out) require the 'network' package, which doesn't build against GHC head (System.Posix.Internals doesn't exist, and the functionality that 'network' uses from there now lives in GHC.IO.* and is much changed). So a few things: - Should I expect the stable version of cabal-install built against GHC 6.10 to work for head? Are the errors I'm getting expected? - Does anyone have a version of 'network' which builds against GHC head? I could bludgeon in the new GHC.IO.FD.FD type myself, but I'd thought I'd ask around first. Thanks, Antoine

4 4

Current GHC core documentation.
by Richard Kelsall 04 Aug '09

04 Aug '09

This page http://www.haskell.org/ghc/documentation.html has a link to the September 2001 (Draft for GHC 5.02) document describing GHC Core (in what is for me user-hostile .ps.gz format.) And this page http://www.haskell.org/ghc/docs/latest/html/users_guide/ext-core.html promises an easier format PDF document, but the link is broken. I did eventually find the 1st April 2009 GHC 6.10 document here http://www.haskell.org/ghc/docs/6.10.2/html/ext-core/core.pdf and a bit on this page http://www.haskell.org/ghc/docs/latest/html/users_guide/options-debugging.h… about GHC core. I haven't read these yet, but could I ask whether they constitute the complete current documentation for GHC core? (I'm just curious to get a flavour of what core does.) Richard.

3 2

equivalent of EXPLAIN PLAN with GHC?
by Joshua Haberman 03 Aug '09

03 Aug '09

Hello, I'm quite new to Haskell, but experienced in other languages (C, Python, Ruby, SQL, etc). I am interested in Haskell because I've heard that the language is capable of lots of optimizations based on laziness, and I want to learn more about that. I dug in with Project Euler problem #1, and wrote: main = print (show (sum [x | x <- [3..999], x `mod` 3 == 0 || x `mod` 5 == 0])) So far so good, but I want to have some way of observing what optimizations GHC has performed. Most notably, in this example I want to know if the list was ever actually constructed in memory. The "sum" function only needs the elements one at a time, in order, so if Haskell and GHC are everything I've heard about them, I would fully expect the list construction to be optimized out. :) Unfortunately I was not able to see any way of examining ghc's output to determine whether it had performed this optimization. The C it produced with '-fvia-C -C' was totally unreadable -- it looked like something from the IOCCC. :( I couldn't find any way to match up any of the code it had generated with code I had written. My attempts to objdump the binaries was similarly unproductive. Is there any kind of intermediate form that a person can examine to see how their code is being optimized? Anything like EXPLAIN PLAN in SQL? It would make it much easier to understand the kinds of optimizations Haskell can perform. I'm not looking so much for profiling -- obvious this program is trivial and takes no time. I just want to better understand what kind of optimizations are possible given Haskell's language model. Thanks! Josh

4 7

Re to `optimization for list'
by Serge D. Mechveliani 02 Aug '09

02 Aug '09

Joshua Haberman <joshua(a)reverberate.org> writes on 2 Aug 2009 > Hello, I'm quite new to Haskell, but experienced in other languages (C, > Python, Ruby, SQL, etc). I am interested in Haskell because I've heard > that the language is capable of lots of optimizations based on laziness, > and I want to learn more about that. > > I dug in with Project Euler problem #1, and wrote: > > main = > print (show (sum [x | x <- [3..999], x `mod` 3 == 0 || x `mod` 5 == 0])) > > So far so good, but I want to have some way of observing what > optimizations GHC has performed. Most notably, in this example I want > to know if the list was ever actually constructed in memory. The "sum" > function only needs the elements one at a time, in order, so if Haskell > and GHC are everything I've heard about them, I would fully expect the > list construction to be optimized out. :) > [..] Your example is rather complex to start with, because `sum' has rather a complex definition in the Haskell library. Consider first a more pure example: main = putStr (shows (or' ys) "\n") where n = 10^8 ys = replicate n False or' :: [Bool] -> Bool or' [] = False or' (x: xs) = x || (or' xs) (the functions `||' (disjunction) and `replicate' are of the library). Compile it with ghc --make -O (for any occasion), and then, it will be evident that it takes a constant in n space (and stack) when running (run it like this: `./T +RTS -M1m -RTS' ). I think, this is not due to optimization but due to the very definition of evaluation in Haskell -- Head Normal Form. Compute this by hand: or' (replicate 9 False) = or' (False: (replicate 8 False)) = False || (or' (replicate 8 False)) = or' (replicate 8 False) = -- by definition of || ... or' [] = False. This is just the definition of evaluation in the Haskell language. In this example, the list under or' never expands further than for 2 members. Consider a more complex example (and more close to your example): main = putStr (shows (sum2 ys) "\n") -- sum' where n = 10^7 ys = [1 .. n] sum2 :: [Int] -> Int sum2 xs = sm xs 0 where sm [] s = s sm (x: xs) s = sm xs (s+x) sum' :: [Int] -> Int sum' [] = 0 sum' (x: xs) = x + (sum' xs) (the function [n .. m] is of the library). Compile it with ghc --make -O, and then, it will be evident that sum2 takes a constant in n space (and stack) when running (run it like this: `./T +RTS -M1m -RTS' ). Let us investigate this. Furst, compute this by hand with treating (+) as not of the library: sm [1 .. 4] 0 = sm (1:[2 .. 4]) 0 = sm [2 .. 4] (1+0) = sm (2: [3 .. 4]) (1+0) = sm [3 .. 4] (2+(1+0)) = ... It must accumulate an intermediate stack of size O(n). Why ghc-6.10.4 computes it in a constant space (and stack) ? The following is my guess. And let the Haskell experts correct me, please. In the Haskell-98 library it is defined that (+) is strict on the type of Int (right?). Therefore, the compiler optimizes (1+0) by replacing it immediately with 1. Taking in account that all other parts are computed lazily, the evaluation of the compiled program is like this: sm [1 .. 4] 0 = sm (1:[2 .. 4]) 0 = sm [2 .. 4] (1+0) = sm [2 .. 4] 1 = sm (2: [3 .. 4]) 1 = sm [3 .. 4] (2+1) = sm [3 .. 4] 3 = ... So, it is the result of combining of the evaluation definition with a certain compiler's optimization related to the strictness info for Int.(+). Right? As to sum', it still takes O(n) space -- in ghc-6.10.4. I think, this is because it is difficult for a compiler to guess how strictness of Int.(+) may correlate to the definition of sum'. Probably, it needs some kind of inductive reasoning about sum' to optimize it (for example) into sum2. Right ? Regards, ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0

Attempted install on Mac OS X - recent versions - FAIL
by Phil Dennis 29 Jul '09

29 Jul '09

I am looking for some assistance with installing GHC on Mac OS X. If there is a more appropriate place for me to ask, please let me know. I have tried, with no luck so far, the 2 different binary distributions of 6.10.4 provided for the Mac on the haskell.org ghc download page (http://www.haskell.org/ghc/download_ghc_6_10_4.html#macosxintel) I have OS X version 10.5.7 with XCode version 3.1.2 installed. When I run the installer (GHC-6.10.4-i386.pkg) I get as far as the "Installation Type" screen with the following text displayed: "Click Install to perform a standard installation of this software for all users of this computer". However the 'Install' button is greyed out and cannot be clicked. The last entries in the installer log are as follows: Jul 29 00:03:29 phil-denniss-macbook-pro Installer[11740]: Glasgow Haskell Compiler Installation Log Jul 29 00:03:29 phil-denniss-macbook-pro Installer[11740]: Opened from: /Users/pjdennis/Downloads/GHC-6.10.4-i386.pkg Jul 29 00:03:30 phil-denniss-macbook-pro installdb[11743]: started (uid 96) Jul 29 00:03:30 phil-denniss-macbook-pro installdb[11743]: Opened receipt database on '/' with schema 17. Jul 29 00:03:36 phil-denniss-macbook-pro installdb[11743]: done. (0.003u + 0.003s) ALSO I tried the binary distribution (ghc-6.10.4-i386-apple-darwin.tar.bz2) which I extracted, and then ran ./configure, as instructed in the INSTALL file. After adding /Developer/usr/bin to the path (so that the configure script could find the 'ar' program) I now get the following error from the configure script: configure: error: C compiler cannot create executables See `config.log' for more details. I have pasted some of what looks relevant from config.log, below. Any help with either one of the install methods for OS X would be much appreciated. I am keen to get started trying out Haskell, instead of mucking with installers. Regards, Phil Dennis --------------------------------------------------------------- >From config.log configure:2298: found /Developer/usr/bin/gcc configure:2309: result: gcc configure:2547: checking for C compiler version configure:2554: gcc --version >&5 i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5490) Copyright (C) 2005 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. configure:2557: $? = 0 configure:2564: gcc -v >&5 Using built-in specs. Target: i686-apple-darwin9 Configured with: /var/tmp/gcc/gcc-5490~1/src/configure --disable-checking -enable-werror --prefix=/usr --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-transform-name=/^[cg][^.-]*$/s/$/-4.0/ --with-gxx-include-dir=/include/c+ +/4.0.0 --with-slibdir=/usr/lib --build=i686-apple-darwin9 --with-arch=apple --with-tune=generic --host=i686-apple-darwin9 --target=i686-apple-darwin9 Thread model: posix gcc version 4.0.1 (Apple Inc. build 5490) configure:2567: $? = 0 configure:2574: gcc -V >&5 gcc-4.0: argument to `-V' is missing configure:2577: $? = 1 configure:2600: checking for C compiler default output file name configure:2627: gcc conftest.c >&5 ld: library not found for -lcrt1.10.5.o collect2: ld returned 1 exit status configure:2630: $? = 1 configure:2668: result: configure: failed program was: | /* confdefs.h. */ | #define PACKAGE_NAME "" | #define PACKAGE_TARNAME "" | #define PACKAGE_VERSION "" | #define PACKAGE_STRING "" | #define PACKAGE_BUGREPORT "" | /* end confdefs.h. */ | | int | main () | { | | ; | return 0; | } configure:2675: error: C compiler cannot create executables See `config.log' for more details.

1 1

ANNOUNCE: GHC version 6.10.4
by Ian Lynagh 28 Jul '09

28 Jul '09

============================================================== The (Interactive) Glasgow Haskell Compiler -- version 6.10.4 ============================================================== The GHC Team is pleased to announce a new patchlevel release of GHC. This release contains a number of bugfixes relative to 6.10.3, so we recommend upgrading. Release notes are here: http://haskell.org/ghc/docs/6.10.4/html/users_guide/release-6-10-4.html How to get it ~~~~~~~~~~~~~ The easy way is to go to the web page, which should be self-explanatory: http://www.haskell.org/ghc/ We supply binary builds in the native package format for many platforms, and the source distribution is available from the same place. Packages will appear as they are built - if the package for your system isn't available yet, please try again later. Background ~~~~~~~~~~ Haskell is a standard lazy functional programming language; the current language version is Haskell 98, agreed in December 1998 and revised December 2002. GHC is a state-of-the-art programming suite for Haskell. Included is an optimising compiler generating good code for a variety of platforms, together with an interactive system for convenient, quick development. The distribution includes space and time profiling facilities, a large collection of libraries, and support for various language extensions, including concurrency, exceptions, and foreign language interfaces (C, whatever). GHC is distributed under a BSD-style open source license. A wide variety of Haskell related resources (tutorials, libraries, specifications, documentation, compilers, interpreters, references, contact information, links to research groups) are available from the Haskell home page (see below). On-line GHC-related resources ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Relevant URLs on the World-Wide Web: GHC home page http://www.haskell.org/ghc/ GHC developers' home page http://hackage.haskell.org/trac/ghc/ Haskell home page http://www.haskell.org/ Supported Platforms ~~~~~~~~~~~~~~~~~~~ The list of platforms we support, and the people responsible for them, is here: http://hackage.haskell.org/trac/ghc/wiki/Contributors Ports to other platforms are possible with varying degrees of difficulty. The Building Guide describes how to go about porting to a new platform: http://hackage.haskell.org/trac/ghc/wiki/Building Developers ~~~~~~~~~~ We welcome new contributors. Instructions on accessing our source code repository, and getting started with hacking on GHC, are available from the GHC's developer's site run by Trac: http://hackage.haskell.org/trac/ghc/ Mailing lists ~~~~~~~~~~~~~ We run mailing lists for GHC users and bug reports; to subscribe, use the web interfaces at http://www.haskell.org/mailman/listinfo/glasgow-haskell-users http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs There are several other haskell and ghc-related mailing lists on www.haskell.org; for the full list, see http://www.haskell.org/mailman/listinfo/ Some GHC developers hang out on #haskell on IRC, too: http://www.haskell.org/haskellwiki/IRC_channel Please report bugs using our bug tracking system. Instructions on reporting bugs can be found here: http://www.haskell.org/ghc/reportabug

6 26

[reiner.pope@gmail.com: [Haskell-cafe] SpecConstr difficulties]
by Don Stewart 28 Jul '09

28 Jul '09

Something for SimonPJ ----- Forwarded message from Reiner Pope <reiner.pope(a)gmail.com> ----- Date: Mon, 20 Jul 2009 22:09:09 +0930 From: Reiner Pope <reiner.pope(a)gmail.com> To: Haskell Cafe mailing list <haskell-cafe(a)haskell.org> Subject: [Haskell-cafe] SpecConstr difficulties Hi everyone, I've been having some trouble getting SpecConstr to work as I want it to. The following example (see end of email) came up in some code I was playing around with. The loops g1 and g2 both compute the same thing: the maximum element of the "list" (which has been fused away) of numbers from 1 to 10. Since 'maximum' is a foldl1 not a foldl, I use a strict Maybe type as an accumulator. The Maybe gets filled after the first element is seen, so the Maybe is a Just for almost the entire running of the loop. It would be good to have this recognised by SpecConstr, to create an optimised loop for the Just case. This does indeed happen for g1, but not for g2. My difficulty is that I am only able to produce code similar to g2, i.e. where the pattern matching is in a separate function, 'expose', because the 'expose' function is implemented in a type-class, like in stream-fusion. Is there some way to keep the SpecConstr while leaving the 'expose' as a separate function? Here is the code: > {-# LANGUAGE BangPatterns #-} > > module Test(ans1,ans2) where > > import Prelude hiding(Maybe(..)) > > data Maybe a = Just !a | Nothing > > Nothing `mapp` Just b = Just b > Just a `mapp` Just b = Just (max a b) > > ans1 = g1 Nothing (0::Int) > > g1 m !n = case m of > Nothing -> if n > 10 then m else g1 (m `mapp` Just n) (n+1) > Just x -> if n > 10 then m else g1 (m `mapp` Just n) (n+1) > > ans2 = g2 Nothing (0::Int) > > g2 m !n = expose m (if n > 10 then m else g2 (m `mapp` Just n) (n+1)) > expose Nothing b = b > expose (Just a) b = a `seq` b On a similar note, when I was having difficulties with this problem, I started to wonder if it would be possible to come up with a more direct way to tell GHC, "do SpecConstr on this variable". From reading the source code of the stream-fusion package, it seems that the current way of doing this is with 'expose' functions like I wrote below. Could we instead have a {-# SPECCONSTR #-} pragma, to be used on function arguments, like: foo {-# SPECCONSTR #-} x y {-# SPECCONSTR #-} z = ... This pragma should say to the GHC something like "ignore conditions H2, H5 and H6 of the SpecConstr paper, for this function and this argument". Cheers, Reiner _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ----- End forwarded message -----

3 2

can we bootstrap GHC 6.x?
by Shu Wu 26 Jul '09

26 Jul '09

Hi buddies. I've been looking for methods to bootstrap GHC 6.10 but with no luck. It seems GHC 5.0 is the last version that provides HC source for bootstrapping. I think, however, bootstrapping GHC above 6.x is still necessary. First, it will be easier to build GHC on a new platform, eg, OpenSolaris. By now I succeed building GHC 6.10.4 on OpenSolaris(x86), with the help of GHC 6.6 binary package for Solaris x86 by Christian Maeder. But that was a terrible procedure. I have to deal with bins and libs for two versions of GHC. Second, compiling GHC from strap is the only way to go into OpenSolaris' official package repository, since all packages for OpenSolaris are built by Source Juicer (http://jucr.opensolaris.org/home/) from pure source code, and there can't be any pre-installed GHC on Source Juicer Build Grid. Cheers, Wu Shu

3 2

Failed to bootstrap 6.10.4 with itself on Windows (MinGW)
by leledumbo 24 Jul '09

24 Jul '09

I've just installed 6.10.4 and try to rebuild a minimal version from source, but the rebuild process failed. It stops with message: Capability.c: error converting to pointer type on stage1. configure command: ./configure --prefix=/c/ghc CFLAGS=-O4 LDFLAGS=-s -- View this message in context: http://www.nabble.com/Failed-to-bootstrap-6.10.4-with-itself-on-Windows-%28… Sent from the Haskell - Glasgow-haskell-users mailing list archive at Nabble.com.

2 6