Re: [Haskell-cafe] ANN: unordered-containers - a new, faster hashing-based containers library
Hi, Am Mittwoch, den 23.02.2011, 20:06 -0500 schrieb wren ng thornton: On 2/23/11 4:42 PM, Sterling Clover wrote: A quick grep of some of my own source reveals that I've used M.size and S.size only to test for sizes equal to 1. So, for my purposes at least, an O(1) isSingleton operation would be just as useful as an O(1) size. I agree, a fast isSingleton function would cover a very common use case--- especially for set-like containers. would ghc’s rule system be strong enough to replace size m == 1 by isSingleton m? It would be nice if programmers get the advantage even when they did not notice that a isSingleton function is provided. Greetings, Joachim -- Joachim nomeata Breitner mail: m...@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: nome...@joachim-breitner.de | http://www.joachim-breitner.de/ Debian Developer: nome...@debian.org signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
The topic of HANSEI in Haskell does come up from time to time. In fact, there was a Haskell edition of the first version of Hansei: http://okmij.org/ftp/kakuritu/probM.hs It was written to see how the code would look in Haskell, and how memoization (inherent in lazy evaluation of GHC) may help. The code contains some of the tests from the HANSEI distribution. The experience showed that lazy evaluation hurts -- a lot. The problem is not in lack of seq -- adding seq would make things even worse. There is a bit of explanation at the end of probM.hs. The gist of the problem is that approximate inference (sampling, to be precise) trades space for time. The search tree is way too large to fit into memory. Therefore, it is better to recompute the values (the branches of the tree) than to keep storing them. That is precisely the opposite to the trade-off of lazy evaluation. The end result is attempting to allocate gigabytes (really!), even for toy problems. We can get around the problem by using thunks explicitly. But then we lose the remaining benefits of Haskell syntax (the ones that are left after we have to switch to the monadic notation). OCaml becomes quite compelling then. It must be stressed that laziness in general is _crucial_ for solving even moderately complex problems. However, the needed laziness is NOT of the kind provided by GHC. We need memoization specific to a possible world, rather than the one that affects all possible worlds. GHC gives only the latter. The sort of laziness needed for non-deterministic programming calls for first-class store. It can be emulated, albeit imperfectly, for example, as was described in the ICFP09 paper. Hansei uses a quite similar idea. Ideally first-class memory is provided as built-in, since it requires interaction with garbage collection. Greg Morrisett has written extensively on this topic and done a few implementations; see for example, http://www.eecs.harvard.edu/~greg/papers/jgmorris-callcs.ps Sadly, the topic has been forgotten. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Either instance of Monad?
I have the same problem with instances of Functor. For instance when I import Control.Applicative, to get the instance Functor ((-) a) I also have to import Control.Monad.Instances. 2011/2/23 Daniel Fischer daniel.is.fisc...@googlemail.com: On Wednesday 23 February 2011 14:14:46, Yves Parès wrote: The latest, I think : GHC 7.0.1, mtl-2.0.1.0, base-4.3.0.0 Hmm, that's exactly what I have. Weirder and weirder. For the moment, I'm out of ideas. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: unordered-containers - a new, faster hashing-based containers library
Gwern Branwen wrote: You could look at them yourself; I attached the files. Max Bolingbroke wrote: Frankly I am surprised how much size gets used. It seems that making it fast is more important than I thought. Johan Tibell wrote: IntMap (which shares data structure with HashMap) only hash O(n) size. I wonder if people avoid using IntMap because of this. Another common usage for Map is as a functional integer-indexed random access array. Once I implemented the standard algorithm for random shuffle of a list using Data.Map Int. It was much nicer than the STArray version, in my opinion. But when I tried switching to Data.IntMap, hoping to make it faster, I was devastatingly disappointed. Now I understand why. -Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: unordered-containers - a new, faster hashing-based containers library
On Wed, Feb 23, 2011 at 08:45:47AM +, Max Bolingbroke wrote: 3. Some map combining algorithms work more efficiently when one of their two arguments are smaller. For example, Data.Map.union is most efficient for (bigmap `union` smallmap). If you don't care about which of the two input maps wins when they contain the same keys, you can improve constant factors by testing the size of the map input to size (in O(1)) and flipping the arguments if you got (smallmap `union` bigmap) instead of the desirable way round. This is a most unfortunate feature of Data.Map, forcing users to bend the logic of their application to suit the library. Ideally you'd want binary operations that are symmetric and associative performance-wise, freeing users to follow the structure of their problem domain. The documentation (and the original paper) doesn't quantify the gain for such unions, but hopefully it achieves the optimum: O(m log(n/m)), where m and n are the sizes of the smaller and larger trees respectively. Then building a tree costs O(n log(n)), regardless of the way you do it. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] GRIN and Urban Boquist's thesis
Hello, Does anyone have a current link to Urban Boquist's thesis? It's no longer available at the Chalmers site. On the LHC blog someone gave a link to a mirror[1], however that link is down for me as well. Thanks, John L. [1] http://lhc-compiler.blogspot.com/2010/06/mirroring-boquists-grin-papers.html#comments ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GRIN and Urban Boquist's thesis
On Thu, Feb 24, 2011 at 1:40 PM, John Lato jwl...@gmail.com wrote: Hello, Does anyone have a current link to Urban Boquist's thesis? It's no longer available at the Chalmers site. On the LHC blog someone gave a link to a mirror[1], however that link is down for me as well. Thanks, John L. [1] http://lhc-compiler.blogspot.com/2010/06/mirroring-boquists-grin-papers.html#comments You can find them here: http://mirror.seize.it/papers/ They will also be in the lhc repository once I restore it on code.haskell.org. -- Cheers, Lemmih ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] SMP parallelism gains inferior than expected
(Forwarding to haskell-cafe) Hi, I have a program that computes a matrix of Floats of m rows by n columns. Computing each Float is relatively expensive. Each line is completely independent of the others, so I thought I'd try some simple SMP parallelism on this code: myFun :: FilePath - IO () myFun fp = do fs - readDataDir fp let process f = readFile' f = parse printLine = putStrLn . foldr (\a b - show a ++ \t ++ b) runDiff l = [ [ diff x y | y - l ] | (x,i) - zip l (map getId fs), myFilter i ] ps - mapM process fs sequence_ [ printLine x | x - runDiff ps *`using` parList rdeepseq* ] So, I'm using parList to evaluate the rows in parallel, and fully evaluating each row. Here are the timings on a Dual Quad Core AMD 2378 @2.4 GHz, ghc-6.12.3, parallel-2.2.0.1: -N time (ms) none1m50 2 1m33 3 1m35 4 1m22 5 1m11 6 1m06 7 1m45 The increase at 7 is justified by the fact that there were two other processes running. I don't know how to justify the small increase at N3, though, but that doesn't matter too much. The problem is that I am not getting the gains I expected (halving at N2, a third at N3, etc.). Is this the best one can achieve with this implicit parallelism, or am I doing something wrong? In particular, is the way I'm printing the results at the end destroying potential parallel gains? Any insights on this are appreciated. Thanks, Pedro ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell platform installation failure on OS X 10.6.6 (intel)
Hello, Below is an experience report from Artem (cc'd) on a failed installation of Haskell platform on a Mac. OS: OS X 10.6.6 CPU: Intel Core i5 Platform downloaded from: http://lambda.haskell.org/hp-tmp/2010.2.0.0/haskell-platform-2010.2.0.0.i386.dmg Sequence of actions: Downloaded the file, mounted the image, ran Install new GHC, pressed OK until the following screen appeared http://i.imgur.com/GGdbg.png - there the Install button was disabled; pressing change install location did not help since only 1 option was available there, and it was already selected. After that, Artem tried to uninstall GHC, but unsuccessfully, since OS told that it was not installed. Then he tried to install the platform, and eventually got the following error around moving files into place: http://i.imgur.com/YHb22.png I've also heard somewhat similar problem reports on installing haskell-platform on OS X from other people (I myself don't have it) - like being unable to install it without first installing XCode, etc. Can anyone help resolve this issue? I'm sure this is not expected behavior. What further information would help find the cause? -- Eugene Kirpichov Senior Software Engineer, Mirantis Inc. http://www.mirantis.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GRIN and Urban Boquist's thesis
On Thu, Feb 24, 2011 at 1:16 PM, Lemmih lem...@gmail.com wrote: On Thu, Feb 24, 2011 at 1:40 PM, John Lato jwl...@gmail.com wrote: Hello, Does anyone have a current link to Urban Boquist's thesis? It's no longer available at the Chalmers site. On the LHC blog someone gave a link to a mirror[1], however that link is down for me as well. Thanks, John L. [1] http://lhc-compiler.blogspot.com/2010/06/mirroring-boquists-grin-papers.html#comments You can find them here: http://mirror.seize.it/papers/ They will also be in the lhc repository once I restore it on code.haskell.org. Thanks, Lemmih. That's exactly what I was looking for. John L. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell platform installation failure on OS X 10.6.6 (intel)
Hello, Usually this is because XCode is not installed. I believe the README states that this is a dependency for the install process. I opened a ticket with GHC HQ a while ago re: making this scenario friendlier for users. G. On Thu, Feb 24, 2011 at 3:41 PM, Eugene Kirpichov ekirpic...@gmail.com wrote: Hello, Below is an experience report from Artem (cc'd) on a failed installation of Haskell platform on a Mac. OS: OS X 10.6.6 CPU: Intel Core i5 Platform downloaded from: http://lambda.haskell.org/hp-tmp/2010.2.0.0/haskell-platform-2010.2.0.0.i386.dmg Sequence of actions: Downloaded the file, mounted the image, ran Install new GHC, pressed OK until the following screen appeared http://i.imgur.com/GGdbg.png - there the Install button was disabled; pressing change install location did not help since only 1 option was available there, and it was already selected. After that, Artem tried to uninstall GHC, but unsuccessfully, since OS told that it was not installed. Then he tried to install the platform, and eventually got the following error around moving files into place: http://i.imgur.com/YHb22.png I've also heard somewhat similar problem reports on installing haskell-platform on OS X from other people (I myself don't have it) - like being unable to install it without first installing XCode, etc. Can anyone help resolve this issue? I'm sure this is not expected behavior. What further information would help find the cause? -- Eugene Kirpichov Senior Software Engineer, Mirantis Inc. http://www.mirantis.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Gregory Collins g...@gregorycollins.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell platform installation failure on OS X 10.6.6 (intel)
Thanks Gregory, Indeed xcode was not installed - however I wonder, why is it a dependency? It seems quite a heavyweight thing to require for installing Haskell, and this requirement may very well be a good reason to *not* install it... Could you please point me to the ticket you opened? I was not able to google it. 2011/2/24 Gregory Collins g...@gregorycollins.net: Hello, Usually this is because XCode is not installed. I believe the README states that this is a dependency for the install process. I opened a ticket with GHC HQ a while ago re: making this scenario friendlier for users. G. On Thu, Feb 24, 2011 at 3:41 PM, Eugene Kirpichov ekirpic...@gmail.com wrote: Hello, Below is an experience report from Artem (cc'd) on a failed installation of Haskell platform on a Mac. OS: OS X 10.6.6 CPU: Intel Core i5 Platform downloaded from: http://lambda.haskell.org/hp-tmp/2010.2.0.0/haskell-platform-2010.2.0.0.i386.dmg Sequence of actions: Downloaded the file, mounted the image, ran Install new GHC, pressed OK until the following screen appeared http://i.imgur.com/GGdbg.png - there the Install button was disabled; pressing change install location did not help since only 1 option was available there, and it was already selected. After that, Artem tried to uninstall GHC, but unsuccessfully, since OS told that it was not installed. Then he tried to install the platform, and eventually got the following error around moving files into place: http://i.imgur.com/YHb22.png I've also heard somewhat similar problem reports on installing haskell-platform on OS X from other people (I myself don't have it) - like being unable to install it without first installing XCode, etc. Can anyone help resolve this issue? I'm sure this is not expected behavior. What further information would help find the cause? -- Eugene Kirpichov Senior Software Engineer, Mirantis Inc. http://www.mirantis.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Gregory Collins g...@gregorycollins.net -- Eugene Kirpichov Senior Software Engineer, Mirantis Inc. http://www.mirantis.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] darcs hacking sprint #6 (March, April, or May 2011)
Hello Haskellers! We are starting to organising the next Darcs Hacking Sprint, most likely in Paris in this spring. If you fancy a weekend of hacking Haskell on a really neat real world project, come join us! If you'd like to attend, please add yourself to http://wiki.darcs.net/Sprints/2011-04 . We will fix the date by March 1st, and there's only about 10+ spaces left, so sign up now! If you want to know what is exactly a Darcs Sprint, have a look at: http://wiki.darcs.net/Sprints http://blog.darcs.net/search/label/sprints The event is open to everybody, even if you're new to Darcs or to Haskell. We have an ample supply of enthusiasm and ProbablyEasy bugs to help you get started. See http://wiki.darcs.net/Recruitment for some ideas and also have a look at http://wiki.darcs.net/Development to see how to start coding on Darcs. Looking forward to see you! Guillaume and Eric -- Eric Kow http://www.nltg.brighton.ac.uk/home/Eric.Kow For a faster response, try +44 (0)1273 64 2905 or xmpp:ko...@jabber.fr (Jabber or Google Talk only) signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
On 24/02/2011 09:30, o...@okmij.org wrote: The sort of laziness needed for non-deterministic programming calls for first-class store. It can be emulated, albeit *imperfectly*, for example, as was described in the ICFP09 paper. What do you mean by imperfectly? Do you think implementing 'probM' with 'share' would lead to the same performance problems you experienced in probM.hs? Ideally first-class memory is provided as built-in, since it requires interaction with garbage collection. Greg Morrisett has written extensively on this topic and done a few implementations; see for example, http://www.eecs.harvard.edu/~greg/papers/jgmorris-callcs.ps ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Terminal library : which ?
What terminal library you will recomedn? Requirements: crossplatform (win/lin), with direct (i.e. with line/column number pair) cursor positioning and possybly direct symbol output. MUST provide function to get terminal dimensions. (could not find one). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
Arnaud Clère arnaud.cl...@free.fr wrote in article ik64e9$j6a$1...@dough.gmane.org in gmane.comp.lang.haskell.cafe: On 24/02/2011 09:30, o...@okmij.org wrote: The sort of laziness needed for non-deterministic programming calls for first-class store. It can be emulated, albeit *imperfectly*, for example, as was described in the ICFP09 paper. What do you mean by imperfectly? I think Oleg meant that, because the garbage collector only understands the native store and not our emulation of first-class stores, cells of a first-class store that are no longer referenced will nevertheless not be garbage-collected until the store itself is garbage-collected. What we need is a way to tell the garbage collector that the store reference and the cell reference are both needed to access the data so the data can be garbage-collected as soon as *either* the store reference *or the cell reference* is. (Analogy from the capabilities literature: the key and the lock are both needed to open the door so the door can be garbage-collected as soon as either the key or the lock is.) Any thoughts on how to achieve that? Do you think implementing 'probM' with 'share' would lead to the same performance problems you experienced in probM.hs? No, implementing probM with share would be like what OCaml HANSEI currently does, except in monadic notation rather than direct style. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 1st graffitiist: QUESTION AUTHORITY! 2nd graffitiist: Why? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
Leon Smith leon.p.sm...@gmail.com wrote in article AANLkTikF6EX4U+uTwNcrdFZPj-ijTWb74o2W_RJMGOe=@mail.gmail.com in gmane.comp.lang.haskell.cafe: On Wed, Feb 23, 2011 at 10:52 AM, Chung-chieh Shan ccs...@cs.rutgers.edu wrote: Mostly we preferred (as do the domain experts we target) to write probabilistic models in direct style rather than monadic style. Haskell's laziness doesn't help -- in fact, to avoid running out of memory, we'd have to defeat that memoization by sprinkling () - throughout the types. I don't think that () - is even guaranteed to work... That's quite true. Then again, it's not guaranteed that () - is needed for good memory usage. We just need a sufficiently smart compiler! -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 1st graffitiist: QUESTION AUTHORITY! 2nd graffitiist: Why? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell-Cafe Digest, Vol 90, Issue 48
Another common usage for Map is as a functional integer-indexed random access array. Once I implemented the standard algorithm for random shuffle of a list using Data.Map Int. It was much nicer than the STArray version, in my opinion. But when I tried switching to Data.IntMap, hoping to make it faster, I was devastatingly disappointed. Now I understand why. A couple thoughts: If you're going to provide an isSingleton method, provide getSingleton :: IntMap m - Maybe (Int, a) which is trivial based on the current implementation. For my TrieMap package, I've been working on my WordMap implementation herehttp://hackage.haskell.org/packages/archive/TrieMap/3.0.1/doc/html/src/Data-TrieMap-WordMap.html. (Using Words as keys makes my life easier, and it doesn't take too much work to write a wrapper that provides an order-preserving bijection from Int to Word.) It provides O(1) size, but its design reflects my willingness to trade memory and code size for speed. ;) Louis Wasserman wasserman.lo...@gmail.com http://profiles.google.com/wasserman.louis ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GRIN and Urban Boquist's thesis
2011/2/24 Lemmih lem...@gmail.com: They will also be in the lhc repository once I restore it on code.haskell.org. Lemmih, while you're here, what's the status of LHC? It's an interesting project but we haven't heard much from you lately. David ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Fun with the ST monad
OK, so I had a function that looks like transform :: [Word8] - [Word16] It works nicely, but I'd like to use mutable state inside. No problem! Use the ST monad. Something like transform :: [Word8] - [Word16] transform xs = runST (work xs) where work :: [Word8] - ST s [Word16] Ah, yes, well there is one *small* problem... If you do that, the function becomes too strict. The input list is being read from disk by lazy I/O. With the original implementation, the input file gets read at the same time as the output file is written. But runST returns nothing until the *entire* input has been compressed. So writing to disk doesn't start until the entire file has been slurped up into memory. Anybody have any hints on how to get around this? My first thought was to break the ST computation into several seperate pieces. But, /by design/, you cannot do this. And here's why: main = do let r = runST $ newSTRef 0 let x = runST $ n - readSTRef r; writeSTRef r (n+1); return n let y = runST $ n - readSTRef r; writeSTRef r (n*2); return n print x print y Now what the hell does this print out? Because it appears, logically, that it ought to vary depending on the order in which x and y are accessed - a clear violation of referential integrity. Fortunately of course, by a clever dodge, this code doesn't actually type-check. That's great, because it has undefined semantics. But it's also a problem, since it's exactly the sort of thing I'd like to do. Come to think of it, how the heck does lazy I/O manage this trick? How come accessing the elements of the list in the wrong order doesn't cause the wrong data to end up in each cell, if each cell is just using unsafePerformIO to read the next byte from a normal file handle? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GRIN and Urban Boquist's thesis
On Thu, Feb 24, 2011 at 9:36 PM, David Waern david.wa...@gmail.com wrote: 2011/2/24 Lemmih lem...@gmail.com: They will also be in the lhc repository once I restore it on code.haskell.org. Lemmih, while you're here, what's the status of LHC? It's an interesting project but we haven't heard much from you lately. Yeah, I've been out of commission for way too long due to college preparation and stuff. There's good news, however. For the last few weeks I've been working nearly full-time on adding garbage collector support to the backend. It is my hope that the work is interesting enough to be published somewhere. Feel free to skip this paragraph if you're not interested in garbage collection. Presently, nearly all Haskell compilers use some form of a shadow stack to implement garbage collection. This has two major drawbacks: * Managing the shadow stack adds overhead (roughly measured to around %62 in the case of UHC). * Forcing objects down on the shadow stack inhibits many optimizations. Instead of using a shadow shack, Boquist used a method that was specialized to the GRIN object model and it didn't have any of these drawbacks. I plan on generalizing said method so it works with any object model. Hopefully I'll be able to show that you can keep track of roots without incurring any overhead on the mutator. -- Cheers, Lemmih ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
On Thu, Feb 24, 2011 at 12:57 PM, Chung-chieh Shan ccs...@cs.rutgers.edu wrote: Arnaud Clère arnaud.cl...@free.fr wrote in article ik64e9$j6a$1...@dough.gmane.org in gmane.comp.lang.haskell.cafe: On 24/02/2011 09:30, o...@okmij.org wrote: The sort of laziness needed for non-deterministic programming calls for first-class store. It can be emulated, albeit *imperfectly*, for example, as was described in the ICFP09 paper. What do you mean by imperfectly? I think Oleg meant that, because the garbage collector only understands the native store and not our emulation of first-class stores, cells of a first-class store that are no longer referenced will nevertheless not be garbage-collected until the store itself is garbage-collected. What we need is a way to tell the garbage collector that the store reference and the cell reference are both needed to access the data so the data can be garbage-collected as soon as *either* the store reference *or the cell reference* is. (Analogy from the capabilities literature: the key and the lock are both needed to open the door so the door can be garbage-collected as soon as either the key or the lock is.) Any thoughts on how to achieve that? Here's a weak cell which is a candidate for GC as soon as either the cell or the key is lost: http://hpaste.org/44280/weak_ref_needing_both_halves The implementation is GHC specific, as far as I know. I don't know if it's exactly what you're looking for, but the idea could be adapted towards some other purpose. Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fun with the ST monad
Anybody have any hints on how to get around this? Use a lazy state monad? That's not going to work. It still needs to read the input to determine which monadic action comes next, and hence what the final result will be. So whether it forces the result or not, it still has to scan the entire input before it can generate any output. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fun with the ST monad
On Thu, Feb 24, 2011 at 2:42 PM, Andrew Coppin andrewcop...@btinternet.comwrote: Anybody have any hints on how to get around this? Use a lazy state monad? That's not going to work. It still needs to read the input to determine which monadic action comes next, and hence what the final result will be. So whether it forces the result or not, it still has to scan the entire input before it can generate any output. From the sound of it, you want some kind of lazy IO, driven/generated by a state monad. Check out the safe-lazy-io. I've never used it, but the announcement is pretty convincing. http://www.haskell.org/pipermail/haskell/2009-March/021133.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: unordered-containers - a new, faster hashing-based containers library
On 2/23/11 8:06 PM, wren ng thornton wrote: On 2/23/11 4:42 PM, Sterling Clover wrote: A quick grep of some of my own source reveals that I've used M.size and S.size only to test for sizes equal to 1. So, for my purposes at least, an O(1) isSingleton operation would be just as useful as an O(1) size. I agree, a fast isSingleton function would cover a very common use case--- especially for set-like containers. On reflection, in order to handle all the comparisons of size to some small constant, it would be better to have two functions: one for comparing the size of a collection against a boundary condition, and one for comparing the size of two collections. That is, you should add analogues of the functions in Data.List.Extras.LazyLength[1]. The lazy boundary condition function is O(min(m,n)) where m is the size of the boundary and n is the size of the collection. For detecting singletons, doubletons, etc, this reduces to O(1) though there may be a constant factor hit vs dedicated isSingleton/isDoubleton/et functions. It would be a slight difference that diminishes as m increases, but it could be worth benchmarking... Similarly, the lazy comparative size function is O(min(m,n)) where m and n are the sizes of the two collections. This is always less than the O(m)+O(n) of taking the sizes individually[2], but it's remarkably less when one of the collections is known to be much smaller than the other (even if you don't know which is which). [1] http://hackage.haskell.org/packages/archive/list-extras/0.4.0.1/doc/html/Data-List-Extras-LazyLength.html [2] The O(m)+O(n) can be parallelized to yield O(max(m,n)) but that's still greater than O(min(m,n)). With some form of chunked-lazy natural numbers you may be able to get the parallel version to approach O(max(m,n)) and then get into a battle of constant factors. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: unordered-containers - a new, faster hashing-based containers library
On 2/24/11 3:05 AM, Joachim Breitner wrote: Hi, Am Mittwoch, den 23.02.2011, 20:06 -0500 schrieb wren ng thornton: On 2/23/11 4:42 PM, Sterling Clover wrote: A quick grep of some of my own source reveals that I've used M.size and S.size only to test for sizes equal to 1. So, for my purposes at least, an O(1) isSingleton operation would be just as useful as an O(1) size. I agree, a fast isSingleton function would cover a very common use case--- especially for set-like containers. would ghc’s rule system be strong enough to replace size m == 1 by isSingleton m? It would be nice if programmers get the advantage even when they did not notice that a isSingleton function is provided. Not really. I mean, yes, you could use rules for that; but it would be fragile and susceptible to breakage due to refactoring. Since maps are finite, you shouldn't get any changes in the domain semantics (i.e., I believe that whether you hit bottom or not cannot change based on whether rules fire), but you could get asymptotic changes (since size is O(n) times whatever loop you're in) and you can get memory leak changes as well (depending on whether CSE fires or not). For me, allowing that much semantic variability based on whether rules fire or not is unacceptable. This is why I disabled the rewrite rules in Data.List.Extras.LazyLength[1] (which, granted, is even worse since infinite lists means that you can get domain semantic differences as well). I'd rather advocate for having smart/lazy size comparison functions like Data.List.LazyLength offers, advertising them well, and then relying on users to say what they mean. [1] http://hackage.haskell.org/packages/archive/list-extras/0.4.0.1/doc/html/Data-List-Extras-LazyLength.html -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fun with the ST monad
On 2/24/11 3:45 PM, Andrew Coppin wrote:
OK, so I had a function that looks like
transform :: [Word8] - [Word16]
It works nicely, but I'd like to use mutable state inside. No problem!
Use the ST monad. Something like
transform :: [Word8] - [Word16]
transform xs = runST (work xs)
where
work :: [Word8] - ST s [Word16]
Ah, yes, well there is one *small* problem... If you do that, the
function becomes too strict.
Given only this specification, the problem is overconstrained, which is
why you get too much strictness. That is, your types are too general to
allow you to do what you want (e.g., they allow the first Word16 to
depend on the last Word8). What is it that transform is supposed to do?
As for figuring out how to do it, first consider the following:
-- | @fix (PreList a) == [a]@ modulo extra bottoms.
type PreList a b = Maybe (a,b)
fmap_PreList :: (b - c) - PreList a b - PreList a c
fmap_PreList f Nothing = Nothing
fmap_PreList f (Just(a,b)) = Just (a, f b)
enlist :: PreList a [a] - [a]
enlist Nothing = []
enlist (Just (x,xs)) = x:xs
prelist :: [a] - PreList a [a]
prelist [] = Nothing
prelist (x:xs) = Just (x,xs)
-- | Monadic version of @Data.List.unfoldr@.
unfoldM :: (Monad m) = (b - m (PreList a b)) - (b - m [a])
unfoldM coalgM b = do
m - coalgM b
case m of
Nothing - return []
Just (a,b') - (a:) `liftM` unfoldM coalgM b'
Assuming that we can generate the elements of [Word16] incrementally,
then this function almost gives us what we need. The problem is that
even though the (a:) part is pure by the time we reach it, we can't see
that fact because of the liftM pushing it down into the monad again. To
put this a different way, consider the following distributive law:
distList :: (Monad m) = m (PreList a (m [a])) - m [a]
distList mx_mxs = do
maybe_x_mxs - mx_mxs
case maybe_x_mxs of
Nothing - return []
Just (x,mxs) - (x:) `liftM` mxs
{- N.B.,
unfoldM coalgM == distList . mfmap (unfoldM coalgM) . coalgM
where
mfmap :: (b - c) - m (PreList a b) - m (PreList a c)
mfmap = liftM . fmap_PreList
-}
In order to factor out the (a:) constructor we need to find some way of
*not* using distList in unfoldM. That way, the monadic effects
associated with the head of the list can be separated from the effects
associated with the tail of the list. Unfortunately, the obvious attempt
doesn't typecheck.
unfoldM'
:: (Monad m)
= (b - m (PreList a b))
- b - fix (\rec - m (PreList a rec))
unfoldM' coalgM = mfmap (unfoldM' coalgM) . coalgM
One problem is the fact that we can't write infinite types, though we
can get around that easily by using a newtype. The other problem is that
we need a function for running ST in a way that allows nested ST to be
run at some later time. Something like,
semirunST :: (Functor f)
= (forall s. ST s (f (ST s a))) - f (ST s a)
You can't do that in ST, since allowing this would mean that multiple
evaluations of the (ST s a) embedded in the result could return
different answers and communicate with one another[1]. However, if you
use another monad for encapsulating memory regions (e.g., ST RealWorld,
STM, IO) then you can probably get away with it.
But you're probably better off using State[2] instead of ST. Or
converting the whole thing to an iteratee-style computation which is
more explicit about the type of stream processing involved and thus what
kinds of laziness are possible.
[1] Though it would be safe to combine it with the newtype:
newtype Compose f g x = Compose (f (g x))
newtype Fix f = Fix (f (Fix f))
interleaveST :: (Functor f) = Fix (Compose (ST s) f) - Fix f
But given the API for ST, you can't define interleaveST in a way that
actually interleaves evaluation instead of using a distributive law for
pulling the (ST s) up over f and then running everything at once.
[2] State is easy:
runfoldState :: (b - State s (PreList a b)) - b - s - [a]
runfoldState coalgM = evalState . rec
where
rec b = do
m - coalgM b
case m of
Nothing - return []
Just (a,b') - do
s - get
return (a : evalState (rec b') s)
--
Live well,
~wren
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fun with the ST monad
On Feb 24, 2011, at 3:45 PM, Andrew Coppin wrote: OK, so I had a function that looks like transform :: [Word8] - [Word16] It works nicely, but I'd like to use mutable state inside. No problem! Use the ST monad. Something like transform :: [Word8] - [Word16] transform xs = runST (work xs) where work :: [Word8] - ST s [Word16] Ah, yes, well there is one *small* problem... If you do that, the function becomes too strict. unsafeInterleaveST? http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad-ST.html#v:unsafeInterleaveST --Sterl___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
On 2011-02-24T16:20:46-0600, Antoine Latter wrote: On Thu, Feb 24, 2011 at 12:57 PM, Chung-chieh Shan wrote: What we need is a way to tell the garbage collector that the store reference and the cell reference are both needed to access the data so the data can be garbage-collected as soon as *either* the store reference *or the cell reference* is. (Analogy from the capabilities literature: the key and the lock are both needed to open the door so the door can be garbage-collected as soon as either the key or the lock is.) Any thoughts on how to achieve that? Here's a weak cell which is a candidate for GC as soon as either the cell or the key is lost: http://hpaste.org/44280/weak_ref_needing_both_halves That's promising! The lock I have in mind would probably be a map from Int to weak pointers. I'm unfamiliar with System.Mem.Weak so I'll have to study this code further. What is addFinalizer lock (finalize wk) for? It seems wk doesn't have any finalizers to run. Thanks! -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 1st graffitiist: QUESTION AUTHORITY! 2nd graffitiist: Why? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
On Thu, Feb 24, 2011 at 10:15 PM, Chung-chieh Shan ccs...@cs.rutgers.edu wrote: On 2011-02-24T16:20:46-0600, Antoine Latter wrote: On Thu, Feb 24, 2011 at 12:57 PM, Chung-chieh Shan wrote: What we need is a way to tell the garbage collector that the store reference and the cell reference are both needed to access the data so the data can be garbage-collected as soon as *either* the store reference *or the cell reference* is. (Analogy from the capabilities literature: the key and the lock are both needed to open the door so the door can be garbage-collected as soon as either the key or the lock is.) Any thoughts on how to achieve that? Here's a weak cell which is a candidate for GC as soon as either the cell or the key is lost: http://hpaste.org/44280/weak_ref_needing_both_halves That's promising! The lock I have in mind would probably be a map from Int to weak pointers. I'm unfamiliar with System.Mem.Weak so I'll have to study this code further. What is addFinalizer lock (finalize wk) for? It seems wk doesn't have any finalizers to run. I was confused by GHC weak references for some time. GHC Weak references have the following parts: * a key * a value * finalizers attached to the key Setting up a weak reference to a value ties the value's liveness to the key's liveness (even if the weak reference itself is dead). Calling 'finalize' on the weak reference breaks the link between the weak reference, and runs the finalizers attached to the key. So here, we attach a finalizer to the Lock structure which then breaks the link between the key and the value (this doesn't break the link from the weak ref to the value, it simply stops the key from keeping the value alive). This might not be entirely safe in the face of some optimizations - finalizers on ForeignPtrs and MVars are odd, to work around other oddities that I don't yet grasp. Antoine Thanks! -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 1st graffitiist: QUESTION AUTHORITY! 2nd graffitiist: Why? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Auto elimination of MVars using a monad or monad transformer.
Hello, just like everyone else, I have a question about monads. I've read the tutorials, written one monad myself (not in this email), but I still consider myself a Haskell beginner. * Does GHC eliminate unneeded MVars during compilation? I'm expecting that it doesn't, as that would mean optimising away ForkIOs, which would be quite a thing to do. I've included example code below. * Is there a monad which allows their automatic elimination of MVars (or their creation only when necessary)? This would be similar to how the IO monad allows you to do purely functional things with a do block, using let. I've had a go at a lifting function, which wraps a pure function into an IO action which forever reads from one MVar and writes to another. What I'm looking for is some form of Monadic context in which many pure functions, MVar fillers and MVar consumers could be linked together, where only the necessary MVars remain (or were created) at compilation time. * Would this be a monad, or a monad transformer? * Can you specialise a monad transformer on a single base (in this case IO) so that you can use forkIO in the bind or return? Thanks, Chris. module Main ( main ) where import Control.Concurrent (forkIO, MVar, newEmptyMVar, putMVar, takeMVar, ThreadId, threadDelay) import Control.Monad (forever) stepA :: MVar String - IO () stepA boxa = forever $ do line - getLine putMVar boxa line stepB :: MVar String - IO () stepB boxb = forever $ do line - takeMVar boxb putStrLn line -- This simply wraps a string in brackets. bracket :: String - String bracket x = ( ++ x ++ ) -- This lifts a function into an action which forever performs the function -- between the two MVars given. lft :: (a - b) - MVar a - MVar b - IO () lft f c d = forever $ do x - takeMVar c putMVar d (f x) -- Just like C's main. main :: IO () main = do box - newEmptyMVar box2 - newEmptyMVar forkIO $ stepA box forkIO $ lft bracket box box2 forkIO $ stepB box2 threadDelay 1000 -- Sleep for at least 10 seconds before exiting. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUNCE: htime-0.1
Hello all, I kept being annoyed at the fact that Windows doesn't come with anything similar to the unix time utility, so I created a small Haskell program that does something similar. I thought this could perhaps be useful to others, so it's now available on Hackage: http://hackage.haskell.org/package/htime-0.1 Cheers, Pedro ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
