[Haskell-cafe] Upgrading Arch Linux Haskell Packages
Hi, Is there a way to manually upgrade Haskell packages in the aur repository of Arch Linux which were previously contributed automatically by arch-haskell? Or is there a batch upgrade planned for the near future? What is the mailing list for arch Best Regards, Cetin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [arch-haskell] Upgrading Arch Linux Haskell Packages
cetin.sert: Hi, Is there a way to manually upgrade Haskell packages in the aur repository of Arch Linux which were previously contributed automatically by arch-haskell? Or is there a batch upgrade planned for the near future? What is the mailing list for arch There's a batch upgrade, I've just been travelling! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [arch-haskell] Upgrading Arch Linux Haskell Packages
Don Stewart d...@galois.com writes: There's a batch upgrade, I've just been travelling! Yeah, let Don have a break for once! Oh, since you're here Don, how do I do ... ? ;-) -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Testing for statistical properties
Hi Greg, Assuming this is a one-dimensional distribtution, you should use a kolmogorov-smirnov test to test this: http://en.wikipedia.org/wiki/Kolmogorov-Smirnov_test I've implemented to the KS distribution from the CERN code linked in the wikipedia article, here: http://github.com/glutamate/samfun/blob/master/Math/Probably/KS.hs (warning, i wasn't able to verify the numbers coming out against anything so just check that it makes sense) So all you have to do is to find the maximal distance between your samples and the cumulative density function, multiply by the sqrt. of of the number of samples, and calculate kprob on that. I don't think you can do this in a Bayesian way because you can't enumerate all the other distributions your samples could come from? Tom On Thu, Jan 7, 2010 at 9:31 PM, Gregory Crosswhite gcr...@phys.washington.edu wrote: Hey everyone! I have some computations that satisfy statistical properties which I would like to test --- that is, the result of the computation is non-deterministic, but I want to check that it is sampling the distribution that it should be sampling. Is anyone aware of a Haskell library out there that does anything like this? Cheers, Greg ___ 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] space leaks and optimizations
Dear Haskellers, Recently I have been looking for a programming language that would be suitable for small scientific and recreational projects and palatable to a picky person like me. (I do theoretical physics and some math; I do not program very often.) Haskell and Clean look attractive from a mathematician's point of view and allow for very elegant solutions in some cases. I tried Clean first because it has a more efficient implementation and better array support. However, I am leaning toward Haskell since it has more libraries, larger community, and some nice features (e.g., the do notation). I thought it would be easier to avoid errors when programming in a pure functional language. Indeed, the Haskell type system is great and catches many errors. But in practice, I found it very difficult to write correct programs in Haskell! This is because my definition of correctness includes asymptotic complexity (time and space). I have pondered why Haskell is so prone to space leaks and whether this can be fixed. I posted a related message (describing a space leak caused by inlining) to Glasgow-haskell-users, http://www.haskell.org/pipermail/glasgow-haskell-users/2009-November/018063.html but apparently the GHC developers were busy preparing a new release. Perhaps on Haskell-cafe there are more people with some spare time; I would really appreciate your comments. So, there seem to be several reasons why controlling space usage is difficult: 1) The operational semantics of Haskell is not specified. That said, it seems that unoptimized programs behave in a predictable way if you follow the execution step by step. The Clean report explicitly says that the execution model is graph reduction; I believe that Haskell uses the same model. However, there are some subtleties, e.g., the tail call and selector optimizations. (I read about the selector optimization in Wadler's paper, http://homepages.inf.ed.ac.uk/wadler/topics/garbage-collection.html and saw it mentioned on the GHC development page. It's really nice and indispensable, but it seems to be missing from the user documentation. Is this the following description accurate? After the rhs of a lazy pattern like (a,b) = expression has been evaluated, the pattern does not take up any space, and the space occupied by a and b can be reclaimed independently.) There must be more subtleties. I imagine that a rigorous definition of operational semantics would be too complicated and impractical. But maybe an informal specification is better than nothing? Why people have not attempted to write it? 2) While each step is predictable, the overall behavior of a lazy program can be rather surprising. So one must be very careful. GHC provides two ways to control the evaluation order, seq and bang patterns, but I am not sure which of these (if any) is the right tool. Consider the following example (from the Real World Haskell book): mean :: [Double] - Double mean xs = sum / fromIntegral num where (num,sum) = foldl' f (0,0) xs :: (Int, Double) f (n,s) x = (n+1, s+x) Although it uses foldl', there is a space leak because Haskell tuples are not strict. There are two possible fixes: f (!n,!s) x = (n+1, s+x) or f (n,s) x = let n1=n+1; s1=s+x in n1 `seq` s1 `seq` (n1,s1) The first one is short, but less natural than the second one, where the offending thunks are suppressed on the spot. Unfortunately, the syntax is awkward; it would be nice to write something like f (n,s) x = (!n+1, !n+1) Well, I am becoming too grumpy, perhaps the bang patterns are fine. More important question: are there established practices to *avoid* space leaks rather than fixing them afterwards? 3) The standard library was not designed with space efficiency in mind; for example, there is sum but no sum'. 4) GHC does a pretty good job optimizing programs for speed, but compiling with the -O option can easily introduce a space leak. I have not encountered such problems with Clean, though my experience is very limited. Apparently, the Clean developers have disallowed some unsafe optimization, see e.g., this message: http://mailman.science.ru.nl/pipermail/clean-list/2009/004140.html I doubt that the Clean solution is 100% reliable because the compiler still uses strictness analysis, which can change the asymptotic space usage (usually for better, but sometimes for worse). So I wonder whether it would be feasible to identify a set of conservative optimizations that do not change the space or time usage more than by a constant factor. For example, the strictness analysis could be limited to fixed-size data. Or instead of strictness analysis, one could inline the top-level patterns of every function. Of course, that would make the optimization less efficient on the average, but predictability is more important. Best regards, Alexei ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANN: hakyll-0.4
Hello, I am announcing the release of hakyll-0.4. Hakyll is a static site generator library written Haskell. It is written in a very configurable way and uses an xmonad-like DSL for configuration. Notable changes since the last big release (0.1) include: - CSS compression - Dependency handling (aka. not generate everything again every time) - A simple http server for previewing your site - Speed improvements and bug fixes - Several specialized functions for dealing with dates, tags... - Abstraction of context manipulations - Some tutorials are added and documentation is mostly complete - Example sites were added More information can be found at http://jaspervdj.be/hakyll All feedback is welcome. Kind regards, Jasper Van der Jeugt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Typed Configuration Files
Dear Café, Neil Mitchell's cmdargs package [1] is pretty neat. It can be used to parse command-line arguments into a user-defined data structure. Is there something similar for parsing config files? There are a number of config file parsers on Hackage. But even the most sophisticated one I found, ConfigFile by John Goerzen [2], only yields primitive data like strings, booleans, and numbers. Did I overlook something? I'd like to write something like do fc - configFile ... ac - cmdArgs ... let conf = fc `mappend` ac where the type of `conf` is a user defined monoid. I found that the fez-conf package [3] provides a function `parseToArgs` which creates a list similar to the one returned by `System.getArgs` from a config file. Neil, if you would add a function to your cmdargs package that allows to specify the argument list, then one could reuse your machinery to create typed config data from config files too, right? Maybe along the lines of do args - parseToArgs $ readFile /my/conf conf - cmdArgsWithDefault args My Program [myMode] The new function `cmdArgsWithDefault` could require the return type to be a monoid in order to allow users to specify themselves how to deal with multiple options of the same kind. Would that be reasonable or is there a better alternative? Cheers, Sebastian [1] http://hackage.haskell.org/package/cmdargs [2] http://hackage.haskell.org/package/ConfigFile [3] http://hackage.haskell.org/package/fez-conf -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUNCE: SourceGraph-0.6.0.0 and Graphalyze-0.9.0.0
I'm pleased to announce the latest releases of SourceGraph [1] and Graphalyze [2]. [1]: http://hackage.haskell.org/package/SourceGraph [2]: http://hackage.haskell.org/package/Graphalyze SourceGraph is a program that performs static code analysis on Haskell projects on the by applying graph theoretic techniques to the project's call graph. Graphalyze is a library for analysing discrete data using graph theory, and as such performs the heavy lifting for SourceGraph. Sample analysis reports generated by SourceGraph are available at http://code.haskell.org/~ivanm/Sample_SourceGraph/SampleReports.html . I will also be demoing SourceGraph at PEPM [3] in Madrid on 19 January. [3]: http://www.program-transformation.org/PEPM10/ Changes since the previous version include: * Now supports implicitly exported entities (as requested by Curt Sampson). This includes instantiated class methods from other modules and functions, etc. that start with an underscore (see http://www.haskell.org/ghc/docs/latest/html/users_guide/options-sanity.html for more information). * All inaccessible entities are now reported, not just those that were root nodes in the call graph. * Edges are now colour-coded based upon whether they are part of a clique, cycle or a chain. * Level-based analyses: visualise how deep an entity is from those exported entities. * A re-done TODO that lists in detail what is planned for SourceGraph. * Lots of under-the-hood changes that don't sound as interesting as the above :-( -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Splitting a Hackage project (was ANN: Streaming Component Combinators 0.4)
I couldn't find any Hackage policy guideline on the appropriate balance between the package list size and package size, so I'll just ask the question. I have released the version 0.4 of my SCC package yesterday. In this particular release, there is at least one module that's nicely self-contained, providing useful functionality of its own, and not expected to evolve much: http://hackage.haskell.org/packages/archive/scc/0.4/doc/html/Control-Concurrent-Coroutine.html My question then is if I should split this module into a separate package or leave it where it is? If I split it out, what should I do about the ParallelizableMonad class in the module? class Monad m = ParallelizableMonad m where bindM2 :: (a - b - m c) - m a - m b - m c This class and its instances would again be something *usable* both outside the SCC package and outside the Control.Concurrent.Coroutine module. But would they be *useful* and would they be *used*? Should I split the class out into a Control.ParallelizableMonad package? I'm sure I'm not the only one with the same dilemma. It would be nice to have some written rules to follow on what belongs on Hackage as a separate package. Version 0.4 of Streaming Component Combinators, or SCC for short, has been released on Hackage. Get it at http://hackage.haskell.org/package/scc There isn't much new high-level functionality compared to the previous version, but the implementation has been heavily refactored and the foundations completely replaced. I'm particularly happy to have found a way to drop the ugly reliance on Data.Dynamic and to encode the required constraints in the type system instead. The foundation of streaming components in this version is the new Control.Concurrent.Coroutine module, whose main export is the monad transformer Coroutine. It can transform any monad into a suspendable, resumable, trampoline-style-runnable monad. Coroutines can be nested, which was the requirement for streaming and the main stumbling block for the implementation. The solution, worth at least 10 milliOlegs according to my estimate, was to parameterize the Coroutine with a functor that wraps the coroutine suspension, and to use nested functors for suspension from nested coroutines. The type system automatically figures out how many wrappings to apply to each suspension depending on how many intermediate coroutines it suspends. In other news is the project's Wiki page at http://trac.haskell.org/SCC/wiki/. It's still rudimentary, but growing. All feedback will be appreciated. ___ Haskell mailing list hask...@haskell.org http://www.haskell.org/mailman/listinfo/haskell ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUNCE: SourceGraph-0.6.0.1
I realised soon after I sent the announcement email that there was a bug in one of the new subtle features that I didn't list, namely the background shading of directories in import visualisation. As such, SourceGraph 0.6.0.1 contains this fix. There were also two other features in 0.6.0.0 that I forgot to mention: * SourceGraph will (well, should; I haven't managed to come across a situation where it occurs anyway) no longer throw a fit if Graphviz throws an error when visualising a graph; instead it will just put an error message into the generated report. * The generated Dot code is also saved in the SourceGraph/graphs/ subdirectory, so you can tweak the call graphs of your programs. Ivan Lazar Miljenovic ivan.miljeno...@gmail.com writes: I'm pleased to announce the latest releases of SourceGraph [1] and Graphalyze [2]. [1]: http://hackage.haskell.org/package/SourceGraph [2]: http://hackage.haskell.org/package/Graphalyze SourceGraph is a program that performs static code analysis on Haskell projects on the by applying graph theoretic techniques to the project's call graph. Graphalyze is a library for analysing discrete data using graph theory, and as such performs the heavy lifting for SourceGraph. Sample analysis reports generated by SourceGraph are available at http://code.haskell.org/~ivanm/Sample_SourceGraph/SampleReports.html . I will also be demoing SourceGraph at PEPM [3] in Madrid on 19 January. [3]: http://www.program-transformation.org/PEPM10/ Changes since the previous version include: * Now supports implicitly exported entities (as requested by Curt Sampson). This includes instantiated class methods from other modules and functions, etc. that start with an underscore (see http://www.haskell.org/ghc/docs/latest/html/users_guide/options-sanity.html for more information). * All inaccessible entities are now reported, not just those that were root nodes in the call graph. * Edges are now colour-coded based upon whether they are part of a clique, cycle or a chain. * Level-based analyses: visualise how deep an entity is from those exported entities. * A re-done TODO that lists in detail what is planned for SourceGraph. * Lots of under-the-hood changes that don't sound as interesting as the above :-( -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] space leaks and optimizations
2) While each step is predictable, the overall behavior of a lazy program can be rather surprising. So one must be very careful. GHC provides two ways to control the evaluation order, seq and bang patterns, but I am not sure which of these (if any) is the right tool. Consider the following example (from the Real World Haskell book): mean :: [Double] - Double mean xs = sum / fromIntegral num where (num,sum) = foldl' f (0,0) xs :: (Int, Double) f (n,s) x = (n+1, s+x) Although it uses foldl', there is a space leak because Haskell tuples are not strict. There are two possible fixes: f (!n,!s) x = (n+1, s+x) or f (n,s) x = let n1=n+1; s1=s+x in n1 `seq` s1 `seq` (n1,s1) The first one is short, but less natural than the second one, where the offending thunks are suppressed on the spot. Unfortunately, the syntax is awkward; it would be nice to write something like f (n,s) x = (!n+1, !n+1) Well, I am becoming too grumpy, perhaps the bang patterns are fine. More important question: are there established practices to *avoid* space leaks rather than fixing them afterwards? I believe the expectation is to learn to not be surprised in the areas where lazy or non-strict evaluation can be overused, and to learn all the advantages of non-strict evaluation vs strict, and the power it gives, such that an imperative programmer doesn't feel surprised or angry when things go wrong. I blogged about writing a long running service in Haskell that ran into problems with the lazy State monad, and lazy Data.Map, and I discussed how I had to force evaluations of everything to get the program under control. This wasn't for a hobby, this was for a production system. I believe I've a much better handle on strict vs non-strict than when I started the project, but I felt pretty lost for a while in the process of doing it. I was even using the Maybe monad with it's MonadPlus implementation to avoid using case statements around deconstruction, which I'm sure exacerbated some of my problem. However, since Haskell will evaluate the outer-most stuff first, the trick seems to be to find the point at which you *really* need the values computed, then tell Haskell to get on with it. You kind of have to have an explicit sequence point where all things need to be resolved, and you have to be able to see those in your code. Sometimes you can get away with only doing small pieces at a time. I had about the worst situation I've ever seen for data growth in my code. I had a pile of non-strict expressions, that were all dependencies for the next, running forever, and never getting evaluated except at asynchronous and user-controlled moments. If these expressions had been evaluated strictly, they would have taken up constant space, but since they were all thunks, I got linear data growth over time, until I blew up. Some advice I've gotten since then was to think about using case for strictness rather than explicitly using seq. Turns out case's pattern matching is pretty strict, and that you can often get by with that. I haven't spent a lot of time with core output, but my understanding is that it's all let and case. 3) The standard library was not designed with space efficiency in mind; for example, there is sum but no sum'. Actually I think that the standard library was designed to be consistent with the way the language is documented to behave. That is to say that it's non-strict by default everywhere it's possible to be so. Control.Monad.State selects Control.Monad.State.Lazy by default instead of Control.Monad.State.Strict, but both exist. Yes, in some cases there's no strict equivalent provided, but is writing a strict sum really a big problem? I think there's stricter folds included because they're not quite as trivial, but once you have a strict fold isn't strict sum pretty easy? I suppose the type of the contained element in the list could make a big difference in whether the strict fold is strict enough, but where do you stop providing strict versions of functions for people? It seems a line must be drawn somewhere, and the right solution is to properly educate Haskell programmer about both the power and drawbacks of non-strict evaluation, and when it's really necessary to turn things off. Giving examples is fine, but one must learn to see the patterns where there is a problem that could brew. Real World Haskell teaches us about the profiling tools that helped me uncover my problems. Best regards, Alexei ___ 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
Re: [Haskell-cafe] Typed Configuration Files
On Fri, Jan 8, 2010 at 12:53 PM, Sebastian Fischer s...@informatik.uni-kiel.de wrote: Dear Café, Neil Mitchell's cmdargs package [1] is pretty neat. It can be used to parse command-line arguments into a user-defined data structure. Is there something similar for parsing config files? If you write one I most certainly will use it! ;) Seriously, cmdargs is *brilliant*. It's also magic (to me). Implementing a config parser in a similar way would likely dispell the magic... if I only could find the time. /M -- Magnus Therning(OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Typed Configuration Files
Excerpts from Magnus Therning's message of Fri Jan 08 16:25:31 +0100 2010: On Fri, Jan 8, 2010 at 12:53 PM, Sebastian Fischer s...@informatik.uni-kiel.de wrote: Dear Café, Neil Mitchell's cmdargs package [1] is pretty neat. It can be used to parse command-line arguments into a user-defined data structure. Is there something similar for parsing config files? If you write one I most certainly will use it! ;) Seriously, cmdargs is *brilliant*. It's also magic (to me). Not only to you in fact it is black magic since it uses unsafePerformIO :( -- Nicolas Pouillard http://nicolaspouillard.fr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Typed Configuration Files
Hi, Seriously, cmdargs is *brilliant*. It's also magic (to me). Not only to you in fact it is black magic since it uses unsafePerformIO :( The problem isn't that it's black magic or that it uses unsafePerformIO - the problem is that it's horribly impure, so doesn't obey referential transparency. Unfortunately this in unavoidable with the way I wanted to write command line arguments... Thanks, Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Typed Configuration Files
Hello Sebastian, Friday, January 8, 2010, 3:53:53 PM, you wrote: Neil Mitchell's cmdargs package [1] is pretty neat. It can be used to parse command-line arguments into a user-defined data structure. Is there something similar for parsing config files? Lua language may be used to describe arbitrarily complex data structure and there is HsLua: http://www.haskell.org/haskellwiki/HsLua -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] telling ghc to run several jobs in parallel
Hi, I have to processors but ghc --make only uses one of them, even if some files could be compiled in parallel. Is there some option similar to the -j one of the make tool ? (I read the manual but didn't find it) Regards, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FASTER primes
Daniel Fischer daniel.is.fischer at web.de writes: Am Donnerstag 07 Januar 2010 11:43:44 schrieb Heinrich Apfelmus: Will Ness wrote: Hm? In my world view, there is only reduction to normal form and I don't see how allocate its own storage fits in there. Okasaki having shown something to that end would be new to me? Perhaps what was meant was storage must be allocated for each filter (which, however, seems trivial). I still contend that in case of nested filters, where each filter has only one consumer, even that isn't ultimately necessary (a chain of pointers could be formed). That's because there's no peeks, only pulls there. If the filters are used in merge situation, then there will be some peeks so current value must be somehow stored, though it's better to be made explicit and thus static (the place for it, I mean, instead of the rolling cons cell). Such implementation technique would prevent some extra gc. Then under merging these split pairs form a monoid, so can be rearranged in a tree. If you haven't seen it yet, it uses a different folding structure to your code, with a lower total cost of multiples production (estimated as Sum (1/p)*depth): correction: tfold f (x:y:z:xs) = (x `f` (y `f` z)) `f` tfold f (pairwise f xs) comps = tfold mergeSP $ pairwise mergeSP multips The idea being that each prime produces 1/p composites each turn and it takes time depth to trickle it to the top? Sounds reasonable, but remember that a prime p does not start to generate composites until the turn count has reached p^2, so it might occupy a place of low depth in the tree that is better spent on the previous primes. That might be why Daniel's structure is better: it plunges down faster than mine. treefold structure was: (2+4) + ( (4+8) + ( (8+16) + ( (16+32) + ( (32+64) + ... dpths: 3 4 4 5 5 66 77 8 daniel's: (2+(4+6)) + ( (8+(10+12)) + ( (14+(16+18)) + ( (20+(22+24)) + )) 3 5 5.4 6 7.8 7.9 8 9 9.5 9.6 10.7 10.8 primes () = 2:3:5:7:11:13:primes' where primes' = roll 17 wheel13 `minus` compos primes''' primes'' = 17:19:23:29:31:37:rollFrom 41 `minus` compos primes'' primes''' = 17:19:23:29:31:37:rollFrom 41 `minus` compos primes'' Haven't read through the whole thing yet. :) :) I thought there was a typo there. There isn't. BTW using the no-share switch isn't necessary if we just write it down twice with some variations, like primes''' = let (h,t)=span ( 17^2) roll 17 wheel13 in h++t `minus` compos primes'' As we've found out, compilers aren't _that_ smart yet. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] telling ghc to run several jobs in parallel
There is no such option yet, but there was some work recently on making GHC more amenable to doing jobs in parallel (from what I understand there's a global variable or two that makes it hard). Dan On Fri, Jan 8, 2010 at 6:33 PM, Paul Brauner paul.brau...@loria.fr wrote: Hi, I have to processors but ghc --make only uses one of them, even if some files could be compiled in parallel. Is there some option similar to the -j one of the make tool ? (I read the manual but didn't find it) Regards, Paul ___ 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] Re: FASTER primes
Daniel Fischer daniel.is.fischer at web.de writes:
The below code is now a well-behaved memory citizen (3MB for the 100
millionth prime, about the same as the PQ code). It still is considerably
slower than the PQ code.
In terms of MUT times as reported by +RTS -sstderr - as well as (MUT+GC)
times - (measured once for prime No. 5*10^5, 10^6, 2*10^6, 4*10^6, 10^7 to get
a rough tendency), it seems to scale a wee bit better than any of the other
tfold versions I created, but a little worse than the PQ versions.
The relation of MUT times isn't too bad, but the GC times are rather abysmal
(30-40%).
--
data People a = P { vips :: [a], dorks :: [a] }
celebrate :: a - People a - People a
celebrate x p = P (x:vips p) (dorks p)
primes :: forall a. Integral a = () - [a]
primes () = 2:3:5:7:11:13:primes'
where
primes' = roll 17 wheel13 `minus` compos primes'''
primes'' = 17:19:23:29:31:rollFrom 37 `minus` compos primes''
primes''' = 17:19:23:29:31:37:rollFrom 41 `minus` compos primes''
pmults :: a - People a
pmults p = case map (*p) (rollFrom p) of
(x:xs) - P [x] xs
multip :: [a] - [People a]
multip ps = map pmults ps
compos :: [a] - [a]
compos = vips . smartfold mergeSP . multip
smartfold f = tfold f . pairwise f
tfold f (a:b:c:xs) = (a `f` (b `f` c)) `f` smartfold f xs
pairwise f (x:y:ys) = f x y : pairwise f ys
mergeSP :: Integral a = People a - People a - People a
mergeSP p1@(P a _) p2 = P (a ++ vips mrgd) (dorks mrgd)
where
mrgd = spMerge (dorks p1) (vips p2) (dorks p2)
spMerge l1 [] l3 = P [] (merge l1 l3)
spMerge ~l1@(x:xs) l2@(y:ys) l3 = case compare x y of
LT - celebrate x (spMerge xs l2 l3)
EQ - celebrate x (spMerge xs ys l3)
GT - celebrate y (spMerge l1 ys l3)
--
Hi Daniel,
Is it so that you went back to my fold structure? Was it better for really big
numbers of primes?
I had the following for ages (well, at least two weeks) but I thought it was
slower and took more memory (that was _before_ the 'no-share' and 'feeder'
stuff). I can see the only difference in that you've re-written spMerge in a
tail-recursive style with explicitly deconstructed parts; mine was relying on
the compiler (8-L) to de-couple the two pipes and recognize that the second
just passes along the final result, unchanged.
The two versions seem to me to be _exactly_ operationally equivalent. All this
searching for the code better understood by the compiler is _*very*_
frustrating, as it doesn't reflect on the semantics of the code, or even the
operational semantics of the code. :-[
Weren't the P's supposed to disappear completely in the compiled code? Aren't
types just a _behavioral_ definitions??? Aren't we supposed to be able to
substitute equals for equals dammit??
Is this the state of our _best_ Haskell compiler
module Primes8 where
import Data.Monoid
data (Ord a) = SplitList a = P [a] [a]
instance (Ord a) = Monoid (SplitList a) where
mempty = P [] []
-- {x | x::SplitList a} form a monoid under mappend
mappend (P a b) ~(P c d) = let P bc b' = spMerge b c
in P (a ++ bc) (merge b' d)
where
spMerge :: (Ord a) = [a] - [a] - SplitList a
spMerge u@(x:xs) w@(y:ys) = case compare x y of
LT - P (x:c) d where (P c d) = spMerge xs w
EQ - P (x:c) d where (P c d) = spMerge xs ys
GT - P (y:c) d where (P c d) = spMerge u ys
spMerge u [] = P [] u
spMerge [] w = P [] w
mconcat ms = fold mappend (pairwise mappend ms)
where
fold f (a: ~(b: ~(c:xs)))
= (a `f` (b `f` c)) `f` fold f (pairwise f xs)
pairwise f (x:y:ys) = f x y:pairwise f ys
primes :: Integral a = () - [a]
primes () = 2:3:5:7:primes'
where
primes'= [11,13] ++ drop 2 (rollFrom 11) `minus` comps
mults = map (\p- P [p*p] [p*n | n- tail $ rollFrom p]) $ primes'
P comps _ = mconcat mults
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Testing for statistical properties
Thanks! I had reached the same conclusion, so I am glad to see that you already wrote code to do this for me. :-) There is a bug in the version that you posted, though: you missed one of the terms in the u 0.755 case, so the c2 constant goes completely unused. Here is my modified version of your function + bug fix, with some stylistic tweaks: computeKolmogorovProbability :: Double - Double computeKolmogorovProbability z | u 0.2 = 1 | u 0.755 = 1 - w * (exp(c1/v)+exp(c2/v)+exp(c3/v))/u | u 6.8116 = 2 * sum [ sign * exp(coef*v) | (sign,coef) - take (1 `max` round (3/u)) coefs ] | otherwise = 0 where u = abs z v = u*u w = 2.50662827 c1 = -pi**2/8 c2 = 9*c1 c3 = 25*c1 coefs = [(1,-2),(-1,-8),(1,-18),(-1,-32)] Cheers, Greg On Jan 8, 2010, at 2:59 AM, Tom Nielsen wrote: Hi Greg, Assuming this is a one-dimensional distribtution, you should use a kolmogorov-smirnov test to test this: http://en.wikipedia.org/wiki/Kolmogorov-Smirnov_test I've implemented to the KS distribution from the CERN code linked in the wikipedia article, here: http://github.com/glutamate/samfun/blob/master/Math/Probably/KS.hs (warning, i wasn't able to verify the numbers coming out against anything so just check that it makes sense) So all you have to do is to find the maximal distance between your samples and the cumulative density function, multiply by the sqrt. of of the number of samples, and calculate kprob on that. I don't think you can do this in a Bayesian way because you can't enumerate all the other distributions your samples could come from? Tom On Thu, Jan 7, 2010 at 9:31 PM, Gregory Crosswhite gcr...@phys.washington.edu wrote: Hey everyone! I have some computations that satisfy statistical properties which I would like to test --- that is, the result of the computation is non-deterministic, but I want to check that it is sampling the distribution that it should be sampling. Is anyone aware of a Haskell library out there that does anything like this? Cheers, Greg ___ 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] Re: FASTER primes
Daniel Fischer daniel.is.fischer at web.de writes:
roll = scanl (+)
wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:
4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel
wheel11 = res
where
snms = scanl (+) 11 (take 47 wheel)
nums = tail $ scanl (+) 11 (take 529 wheel)
cops = nums `minus` map (*11) snms
diffs = zipWith (-) (tail cops) cops
res = foldr (:) res diffs
wheel13 = res
where
snms = take 480 $ scanl (+) 13 wheel11
nums = take (480*13+1) . tail $ scanl (+) 13 wheel11
cops = nums `minus` map (*13) snms
diffs = zipWith (-) (tail cops) cops
res = foldr (:) res diffs
BTW have you seen my take on the faithful Euler's sieve? It shows another way
to look at the wheels, which for me was really the first time I really
understood what's going on there.
It also makes for easier wheel extention (IMO):
euler ks@(p:rs) = p : euler (rs `minus` map (*p) ks)
primes = euler [2..]
The essence of Euler's sieve is the wheel: after each step we're left with
lists of non-multiples of the preceding primes:
primes = euler $ listFrom [2] 1
= 2:euler ( listFrom [3] 1 `minus` map(2*) (listFrom [2] 1)) )
listFrom [3,4] 2 `minus` listFrom [4] 2
-- listFrom [3] 2 --
= 2:3:euler (listFrom [5] 2 `minus` map(3*) (listFrom [3] 2))
listFrom [5,7,9] 6 `minus` listFrom [9] 6
-- listFrom [5,7] 6 --
= 2:3:5:euler (listFrom [7,11] 6 `minus` listFrom [25,35] 30)
[7,11, 13,17, 19,23, 25,29, 31,35] 30
-- listFrom [7,11,13,17,19,23,29,31] 30 --
= .
where
listFrom xs by = concat $ iterate (map (+ by)) xs
so
-- startRoll = ([2],1)
nextRoll r@(xs@(x:xt),b)
= ( (x,r') , r')
where
ys@(y:_) = xt ++ [x + b]
r' = (xs',b')
b' = x*b
xs' = takeWhile ( y + b') (listFrom ys b)
`minus` map (x*) xs
rolls = unfoldr (Just . nextRoll) ([2],1)
nthWheel n = let (ps,rs) = unzip $ take n rolls
(x:xs,b) = last rs
in ((ps, x), zipWith (-) (xs++[x+b]) (x:xs))
{-
*Main mapM print $ take 4 rolls
(2,([3],2))
(3,([5,7],6))
(5,([7,11,13,17,19,23,29,31],30))
(7,([11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
101,103,107,109,113,121,127,131,137,139,143,149,151,157,163,167,169,
173,179,181,187,191,193,197,199,209,211],210))
*Main nthWheel 3
(([2,3,5],7),[4,2,4,2,4,6,2,6])
*Main nthWheel 4
(([2,3,5,7],11),[2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,
4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10])
-}
Coincidentally, the function specified by
eulerPrimes n = let (ps,rs) = unzip $ take n rolls
(qs@(q:_),b) = last rs
in ps ++ takeWhile ( q^2) qs
can be used to write the specialized nthEulerPrime etc., whose complexity seems
to be about O(n^1.5).
Maybe this reinvents some spiraling wheels or somethn'. :)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FASTER primes
Will Ness will_n48 at yahoo.com writes: That might be why Daniel's structure is better: it plunges down faster than mine. treefold structure was: (2+4) + ( (4+8) + ( (8+16) + ( (16+32) + ( (32+64) + ... dpths: 3 4 4 5 5 66 77 8 this should of course have been dpths: 3 4 5 6 7 89 10 11 12 daniel's: (2+(4+6)) + ( (8+(10+12)) + ( (14+(16+18)) + ( (20+(22+24)) + )) 3 5 5.4 6 7.8 7.9 8 9 9.5 9.6 10.7 10.8 hmm. :| ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: ANNOUNCE: Clutterhs 0.1
(Sorry for replying to this old thread.) On Sun, Nov 29, 2009 at 08:09:18AM +0100, Gour wrote: What do you think about binding Moblin's nbtk (now it's called mx) ? Just out of curiosity, did anyone do something about Moblin's toolkit and Haskell? Thanks! :) -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Infix instance headers
Simon, I discovered that the following example also won't parse in ghc-6.12.1 because of the infix 'MayOpen' constraint: with ∷ (Resource resource, MonadCatchIO pr) ⇒ resource → (∀ s. s `MayOpen` resource ⇒ RegionalHandle resource (RegionT s pr) → RegionT s pr α) → pr α Is this also fixed by your previous patch? regards, Bas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Capped lists and |append|
Earlier today I uploaded the capped-list package; I didn't think there would be any interest, since it's a relatively trivial data structure, but already there's been three emails and an IRC convo about it. In short, this is Heinrich Apfelmus's Train type from http://www.haskell.org/pipermail/haskell-cafe/2009-December/069895.html, which showed up in a thread I posted regarding lazy error handling http://www.haskell.org/pipermail/haskell-cafe/2009-November/069825.html. The structure of a Train / CappedList (I like my name better) is: data Train a b = Wagon a (Train a b) | Loco b data CappedList cap a = Next a (CappedList cap a) | Cap cap Since uploading, there's been a big problem pointed out to me regarding this structure, namely the possible definitions of |append|. Because the list terminus is itself a value, but isn't / shouldn't be the same type as the elements, either obvious implementation will drop it. append :: CappedList cap a - CappedList cap a - CappedList cap a append (Cap 0) (Cap 1) = -- either (Cap 0) or (Cap 1), but information has been lost This problem can be solved using an unusual type signature for |append|, such as: append :: CappedList cap1 a - CappedList cap2 a - (cap1, CappedList cap2 a) or by declaring that a capped list is truly capped: append :: CappedList cap a - CappedList cap2 b - CappedList cap a but these makes defining a reasonable |concat| difficult. Any ideas? This seems like a useful structure, since several people have described it, but some of the semantics seem troublesome. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Capped lists and |append|
[Disclaimer: I didn't really read all the thread from which this data structure originated on Cafè =).] On Fri, Jan 08, 2010 at 03:38:15PM -0800, John Millikin wrote: Since uploading, there's been a big problem pointed out to me regarding this structure, namely the possible definitions of |append|. Because the list terminus is itself a value, but isn't / shouldn't be the same type as the elements, either obvious implementation will drop it. append :: CappedList cap a - CappedList cap a - CappedList cap a append (Cap 0) (Cap 1) = -- either (Cap 0) or (Cap 1), but information has been lost I don't think there is an easy solution here. In a first approach, what I would do would be to provide -- Returning one of the caps out of list. appendL :: CappedList cap a - CappedList cap' a - (cap', CappedList cap a) appendR :: CappedList cap' a - CappedList cap a - (cap', CappedList cap a) -- Discarding one of the caps. appendL_ :: CappedList cap a - CappedList discarded a - CappedList cap a appendR_ :: CappedList discarded a - CappedList cap a - CappedList cap a -- 'mappend'ing the caps appendM :: Monoid cap = CappedList cap a - CappedList cap a - CappedList cap a and then define mappend = appendM If we used appendL_ then we would violate Monoid's law that says that mappend mempty x = x And if we used appendR_ we would violate mappend x mempty = x Of course, you would have to change your 'empty' package to include the following law: For every data type implementing Empty and Monoid, empty should be mempty. This way you will guarantee that when using appendM Cap empty `mappend` Cap c = Cap c Also, you may want to have CappedList an instance of Control.Functor.Bifunctor from category-extras: -- Hask is a synonym for (-). instance Bifunctor CappedList Hask Hask Hask where bimap f g = foldr (Next . f) (Cap . g) And, of course, import Data.Monoid (First(..), Last(..)) appendL_ = bimap id getFirst . appendM . bimap id First appendR_ = bimap id getLast . appendM . bimap id Last Cheers, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Capped lists and |append|
John Millikin wrote: Earlier today I uploaded the capped-list package; I didn't think there would be any interest, since it's a relatively trivial data structure, but already there's been three emails and an IRC convo about it. Since uploading, there's been a big problem pointed out to me regarding this structure, namely the possible definitions of |append|. Any ideas? This seems like a useful structure, since several people have described it, but some of the semantics seem troublesome. Some ideas: append :: Monoid c = CappedList c a - CappedList c a - CappedList c a append (Cap a) (Cap b) = Cap (a `mappend` b) This also leads to an instance Monoid (CappedList c): instance Monoid c = Monoid (CappedList c) where mempty = Cap mempty mappend = append You could also make the combining function flexible: appendWith :: (c - d - e) - CappedList c a - CappedList d a - CappedList e a The problem with this definition is that it doesn't really respect the structure of the second list: the entire list has to be traversed just to update the cap. More random ideas: -- this is bind in the CappedList _ a monad bindCap :: CappedList c a - (c - CappedList d a) - CappedList d a bindCapF :: Functor f = CappedList c a - (c - f (CappedList d a)) - f (CappedList d a) Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [arch-haskell] Upgrading Arch Linux Haskell Packages
Even while having a break he's blazing fast with his replies! 2010/1/8 Ivan Lazar Miljenovic ivan.miljeno...@gmail.com Don Stewart d...@galois.com writes: There's a batch upgrade, I've just been travelling! Yeah, let Don have a break for once! Oh, since you're here Don, how do I do ... ? ;-) -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FASTER primes
Am Freitag 08 Januar 2010 19:45:47 schrieb Will Ness: Daniel Fischer daniel.is.fischer at web.de writes: mergeSP :: Integral a = People a - People a - People a mergeSP p1@(P a _) p2 = P (a ++ vips mrgd) (dorks mrgd) where mrgd = spMerge (dorks p1) (vips p2) (dorks p2) spMerge l1 [] l3 = P [] (merge l1 l3) spMerge ~l1@(x:xs) l2@(y:ys) l3 = case compare x y of LT - celebrate x (spMerge xs l2 l3) EQ - celebrate x (spMerge xs ys l3) GT - celebrate y (spMerge l1 ys l3) -- Hi Daniel, Is it so that you went back to my fold structure? Yes. Was it better for really big numbers of primes? Yes, it is slower for = 20 million primes (and some beyond), but faster for = 50 million (and some before), according to the few tests I made. I had the following for ages (well, at least two weeks) but I thought it was slower and took more memory (that was _before_ the 'no-share' and 'feeder' stuff). I can see the only difference in that you've re-written spMerge in a tail-recursive style with explicitly deconstructed parts; It's not tail-recursive, the recursive call is inside a celebrate. As it turns out, the important things are 1. a feeder and separate lists of multiples for the feeder and the runner, for the reasons detailed earlier (two-step feeding and larger wheel are pleasing but minor optimisations). 2. a strict pattern in tfold 3. moving the merge inside spMerge (you can have mergeSP (a,b) ~(c,d) = (a ++ bc, m) where (bc,m) = spMerge b c spMerge u [] = ([],merge u d) ... without exploding memory, but it's *much* slower than letting spMerge take three arguments) Now, I have to admit, the only point I _really_ understand is 1. (and why the three-argument spMerge is faster than the two-argument one taking the merge-partner from mergeSP's binding :). Why has mergeSP (a,b) ~(c,d) = let (bc,b') = spMerge b c in (a ++ bc, merge b' d) a memory leak, but mergeSP (a,b) ~(c,d) = let (bc,m) = spMerge' b c d in (a ++ bc, m) not? Well, looking at the core for mergeSP, the fog clears somewhat. The former is translated roughly to mergeSP (a,b) pair = let sm = spMerge b (fst pair) in (a ++ fst sm, merge (snd sm) (snd pair)) It holds on to the pair until the result of the merge is demanded, that is until the entire (a ++ fst sm) is consumed. Only then is the pair released and can be collected. On top of that, as soon as a is consumed and (fst sm) [or bc] is demanded, spMerge forces the evaluation of (fst pair) [c]. After a few levels, the evaluated list will take more space than the thunk. It cannot yet be collected, because pair is still alive. The elements have to be duplicated for (fst sm), because they're intertwined with those of b. On the next level of merging, they have to be duplicated again. The latter is translated roughly to mergeSP (a,b) pair = let sm = spMerge' b (fst pair) (snd pair) in (a ++ fst sm, snd sm) The pair is released as soon as the result of the spMerge' is demanded, that is, when a is consumed. Then the elements of (fst pair) need not be duplicated and they can be discarded almost immediately after they have been produced [for small primes, multiples of larger primes live a little longer, but those are fewer]. So, no duplication, shorter lifespan = no leak. Having seen that, the question is, why can't the compiler see that deconstructing the pair when the first component is needed is better? The first component of the pair is used in no other place, so keeping the pair can't have any advantage, can it? And why does tfold f (a: ~(b: ~(c:xs))) = ... leak, but not tfold f (a:b:c:xs) = ... ? I guess it's similar. tfold f (a: ~(b: ~(c:xs))) = (a `f` (b `f` c)) `f` tfold f ([pairwise f] xs) is tfold f (a:zs) = (a `f` (head zs `f` (head $ tail zs))) `f` tfold f (pairwise f $ drop 2 zs) the latter part holds on to the beginning of zs, leading again to data duplication and too long lifespans. mine was relying on the compiler (8-L) to de-couple the two pipes and recognize that the second just passes along the final result, unchanged. The two versions seem to me to be _exactly_ operationally equivalent. Well, they're not. The main difference is what we told the compiler _when_ to deconstruct the pairs. You said at the latest possible moment, I said as soon as we need the first component. It's not entirely obvious, but it is frequently said that understanding the space (and time) behaviour of lazy evaluation isn't always easy. All this searching for the code better understood by the compiler is _*very*_ frustrating, as it doesn't reflect on the semantics of the code, or even the operational semantics of the code. :-[ Weren't the P's supposed to disappear completely in the compiled code? No. Constructors for
Re: [Haskell-cafe] Capped lists and |append|
Everything here makes much more sense than the previous implementation -- I've upped 1.2, which splits up |append|, implements the instances in terms of Monoid, etc. Also included is |toList| and |toList_| , which are like functions defined in Felipe's earlier email to me. The first returns the cap and values, the second only the values. Last (but not least), some of the |append*| functions are now defined in terms of |appendWith| from Twan van Laarhoven's email. For example, |appendM = appendWith mappend|. On Fri, Jan 8, 2010 at 17:57, Felipe Lessa felipe.le...@gmail.com wrote: Of course, you would have to change your 'empty' package to include the following law: For every data type implementing Empty and Monoid, empty should be mempty. empty turned out to be a dumb idea -- I had hoped to use it for types which support a NIL value but not appending. Turns out, there's not much point to lists which can't be appended. C'est la vie. Also, you may want to have CappedList an instance of Control.Functor.Bifunctor from category-extras: [...] This is probably a good idea, but, I am nervous about making such a small package depend on the huge category-extras and mtl. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FASTER primes
Daniel Fischer daniel.is.fischer at web.de writes: Am Freitag 08 Januar 2010 19:45:47 schrieb Will Ness: Daniel Fischer daniel.is.fischer at web.de writes: It's not tail-recursive, the recursive call is inside a celebrate. It is (spMerge that is). It calls tail-recursive celebrate in a tail position. What you've done, is to eliminate the outstanding context, buy moving it inward. Your detailed explanation is more clear than that. :) BTW when I run VIP code it is consistently slower than using just pairs, modified with wheel and feeder and all. So what's needed is to re-implement your approach for pairs: mergeSP (a,b) ~(c,d) = let (bc,bd) = spMerge b c d in (a ++ bc, bd) where spMerge u [] d = ([], merge u d) spMerge u@(x:xs) w@(y:ys) d = case compare x y of LT - consSP x $ spMerge xs w d EQ - consSP x $ spMerge xs ys d GT - consSP y $ spMerge u ys d consSP x ~(a,b) = (x:a,b) -- don't forget that magic `~` !!! BTW I'm able to eliminate sharing without a compiler switch by using mtwprimes () = 2:3:5:7:primes where primes = doPrimes 121 primes doPrimes n prs = let (h,t) = span ( n) $ rollFrom 11 in h ++ t `diff` comps prs doPrimes2 n prs = let (h,t) = span ( n) $ rollFrom (12-1) in h ++ t `diff` comps prs mtw2primes () = 2:3:5:7:primes where primes = doPrimes 26 primes2 primes2 = doPrimes2 121 primes2 Using 'splitAt 26' in place of 'span ( 121)' didn't work though. How about them wheels? :) Yes. It's still a do what I tell you to compiler, even if a pretty slick one, not a do what I mean compiler. Sometimes, what you tell the compiler isn't what you wanted. It's easier to predict when you give detailed step by step instructions. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FASTER primes
Heinrich Apfelmus apfelmus at quantentunnel.de writes: Will Ness wrote: But I get the impression that GHC isn't working through equational reasoning?.. I see all this talk about thunks etc. Sure it does. Concerning the thunks, they're part of the implementation of the reduction model (call-by-need aka lazy evaluation). At run-time? I meant to eliminate as much calculation as possible, pre-run-time. I would expect the best efforts of the best minds to go into searching for ways how to eliminate computations altogether, instead of how to perform them better. Concerning the sieves, there is a fundamental difference between the imperative sieve and the functional sieves, regardless of whether the latter start at p or p^2 or use a priority queue. [...] We can directy jump to the next multiple too, it is called (+). :) :) But seriously, the real issue is that we have to merge the produced streams of multiples, while the mutable-storage code works on same one, so its merging cost is zero. Not quite, I think there are two things going on: 1. In contrast to the standard imperative version, we are implementing an on-line algorithm that produces arbitrarily many primes on demand. Any imperative on-line version will need to think about storage for pending prime filters as well. True. 2. Even the imperative algorithm can be interpreted as merging arrays, just that the composites are magically merged at the right place (at distance p from each other) because arrays offer O(1) jumps. i.e. with a merging cost of zero. :) In contrast, the functional version needs O(log something) time to calculate where to put the next composite. when thinking it terms of the finally produced sequence, yes. We have to produce numbers one by one and take care of their ordering ourselves; _they_ just /throw/ the numbers at the shared canvas and let _it_ take care of ordering them automagically, _later_, on the final sweep through. ISWYM. If you could take a look at the tree-merging primes and why it uses too much memory, it would be great. Fortunately, Daniel already took a detailed look. :) Yes he really came through! He finally found, and fixed, the space leak. It was hiding in mergeSP_BAD (a,b) ~(c,d) = let (bc,b') = spMerge b c in (a ++ bc, merge b' d) where spMerge :: (Ord a) = [a] - [a] - ([a],[a]) spMerge a@(x:xs) b@(y:ys) = case compare x y of LT - (x:c,d) where (c,d) = spMerge xs b EQ - (x:c,d) where (c,d) = spMerge xs ys GT - (y:c,d) where (c,d) = spMerge a ys spMerge a [] = ([] ,a) spMerge [] b = ([] ,b) which really ought to have been mergeSP (a,b) ~(c,d) = let ~(bc,bd) = spMerge b c d in (a ++ bc, bd) where spMerge u [] d = ([], merge u d) spMerge u@(x:xs) w@(y:ys) d = case compare x y of LT - spCons x $ spMerge xs w d EQ - spCons x $ spMerge xs ys d GT - spCons y $ spMerge u ys d spCons x ~(a,b) = (x:a,b) Can you spot the difference? :) :) Aww, why remove the cutesy name? The VIPs will be angry for being ignored! It runs faster on plain pairs, and on less memory, equals for equals. For some reason. :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
