- Libraries - Haskell.org

Re: [nightly] 10-Aug-2008 build of HEAD oni386-unknown-linux(cam-02-unx.europe.corp.microsoft.com)
by Claus Reinke 11 Aug '08

11 Aug '08

>> 1. whatever I check in, the _whole_ thing has to build ok >> 2. if _my_ changes break someone else's code, _I_ have to fix that >> >> I'd suggest to interpret GHC+corelibs as a unit, and to apply rules >> 1 and 2. I was thinking of a unit of concern, not of any ownership or packaging (even the name "core"libs is ghc-specific: libraries ghc builds depends on). > But I do wish to point out that you cannot achieve both goals: "make > GHC and its dependencies into a single unit" and "share the libraries > with other compilers". At least, not without accepting some extra > work on the GHC side to maintain both illusions. Usually, the first time I hear about breakage affecting nhc98 or hugs is when you or Ross submit patches fixing said breakage!-) I think you are right: if the libraries are considered to be shared, then there are several such "units" which might affect each other via those shared libraries. Perhaps it helps to spell out the dependencies. In terms of changes in one place potentially having unwanted effects elsewhere, we have ghc <-> corelibs, ghc -> extralibs hugs -> corelibs+extralibs, ??hugslibs -> hugs nhc98 -> corelibs+extralibs, ??nhclibs -> nhc98 Actually, there are several forms of dependency: - changing the libraries cannot break hugs itself, but can make it unable to load or use any libraries, including the shared ones - changing (ghc-)corelibs can break ghc - changing nhc98-corelibs (which are?) can break nhc98 - changing hugs/nhc98/ghc can render each unable to load use some of the shared libraries (and others depending on these) Does that cover all cases? Changing ghc to make a library uncompilable by ghc only hurts ghc itself, but if the fix involves changing the library, the breakage might spread to hugs and nhc98. In principle, any changes to the shared libraries ought to be tested against all implementations sharing them. But as long as hugs and nhc98 are not part of a shared buildbot or validate system (neither of which are quite perfect even limited to ghc), breakage won't even be flagged for, let alone be fixed by submitters. While it is great that the two of you are always on the ball, is that something to be expected from all library maintainers all the time? Do all of them have to be subscribed to all of cvs-ghc, cvs-hugs, cvs-nhc98, and cvs-libraries, and fix any and all breakage arising in any and all situations, without their doing? Making it the submitters responsibility to look out for and fix any breakage caused by their patches simplifies the system and helps to ensure that any breakage resulting from changes is actually fixable (also in libraries outside the core+extralibs responsibility). In the time example, if ghc changes a warning flag to break the build, the immediate "fix" is to disable that new functionality, leaving it to the library maintainers to think about what the "proper" fix might be, possibly changing their code and re-enabling or leaving things as they are. Since those policies worked well in all projects where I have seen them used, I never really questioned them after I got my introduction. Is there a reason why they shouldn't or couldn't apply to the shared libraries and sharing haskell implementations? As I have mentioned, I'm worried that the move from extralibs to haskell platform will severe that responsibility, so library maintainers will have to become much more watchful for breakage affecting their packages, and more active in fixing such breakage. Claus

1 1

cabal-install
by Johannes Waldmann 11 Aug '08

11 Aug '08

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 "cabal install foo" seems a nice (in fact, indispensible) idea, but I don't see how to do the following with *one* command, for package "foo" and all its dependencies: * download and build as user, but install as root * also build and install haddockumentation for each of the packages Best regards, J.W. -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.4-svn0 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFIoChEDqiTJ5Q4dm8RAlM3AJwPSNROTgsheAZksP3I9WrRVD/xBwCgiI0S Tpmo/YRT4J3kEq9HjkTOzqY= =YWYl -----END PGP SIGNATURE-----

2 1

Library submission process for tweaks / bugfixes
by Scott Dillard 07 Aug '08

07 Aug '08

