August 2008 - Libraries

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

Re: Libraries Digest, Vol 60, Issue 4
by John Lato 05 Aug '08

05 Aug '08

On Mon, Aug 4, 2008 at 5:26 AM, Duncan Coutts wrote: > > Oh, great. I didn't know OS X had a standard location for per-user > installs. That's excellent. So is there a preferred layout for those > dirs? I'm guessing there probably is. > >> * ~/.cabal is bad on Mac OS, too. Preferences ought to go into ~/ >> Library/Preferences/ ~/Library/Preferences should only be used if the .plist format is supported. In general, I agree with Brendan that unixy programs don't belong here, and I'm happy with .cabal. However, if you want to use the OSX dirs, I would think that most of the items in .cabal could be placed in ~/Library/Application Support/Cabal/. Unlike most other standard directories, this appears to be completely application-dependent. > > Ok. BTW, in that case we should probably fix > System.Directory.getAppUserDataDirectory to follow the system convention > on OSX. Currently it uses $HOME/.appname on all unix systems (and the > Windows convention on Windows). If necessary we may want to > split getAppUserDataDirectory into a variant for config and another for > data. > > Since cabal-install is a program should it still be > using ~/Library/Preferences/ or is there are > corresponding ~/Applications/Preferences/ ? Where would be > appropriate for cabal-install put its download cache and build logs? > All preferences are in ~/Library/Preferences/, in Apple's .plist format. There is no ~/Applications/Preferences/. Build logs should go in ~/Library/Logs/, either in a subdirectory or directly in this folder. There is a ~/Library/Caches/, but I believe that's reserved for the NSURL cache (accessed through Cocoa). > > It's less clear what we'd do on windows if we want versioned binaries > since there are no links. > I have personally ended up just copying the latest version of "appname-n.n.n" to "appname". Granted I've only done that on my own computer, never as part of an install process. John Lato

1 0

for old-time sakes:-) shouldn't deprecated libraries have DEPRECATED pragma?
by Claus Reinke 05 Aug '08

05 Aug '08

The haddocks for System.Time (suggestively located in old-time) state: This library is deprecated, please look at Data.Time in the time package instead. Yet, there is no DEPRECATED pragma for the module, so I actually missed all those other hints, and the improved Data.Time functionality, for a while at least. Claus

1 0

Unordered map
by Andrew Wagner 02 Aug '08

02 Aug '08

All, Forgive me if this has been brought up before, but I was just thinking about the fact that there's no Map structure in the standard library that doesn't pretty much require an Ord instance for its keys. I say "pretty much" because, while you can declare a Map with keys of a type that's not an Ord instance, you can't do hardly anything with it. E.g., you can't do an insert. Makes it kind of pointless. Now, I understand the fact that this is for efficiency purposes, but it does seem a bit inconsistent. Why allow the construction of a Map you can't do anything with? Here are two possible more consistent ways of handling this: Suppose I have some data structure that is inherently unordered, and I want to use it as a key into a Map. How would I get around this limitation on the client side? Well, the most obvious way is to create some nonsensical Ord instance, like compare _ _ = Eq. Is that the recommended solution? If so, we could create unordered versions of all the ordered methods that assume this 'ordering'. If not, what is the recommended way, and why not create unordered versions that use that? The other way to make the library more consistent, perhaps, would be to simply move the Ord requirement up to that data structure: that is, make it Ord k => Map k a, and then have a new data structure like UnorderedMap (or, to use a more standard term, Dictionary). Thoughts? Am I completely missing something?

8 12

proposal #2461: add Traversable generalizations of mapAccumL and mapAccumR
by Ross Paterson 02 Aug '08

02 Aug '08

The proposal is to add the following functions to Data.Traversable, generalizing the list versions in Data.List: -- |The 'mapAccumL' function behaves like a combination of 'fmap' -- and 'foldl'; it applies a function to each element of a structure, -- passing an accumulating parameter from left to right, and returning -- a final value of this accumulator together with the new structure. mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) -- |The 'mapAccumR' function behaves like a combination of 'fmap' -- and 'foldr'; it applies a function to each element of a structure, -- passing an accumulating parameter from right to left, and returning -- a final value of this accumulator together with the new structure. mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) These functions are handy for things like labelling trees, zipping, etc. Deadline: 3 weeks

7 12

Re: [Hs-Generics] Re: Owning SYB
by José Pedro Magalhães 02 Aug '08

02 Aug '08

Hello all, As Johan mentioned, here in Utrecht we are working on libraries for generic programming. We want to make it easier for people to use generic libraries, so we are packaging EMGM [1] and a library for generic programming for mutually recursive datatypes [2]. We intend to release these on Hackage soon (Summer vacations are delaying us a bit), along with useful generic applications (a zipper and a generic rewriting framework). Maintaining SYB fits well in this idea, and if no other natural maintainers volunteer, I (with some support from the other people at Utrecht) am happy to take it upon me. I probably won't do heavy development on the library, but including patches, and providing support is fine. We're also planning to maintain EMGM here in Utrecht, although we didn't develop that ourselves. Recently, (at least) Claus and Oleg have been posting interesting suggestions of improvements/modifications to SYB. Those should be further analyzed and discussed, and finally introduced (or not) in the library. The generic map for SYB, for instance, evolved from the "impossible to implement", through the "unsafe implementation", until the latest gmap2 as described by Oleg [3]. If further tests show this function behaves as expected, then it's clearly a good candidate for extending SYB. We should also rethink if other things previously deemed impossible remain so. Maintaining SYB, alongside with the other generic libraries, will require things such as: * Releasing packages in Hackage, properly documented with Haddock; * Updating such packages as necessary for new releases of GHC; * Writing examples of how to use the libraries (from a user perspective); * Writing testsuites, which are important for checking backwards compatibility of any changes; * Having an updated webpage linking to the library sources, documentation, possibly a bug tracker, etc. These are all things we plan to do for the libraries. Additionally, we could think of improving syb-with-class [4] in parallel with regular SYB. This is something to ask to its maintainer. Cheers, Pedro [1] http://books.google.com/books?id=OyY3ioMJRAsC&pg=PA199&sig=ACfU3U1nczeRAIjN… [2] http://www.cs.uu.nl/research/techreps/UU-CS-2008-019.html [3] http://www.haskell.org/pipermail/generics/2008-July/000362.html [4] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/syb-with-class

2 2