- Libraries - Haskell.org

Proof that scanl' is fusion-safe
by David Feuer 25 Jul '14

25 Jul '14

This proof is horribly inefficient. I imagine it could be fixed by appealing to the universal property of foldr or something like that, but I don't have time to look at that right now, so I'll just show you what I have right now; I'm hoping someone will be willing to verify that I haven't made any major errors. scanl' :: (b -> a -> b) -> b -> [a] -> [b] scanl' f a bs = build $ \c n -> a `seq` a `c` foldr (\b g x -> let b' = f x b in b' `seq` (b' `c` g b')) (\b -> b `seq` n) bs a -- Inlining build in scanl' gives scanl' f a bs = a `seq` a : foldr (\b g x -> let b' = f x b in b' `seq` (b` : g b')) (\b -> b `seq` []) bs a foldr evil wrong (scanl' f a bs) = foldr evil wrong $ a `seq` a : foldr (\b g x -> let b' = f x b in b' `seq` (b` : g b')) (\b -> b `seq` []) bs a -- Call this e1 a bs =?= (\c n -> a `seq` a `c` foldr (\b g x -> let b' = f x b in b' `seq` (b' `c` g b')) (\b -> b `seq` n) bs a) evil wrong -- Call this e2 a bs -- Expanding the outer foldr of e1 one step: e1 a bs = a `seq` evil a (foldr evil wrong $ foldr (\b g x -> let b' = f x b in b' `seq` (b' : g b')) (\b -> b `seq` []) bs a) --Beta reduction of e2 gives e2 a bs = a `seq` a `evil` foldr (\b g x -> let b' = f x b in b' `seq` (b' `evil` g b')) (\b -> b `seq` wrong) bs a -- Now if a = _|_, these are clearly both _|_, so for the rest of all eternity, -- assume a /= _|_. This eliminates one `seq`: e1 a bs = evil a $ foldr evil wrong $ foldr (\b g x -> let b' = f x b in b' `seq` (b' : g b')) (\b -> b `seq` []) bs a e2 a bs = evil a $ foldr (\b g x -> let b' = f x b in b' `seq` (b' `evil` g b')) (\b -> b `seq` wrong) bs a -- We will work by induction on the structure of bs, assuming that bs = -- b1:b2:...:[] or b1:b2:...:_|_ I believe that the proof for the -- partially defined case will somehow magically cover the infinite -- case too by some general principle, but I don't know how that magic -- works. -- The base cases are kind of dull, so I'll start with the -- inductive case. Assume that e1 bs = e2 bs e1 a (q:bs) = evil a $ foldr evil wrong $ foldr (\b g x -> let b' = f x b in b' `seq` (b' : g b')) (\b -> b `seq` []) (q:bs) a = evil a $ foldr evil wrong $ (\b1 g1 x1 -> let b1' = f x1 b1 in b1' `seq` (b1' : g1 b1')) q (foldr (\b g x -> let b' = f x b in b' `seq` (b' : g b')) (\b -> b `seq` []) bs) a = evil a $ foldr evil wrong $ (\g1 x1 -> let b1' = f x1 q in b1' `seq` (b1' : g1 b1')) (foldr (\b g x -> let b' = f x b in b' `seq` (b' : g b')) (\b -> b `seq` []) bs) a = evil a $ foldr evil wrong $ (let b1' = f a q in b1' `seq` (b1' : (foldr (\b g x -> let b' = f x b in b' `seq` (b' : g b')) (\b -> b `seq` []) bs) b1' -- Since foldr is strict in its list argument, we can move the first `seq` outward: = evil a $ let b1' = f a q in b1' `seq` foldr evil wrong $ (b1' : (foldr (\b g x -> let b' = f x b in b' `seq` (b' : g b')) (\b -> b `seq` []) bs) b1' = evil a $ let b1' = f a q in b1' `seq` evil b1' (foldr evil wrong $ (foldr (\b g x -> let b' = f x b in b' `seq` (b' : g b')) (\b -> b `seq` []) bs) b1') = evil a $ let b1' = f a q in b1' `seq` e1 b1' bs e2 a (q:bs) = evil a $ foldr (\b g x -> let b' = f x b in b' `seq` (b' `evil` g b')) (\b -> b `seq` wrong) (q:bs) a = evil a $ (\b1 g1 x1 -> let b1' = f x1 b1 in b1' `seq` (b1' `evil` g1 b1')) q (foldr (\b g x -> let b' = f x b in b' `seq` (b' `evil` g b')) (\b -> b `seq` wrong) bs) a = evil a $ let b1' = f a q in b1' `seq` (evil b1' (foldr (\b g x -> let b' = f x b in b' `seq` (b' `evil` g b')) (\b -> b `seq` wrong) bs) b1') = evil a $ let b1' = f a q in b1' `seq` e2 b1' bs scanl' f a bs = a `seq` a : foldr (\b g x -> (let b' = f x b in b' `seq` (b` : g b'))) (\b -> b `seq` []) bs a -- The first base case is bs = _|_ e1 _|_ = evil a $ foldr evil wrong $ foldr (\b g x -> (let b' = f x b in b' `seq` (b' : g b'))) (\b -> b `seq` []) _|_ a -- Since foldr is strict in its list argument, this reduces to e1 _|_ = evil a $ foldr evil wrong $ _|_ a = evil a (_|_ a) = evil a _|_ -- Next we look at e2 _|_ e2 _|_ = evil a $ foldr (\b g x -> (let b' = f x b in b' `seq` (b' `evil` g b'))) (\b -> b `seq` wrong) _|_ a = evil a (_|_ a) = evil a _|_ -- The second base case is bs = []. e1 [] = evil a $ foldr evil wrong $ foldr (\b g x -> (let b' = f x b in b' `seq` (b' : g b'))) (\b -> b `seq` []) [] a = evil a $ foldr evil wrong $ (\b -> b `seq` []) a = evil a $ foldr evil wrong (a `seq` []) -- Since we haven't reached the end of all eternity yet, a /= _|_ e1 [] = evil a $ foldr evil wrong [] = evil a wrong e2 [] = evil a $ foldr (\b g x -> (let b' = f x b in b' `seq` (b' `evil` g b'))) (\b -> b `seq` wrong) [] a = evil a $ (\b -> b `seq` wrong) a = evil a (a `seq` wrong) = evil a wrong -- Eternity passes so slowly!

1 0

At long last: 2014.2.0.0 Release Candidate 1
by Mark Lentczner 25 Jul '14

25 Jul '14

*Even I find it hard to believe that it's finally here!* *I'm happy to announce the RC1 release of Haskell Platform 2014.2.0.0.* You can find builds for Windows (32bit and 64bit), Mac (64bit), as well as a source tarball, and a tag in the repo: - source tarball: haskell-platform-2014.2.0.0-RC1.tar.gz <http://www.ozonehouse.com/mark/platform/haskell-platform-2014.2.0.0-RC1.tar…> - source repo: https://github.com/haskell/haskell-platform/tree/2014.2.0.0-RC1 - windows 32bit: HaskellPlatform-2014.2.0.0-i386-RC1-setup.exe <http://www.ozonehouse.com/mark/platform/HaskellPlatform-2014.2.0.0-i386-RC1…> - windows 64bit: HaskellPlatform-2014.2.0.0-x86_64-RC1-setup.exe <http://www.ozonehouse.com/mark/platform/HaskellPlatform-2014.2.0.0-x86_64-R…> - os x 64bit: Haskell Platform 2014.2.0.0 64bit RC1.signed.pkg <http://www.ozonehouse.com/mark/platform/Haskell%20Platform%202014.2.0.0%206…> - travis-ci build: 20 <https://travis-ci.org/haskell/haskell-platform/builds/30723884> *Notes:* General - Built with the new shake based build system - cgi package not included as it doesn't build under 7.8, and no word from the maintainer in quite some time - hscolour is included as a tool, mostly as it is used to build the platform itself on win and mac... but we should probably officially decide to include it - the haskell-platform package itself is not in these releases... not sure if we actually need it as it doesn't contain anything other than dependencies. Windows - The Haskell Platform now provides a native Windows 64-bit installation (haskell-platform issue #54 <https://github.com/haskell/haskell-platform/issues/54>) - All included packages built without --enable-split-objs (GHC 7.8 FAQ <https://ghc.haskell.org/trac/ghc/wiki/GHC-7.8-FAQ#Cabal>) - All included packages built without --enable-shared (GHC ticket #8228 <https://ghc.haskell.org/trac/ghc/ticket/8228>) - All html document links are relative and everything links nicely together now, including the master index and cross-package links - If other Haskell Platform installations are detected during the installation of Haskell Platform 2014.2.0.0, a warning is displayed to the user that this is not recommended since problems will arise due to how the PATH is used in many cases to find ancillary build tools - Using ghci to build an executable that links against a DLL may result in numerous warnings about symbols (GHC ticket #9297 <https://ghc.haskell.org/trac/ghc/ticket/9297>) - On Windows 64-bit, some unneeded python files are included (GHC ticket #9014 <https://ghc.haskell.org/trac/ghc/ticket/9014>) - The Haskell Platform for Windows, both 32-bit and 64-bit, now includes an updated version of the OpenGL Utility Toolkit (GLUT) from the FreeGLUT project, utilizing the pre-built distribution from http://www.transmissionzero.co.uk/software/freeglut-devel/ with the MinGW build (freeglut-MinGW-2.8.1-1.mp.zip). (haskell-platform issue #81 <https://github.com/haskell/haskell-platform/issues/81>) Mac OS X - Distributed with a build of 7.8.3 that differs from the released bindist in two ways: a) it was built split-objs for smaller resulting executables, b) it includes Cabal-1.18.1.4 which fixes a particularly nasty problem with haddock, -XCPP, and clang based systems. This ghc-7.8.3 bindist is available as well: - ghc-7.8.3-x86_64-apple-darwin-r3.tar.bz2 <http://www.ozonehouse.com/mark/platform/ghc-7.8.3-x86_64-apple-darwin-r3.ta…> - haddocks finally cross link between packages correctly - includes a new experimental activate-hs command that can switch between multiple installed versions of the platform - includes a slightly updated uninstall-hs command - the cabal command is wrapped to provide a smoother file layout on the Mac... the wrapping only updates the ~/.cabal/config file the first time you run it.. please pay attention to its output - if you have a custom config file, you'll want to update it, as Cabal's defaults have changed - works on 10.7 (tested), 10.8 (assumed!), 10.9 (tested) - both with gcc and clang based Xcode installs. (Next RC will support back to 10.6!) - 64bit only build this time... anyone still want the 32bit build? Source tarball - Quite some changes from last time - notably now includes the new build machinery, not the old. - The build machinery is well tested (see the travis-ci link above) from a repo... not tested much from a source repo - It isn't clear the source repo is of much interest... anyone need it? anyone need anything beyond the haskell-platform.cabal file in it? Timetable - These can "soak" amongst the intreped on these lists for 48 hours. - On Saturday, I'll release any needed updated RCs, and announce to a wider audience - End of next week (from my vacation, I'll point out), we'll declare success and ship. — Mark P.S.: sha256 sums for the reasonably wary: 860cba2d65bc1790ec3b8a0a62c8aaf19f5b18e9070aa1ec3c468b7c6ca82697 Haskell Platform 2014.2.0.0 64bit RC1.signed.pkg 8ca8a994334bf846ac6a41ada381c51634b2fce0d68dc70b2dadf59cb8748397 haskell-platform-2014.2.0.0-RC1.tar.gz b034e2daa595e0d3827860b062afca05f62df64434b0923559acc99bd82ef1e9 HaskellPlatform-2014.2.0.0-i386-RC1-setup.exe e31fe5e0cb9dca330e6f0c62ac49bf70b79f555bfe11e8f04c47739fef224145 HaskellPlatform-2014.2.0.0-x86_64-RC1-setup.exe 8e479d9dd504b1c603cd51f3be0fa57ecdc996e842d655e39d97faafff3c2d31 ghc-7.8.3-x86_64-apple-darwin-r3.tar.bz2

2 7

Enhancement: Default cabal to `-p` profiling enabled
by Andrew Pennebaker 24 Jul '14

24 Jul '14

I love GHC's profiling support, and like to use it to analyze the performance of my Haskell applications. However, profiling an application is difficult when it depends on any third-party libraries, as cabal doesn't include profiling information by default. Fortunately, cabal can reinstall a library with profiling support, with: cabal install --reinstall -p <library> Unfortunately, cabal is a bit of a simpleton, so this will fail unless that libraries dependencies are also installed with profiling enabled: cabal install --reinstall -p <libraryX> <libraryY> <libraryZ> ... For example, a user who wants to profile his die-rolling program must run: $ sudo apt-get install haskell-platform haskell-platform-doc haskell-platform-prof $ sudo cabal install --reinstall -p mwc-random rvar random-fu random-source mersenne-random-pure64 stateref flexible-defaults th-extras MonadPrompt math-functions erf vector-th-unbox monad-loops random-shuffle MonadRandom And that long list of packages must be slowly grown one at a time, starting from random-source, based on many attempts at running cabal install --reinstall -p ..., waiting several minutes for compilation to partially complete, and scrolling back up through the logs to track down which dependencies also neglected to compile with profiling enabled. It can take a while to get a list of this long, full dependency chain. It would be much easier if cabal simply enabled `-p` by default, so we didn't have to think about it. What do you think? -- Cheers, Andrew Pennebaker www.yellosoft.us

9 11

Is scanl' safe for foldr/build fusion?
by David Feuer 24 Jul '14

24 Jul '14

In a comment on trac #9345, nomeata proposed the implementation of Data.List.inits below. He indicates that the performance is very good, and wrote it in this fashion so it could fuse. My concern is that since seq is used in the argument to build, we need to make sure that fusion on the left will be safe. If I did the calculations right, this specifically requires that for all f, cons, nil, and bs, and all a≠_|_, the following "correct" expression e1 = a `cons` foldr cons nil $ foldr (\b g x -> (let b' = f x b in b' `seq` (b' : g b'))) (\b -> b `seq` []) bs a gives the same result as the fused expression e2 = a `cons` foldr (\b g x -> (let b' = f x b in b' `seq` (b' `cons` g b'))) (\b -> b `seq` nil) bs a I haven't been able to figure out how to prove this or give a counterexample, so far, but I have very little experience with such. myScanl' :: (b -> a -> b) -> b -> [a] -> [b] myScanl' f a bs = build $ \c n -> a `seq` a `c` foldr (\b g x -> (let b' = f x b in b' `seq` (b' `c` g b'))) (\b -> b `seq` n) bs a initsQ2 :: [a] -> [[a]] initsQ2 = map toListQ . myScanl' snocQ emptyQ

2 3

Re: At long last: 2014.2.0.0 Release Candidate 1
by Brandon Allbery 24 Jul '14

24 Jul '14

On Thu, Jul 24, 2014 at 8:09 AM, George Colpitts <george.colpitts(a)gmail.com> wrote: > Installed on the Mac, looks good, not sure if following is significant: > > ghc-pkg check > Warning: library-dirs: /opt/local/lib/ doesn't exist or isn't a directory > Warning: include-dirs: /opt/local/include/ doesn't exist or isn't a > directory > Warning: haddock-interfaces: > /Users/gcolpitts/Library/Haskell/ghc-7.8.3/lib/Cabal-1.20.0.1/doc/html/Cabal.haddock > doesn't exist or isn't a file > > did cabal install -j3 of threadscope, criterion, hlint, ghc-mod, > quickcheck, smallcheck and smartcheck > > Errrr. Whoever is making the Mac bindist should take care to avoid any MacPorts (or for that matter Homebrew) components slipping in to it; this will cause problems down the road. (The same goes for users; if you use MacPorts or Homebrew, wait for the Platform to be updated there and install from there, or you will end up with iconv etc. conflicts. Possibly a warning about this should be included in the install docs.) -- brandon s allbery kf8nh sine nomine associates allbery.b(a)gmail.com ballbery(a)sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

2 1

Re: At long last: 2014.2.0.0 Release Candidate 1
by Mark Lentczner 24 Jul '14

24 Jul '14

On Thu, Jul 24, 2014 at 5:09 AM, George Colpitts <george.colpitts(a)gmail.com> wrote: > Installed on the Mac, looks good, ... > did cabal install -j3 of threadscope, criterion, hlint, ghc-mod, > quickcheck, smallcheck and smartcheck > > That's all a good sign... not sure if following is significant: > > ghc-pkg check > Warning: library-dirs: /opt/local/lib/ doesn't exist or isn't a directory > Warning: include-dirs: /opt/local/include/ doesn't exist or isn't a > directory > Warning: haddock-interfaces: > /Users/gcolpitts/Library/Haskell/ghc-7.8.3/lib/Cabal-1.20.0.1/doc/html/Cabal.haddock > doesn't exist or isn't a file > > Something is amiss in how things ended up on your machine. I've just double checked the contents of the Mac distro and /opt doesn't appear in any of the package registrations. Furthermore, unless you built Cabal-1.20.0.1, it shouldn't be in your package db. My rough guess is that you've got a 7.8.3 compatible package db left over from a prior install somewhere. Can you e-mail me directly the output of: which cabal cabal --version which ghc ghc --version which ghc-pkg ghc-pkg --version ghc-pkg list ghc-pkg dump Thanks!

1 0

GHCi: Behave nicely on `-e`, like `ghc` and other programs
by Andrew Pennebaker 24 Jul '14

24 Jul '14

Like many programming language environments, GHC offers a handy `-e` option for evaluating an expression, then returning to the shell. $ ghc -e '2 + 2' 4 One would expect the interpreter, GHCi, to offer a similar flag, but it surprisingly rejects it. ghci -e '2 + 2' ghc: on the commandline: cannot use `--interactive' with `-e' Usage: For basic information, try the `--help' option. I think this behavior is quite unintuitive--when I pass `-e <exp>` to ghci, or pass `--interactive -e <exp>` to ghc, I expect the expression to be evaluated as the leading expression in an interactive interpreter session. Could we please tweak ghc like this to make it slightly more intuitive when these flags are used together? -- Cheers, Andrew Pennebaker www.yellosoft.us

2 1

Looking for help writing some GHC RULES
by David Feuer 24 Jul '14

24 Jul '14

I'm looking for some help writing some translate/untranslate rules to implement fusion for a couple of basic functions (the ones I'm looking at right now are takeWhile and scanr, but there may be others). I have a translation for takeWhile that seems to be at least decent, and one for scanr that is completely untested. I've never mucked about with GHC RULES, however, so I don't even know where to begin. Thanks in advance, David Feuer

5 5

Status of Haskell Platform 2014.2.0.0
by Mark Lentczner 22 Jul '14

22 Jul '14

The status is: *Good-to-Go!* The new-build branch of Haskell Platform is in pretty great shape: - One consistent build system using Shake - Builds source tarball - Builds linux distribution tarball - Builds Mac installer - Builds in one command line from a GHC bindist to end-user installer! - We have a running travis-ci instance <https://travis-ci.org/haskell/haskell-platform>* (currently red as we await a 7.8.3 bindist)* As soon as GHC 7.8.3 is out, I'll be running an alpha (or is this rc1?) or Haskell Platform (well, after I build the bindists for GHC for Mac... so it'll be a few hours on my puny MacBook Air...) *Shout out to: Yitzchak Gale, Bob Ipoloito, and Randy Polen for lots of help with the new build; Carter Schonwald for Mac and GHC build issues; Robert Lefkowitz for wiki and issue converstion (now on github!); Neil Mitchell for consultations on Shake.* The platform is now in a place that we'll be able to turn it much more quickly. This means we can track GHC release more closely, handle important library fixes when needed. And more importantly, spend time improving the platform itself, rather than sapping our energies build it! What you need to do now: - Check the version list in Release2014.hs <https://github.com/haskell/haskell-platform/blob/new-build/hptool/src/Relea…> - If you see a problem with the version of your library, let us know - If you are a packager for one of the linux distros - please try out the build and see how it works, and how it meshes with your packaging process for the distro. Come talk to me if you need help or brainstorming w.r.t. to the new-build. - If you have a Mac, you can try building the platform. *Build note: The repo is in sync with head of GHC 7.8 and we've been working with bindists we build ourselves off of head. If you want to try out the HP build with a 7.8.2 bindist, you'll need to change the version of base back to 4.7.0.0.* What you can do to help There are few aspects in progress, but none of these are show stoppers: - Windows installer using the new build being written by Randy Polen. (Existing windows build from the source tarball is still possible) - contact him if you'd like to help. - Platform website is being revamped by Erin Depew in concert with the general Haskell redesign by Chris Done - Platform website is template generated... but the pages haven't been templated much. if you're interested, e-mail and I can supply more details and hook up interested parties and Erin. - The travis-ci instance is enabled for Mac builds, but isn't configured to do them right. - There is a TO DO small task list in BUILD-NEW <https://github.com/haskell/haskell-platform/blob/new-build/notes/BUILD-NEW#…> in the repo - I'd like to see the As and Bs done. If you want to tackle one just do it and send me a merge request. - Many people have asked for a "server edition" of the platform w/o packages that don't make sense on a server (such as the OpenGL stuff). The new-build could easily be extended to do this now. - I'd love to see a version of Simon Hengel's Haskell Platform Versions Comparison Chart <http://sol.github.io/haskell-platform-versions-comparison-chart/> as part of the platform website. Now that it is templatized and the raw data is in Haskell, it should be possible. (I have prior year's data in the right format, just not checked in, ask me...) - It would be wonderful if we could get tests incorporated: Both running the tests that are part of the included libraries, and perhaps some "big integration tests" (is compiling Pandoc enough?). It would be great if these tests can be run "in-place" after the platform is built (for travis-ci), and if they could be run on the target machine (post-installation). — Mark "is it July already?" Lentczner

10 17

Let's make takeWhile fuse!
by David Feuer 22 Jul '14

22 Jul '14

`takeWhile` doesn't do the stream fusion thing. This definition seems to fix that, at least to a great extent. I don't know how to write the necessary rules to make this definition be used in the right places. takeWhile :: forall a . (a -> Bool) -> [a] -> [a] takeWhile p xs = build tw' where tw' :: forall b . (a -> b -> b) -> b -> b tw' kons knil = foldr go knil xs where go x rest | p x = x `kons` rest | otherwise = knil Tests (performed on 7.8.3, but the definition hasn't changed in HEAD): In the trivial main = print $ length $ takeWhile (< 10000000) [(1::Int) .. 20000000] it fused completely, allocating virtually nothing, whereas using Prelude.takeWhile (on 7.8.3) required a whopping 1,360,049,352 In the more complex main = print $ length $ filter (\x -> x `rem` 3 == 0) $ takeWhile (< 10000000) $ filter even [(1::Int) .. 20000000] it fused partially, allocating 266,716,048 bytes. The current GHC definition allocates 746,716,000 bytes in this case (strangely, less than it used for the simple test)! David Feuer

2 1