Hi, The library submission process wiki page says to create a ticket and post it to the list when proposing interface changes, but what is the proper method for submitting bug fixes and tweaks? This post is both an inquiry into the library patching process, and a friendly reminder of some outstanding submissions of mine. I'm watching http://darcs.haskell.org/packages/containers and I don't see anything related to the following : 1) There is an egregious and program-breaking typo, already patched and languishing on trac : http://hackage.haskell.org/trac/ghc/ticket/2359 . IMO that needs to be pushed right now. (milestone 6.10? Whats the point of a separate containers repo?) 2) Months ago I submitted a small patch to fix a too-restrictive type signature : http://www.haskell.org/pipermail/libraries/2008-May/009677.html 3) and another to improve performance of findMin / findMax : http://www.haskell.org/pipermail/libraries/2008-May/009687.html 4) and another, with the help of Bertram F, to improve the runtime complexity of fromAscList for IntSet and IntMap : http://www.haskell.org/pipermail/libraries/2008-May/009685.html I was hoping for some kind of binary response, "ok, pushed" or "no thanks." I have more of these kinds of changes that I plan on making. Whom do I email? Should I use all caps or what? :) Clearly its not sufficient to say "propose interface changes on trac, post bugfixes to the list" because either no one with push power is reading the list, or they get their "to do" items from trac only. Which is something of a problem, because a mailing list can't generate "to do" items. On trac someone with access rights flags a ticket, but nothing like that happens on the list. And even if the proper place for submissions is trac, there is no "libraries/containers" component listed, and many library submissions are flagged "Not GHC" which sounds to me like a dismissal. Is containers still "GHC"? As I understand it, containers is a free-standing project and this list is its collective maintainer. (Which I don't really see as a solution.) Scott

2 1

Functor instance of ReaderT
by Henning Thielemann 07 Aug '08

07 Aug '08

The Functor instance of ReaderT has the header: Monad m => Functor (ReaderT r m) I thought (Functor m) must be the appropriate constraint.

2 2

Where should cabal install to by default?
by Duncan Coutts 06 Aug '08

06 Aug '08

Hi folks, cabal-install is supposed to make things simpler for users, especially new users. It's partly successful at that currently. Many users do not know ghc-pkg even exists for example (not that it was a design goal but it seems to be a consequence). On the other hand we're currently failing users by not making programs they install work by default. Currently cabal-install installs all binaries to ~/.cabal/bin by default. It does per-user installs by default and uses ~/.cabal as its prefix. Obviously ~/.cabal/bin is not on the $PATH, so users who install say, yi or whatever find that typing yi at the prompt does not do anything even though they just installed it. That's a failure on our part. It should work, and if we cannot make it work by default then we need to tell users what they need to do to make it work. So I'd like to discuss what defaults we should use. For reference, these are the features that are implemented right now that we have to play with: * We can do per-user or global installs (affects which package db we use but it also changes the default prefix) * We can set any --prefix we like * We can use versioned binaries (ie adding -$version suffixes) * We can add symlinks to binaries in some other directory * We can use a commend like sudo to do the install phase We can control all these features in the ~/.cabal/config file. When cabal-install is first run it creates a default ~/.cabal/config file. So the question is what default it should set and how we report failure cases to the user. We do not have to use the same defaults on every platform. If we can get away with it I think it's much nicer not to make it interactive. Here's a couple suggestions: For unix systems, do per-user installs to --prefix=~/.cabal but if ~/bin exists then add symlinks there. Or perhaps if ~/bin is not a convention on that unix platform (eg OSX) then do global installs by default to /usr/local and use sudo for the install phase (we know that OS X comes with sudo where as it may or may not on other unix systems). Duncan

8 12

A fancier Get monad or two (a la binary and binary-strict)
by Chris Kuklewicz 06 Aug '08

06 Aug '08

Summary: I have two new Get-like monads for binary data (byte-aligned) that also (*) Suspend parsing and request more import when reading past the end of data. It is possible to respond with Nothing to indicate the hard end of data. (*) Return failures instead of calling error (*) Offer lookAhead,lookAheadM,lookAheadE like Data.Binary.Get (*) Are BinaryParser instances from Data.Binary.Strict.Class (*) Are Monad Transformers (and thus MonadIO) (*) Are MonadError,Plus,Reader,Writer,State and Applicative,Alternative (*) They differ because one is also MonadCont while the other is simpler (*) Simplified Non-transformer versions (applied to Identity) are defined Note: Making the suspend/resume-with-more-input work efficiently with MonadError/Alternative is one improvement to binary-strict. Make callCC work with sane semantics at the same time was non-trivial. Long version and where to find the source: In the process of writing an implementation of google's protocol buffers, I used binary's Put monad and binary-strict's BinaryParser class (i.e. binary-strict's Incremental Get monad). The Get in the binary package works on Lazy ByteString (good for me) but tends to call "error" when unhappy, which was not ideal. The Incremental Get from the binary-strict package does not want to work on Lazy bytestrings (it can be adapted), but the internals hold onto data too long and obstruct garbage collection (this is how it appears to me when I read the code). So I have made a fancier Get monad that offers a large collection of features. I am announcing this in case other people might want to further adapt my solution for their own ends (or just use it outright). Removing feature from my code ought to be much easier than adding them was. The code itself is currently living in a few files inside the protocol-buffers project at http://darcs.haskell.org/packages/protocol-buffers/Text/ProtocolBuffers/ The files are "MyGet.hs" or "MyGetW.hs", there are two flavors. (The "testDepth" file is annotated test output from MyGetW's testDepth function). They depend on binary-strict, but this would be easy to comment out. They both contain code "lifted" from binary and "inspired" by binary-strict. MyGetW.hs is the version with a MonadCont instance. MyGet.hs has the (forall b.) to simplify the types and thus has no MonadCont instance. I have tested the code, but it is still quite new. I doubt I will have time to make a proper cabal release. I may see if the maintainers of the binary-strict or binary packages are interested in a fancier Get monad. Cheers, Chris K

4 10

Re: Proposal: add laziness to Data.Map / IntMap
by Scott Dillard 06 Aug '08

06 Aug '08

Hi Bertram Scott Dillard wrote: > > I think maybe you guys (Don and Andrew) are misunderstanding my proposal. > > The lazy/strict tradeoff is a subtle issue, and I'll be sure to re-read > > Okasaki's stuff with this in mind, but what I'm talking about here is not > a > > trade off. It's laziness "for free". Move the strictness annotations out > of > > the constructors and into the library functions using 'seq'. Laziness is > > exposed through _separate_ functions. > > It's not for free. When the compiler does a pattern match on the Bin > constructor, Bin sz kx x l r, it can no longer assume that l and r are > fully evaluated, so it has to add code to evaluate them in case they are > not. And in fact, this code will be needed if any of your proposed lazy > functions are added later. I have not checked whether this has a > measurable performance or code size impact. > > > So mapWithKey retains all semantics, including guarantees. > > Semantically the change is safe, agreed. You're right of course (hadn't thought about that) but I'd like to point out that Adrien Hey's AVL tree library is structured in the way I propose: A node's subtree fields are not marked strict, instead seq is used to force construction of the tree. I think it's generally faster than Data.Map, at least it's claimed to be so in the documentation. The trees are not built with the same algorithm, but if the use of seq instead of bangs does impose a significant overhead, then that speaks very highly to the AVL algorithm. This of course raises the question of why I don't just use that library. I'm checking it out, but it's quite a bit bigger than Data.Map. The thing I like about Data.Map is that it's relatively simple and I can see whats going on very quickly, enough to make modifications (which I'm about to do.) Reading Data.Tree.AVL is a more daunting task. Also, there's something to be said for "lazy by default." I don't see much difference between Data.List.map and Data.Map.map (for finite lists anyway) and so if laziness is the correct default for the former then it should also be for the latter. The current Data.Map.map is only half strict: it builds an entire tree and fills it with thunks. Better I think to either build the whole thing completely or build only what's needed. The current Data.Map.map is the worst of both, no laziness + heap burn. So I guess I'll start writing. Anyone have any good benchmarks? Which naming scheme is less ugly, Data.Map.mapWithKeyL or Data.Map.Lazy.mapWithKey? Any other suggestions would be appreciated. Scott

5 4

Proposal: add laziness to Data.Map / IntMap
by Scott Dillard 06 Aug '08

06 Aug '08

>Adrian Hey wrote: > > Using explicit seqs rather than strict data types is actually faster, > for reasons that are a bit of a mystery to me. I'm not sure what cost > Bertram is talking about, but AFAIK ghc uses the same info pointer > mechanism for all heap records, including unevaluated thunks (although > the info pointers will point to different things of course). But the > cost of pattern matching on *evaluated* AVL nodes should be independent > of strictness annotation AFAICS. Thanks for chiming in Adrian. Just to get started I removed the strictness annotations from the Data.Map Bin constructor, made no other changes, and ran a silly benchmark (at the end of this email). The version without bangs is actually faster than the version currently shipping. I get about 10.5 sec for the lazy version and 11.5 sec for the strict version (2.1Ghz Intel Core) I'll repeat that in bold for people just skimming this thread: __Removing Strictness Annotations Makes It Go Faster__ The reason I think is that the helper functions bin, join and balance already provide just enough strictness, as they need to inspect the size field. The strictness analyzer can then do its job. The case for IntMap is tricker, as there is no implicit strictness in the code so removing the bangs causes stack overflows. Still working on that one. Here are the benchmarks. The lazy version also evaluates "keySum dmap" slightly faster (repeated inserts) and its a tie for "keySum smap" (sequential inserts). I admit this benchmark is goofy, if you have a better one please share. Scott import qualified Data.Map as Map import Data.List as List n = 1000000 rkeys = [ (i*122789) `mod` 1006471 | i<-[0..] ] :: [Int] dkeys = map (`div`1000) rkeys :: [Int] skeys = [0..] :: [Int] shuffle (a:b:c:d:e:f:g:h:rest) = e:a:h:d:c:b:g:f: shuffle rest keySum = List.foldl' (+) 0 . Map.keys rmap = Map.fromList . take n . shuffle $ rkeys `zip` [0..] dmap = Map.fromList . take n . shuffle $ dkeys `zip` [0..] smap = Map.fromAscList . take n . shuffle $ skeys `zip` [0..] mix (x:xs) (y:ys) = x : y : mix xs ys mix _ [] = [] mix [] _ = [] rkeys2 = [ (i*122789) `mod` 1006471 | i<-[0..] ] :: [Int] rlooks = [ (i*122819) `mod` 1006471 | i<-[0..] ] :: [Int] rlook = List.foldl' (\k s -> case Map.lookup k rmap of Nothing -> s; Just x -> s+x) 0 (take n $ rkeys2 `mix` drop 1000 rlooks) main = print rlook -- or print (keySum dmap) or whatever

2 1

runCommand/waitForProcess don't respect text printing order when stdout is redirected
by Alfonso Acosta 05 Aug '08

05 Aug '08

Hi all, I'm running ghc 6.8.2 in OSX and Linux. The following program behaves as expected when run on a terminal. == module Main where import System.Process main = sequence $ replicate 3 command where command = do putStrLn "foo" waitForProcess =<< runCommand "echo echo" putStrLn "bar" == $ ghc --make Main.hs -o main $./main foo echo bar foo echo bar foo echo bar However, when stdout is redirected to a file, the order is no longer respected: $ ./main > output $ cat output echo echo echo foo bar foo bar foo bar Am I missing something or should I file a bug report? Thanks in advance, Fons

4 5

Proposal: add laziness to Data.Map / IntMap
by Scott Dillard 05 Aug '08

05 Aug '08

Hi, I found myself wanting a lazy version of Data.Map today, and by "lazy" I mean in the node-subtree pointers. I trust the library writers when they put strictness annotations in the fields of the tree nodes, so I'm wondering what the various implications of lazy subtrees are, beyond the obvious speed hit. Does this cause space leaks beyond what lazy value pointers can already cause? Can someone point me to some reading that discusses this? Anyway, I'm positing to libraries (rather than haskell-cafe) to gauge opinion about a possible rewrite of Data.Map and IntMap to remove strictness annotations (bangs) from the node constructors and move them into the functions (as seqs). "Rewrite" is maybe too strong of a word. "Significant patch" is more like it. It would involve only those functions that construct Bin values directly, which is not that many. Less than a days work, I think (yes that means I volunteer.) Semantics of everything remains unchanged, but it opens up the possibility for lazy versions of some functions. The most usefull result of this would be a lazy map (little m). Here's Data.Map.mapWithKey mapWithKey f Tip = Tip mapWithKey f (Bin sx kx x l r) = Bin sx kx (f kx x) (mapWithKey f l) (mapWithKey f r) De-banged and then restrictified, it would look like this mapWithKey f Tip = Tip mapWithKey f (Bin sx kx x l r) = seq l' $ seq r' $ Bin sx kx (f kx x) l' r' where l = (mapWithKey f l) r = (mapWithKey f r) Looking at the first version, clearly you see that when constructing a new map you should only have to pay for the sub trees that you actually use. If you perform only a handful of lookups then throw the new tree away, why build the whole thing? To further motivate, let me explain my use case. I have cyclical data structures (graphs, more or less) that I mutate frequently, so I store them in a Map, indexed by some Ord thing, lets say Int, so I'd have something like Map Int [Int] (but not that exactly, and nothing like Data.Graph). This is great for mutations because I can use backtracking, but for lookups it's a burden on both me and the cpu. So I memoize the thing into something like "data Node a = Node a [Node a]" I can do this memoization using Data.Map.mapWithKey, with the Nodes built therein referring back to the produced Map. But then, what if I only crawl a small portion of this cyclical network of Nodes? Why should I have to pay for the whole thing to be rebuilt? It defeats the purpose of the memoization, which is to amortize the cost of following edges in the mutable graph. The pro and con as I see it are: Pro - More flexible data structure Con - Code is more verbose (see Data.Tree.AVL) - Only a few (but important) functions can be made lazy To that last point, note that while mapWithKey can be made lazy for both Map and IntMap, only IntMap allows lazy filter and mapMaybe because it doesn't rebalance. But I'm wondering how much of the tree needs to be forced when rebalancing. Should be only O(log n), right? It also becomes important where the tree is sourced from. The source needs to produce the tree lazily. The regular definition of fromList (= foldr (uncurry insert) empty) admits no laziness, but maybe successive unions could if the sub-maps were nearly disjoint (a not-uncommon case I think.) Does anyone know if any benchmarking has been done to this end? Finally, I'll stress once more that the semantics of the functions currently exported would be unchanged. This would only allow new lazy versions, named something like mapWithKeyL or unionL. So what do you think? Too much for too little? Scott

4 4