[Haskell-cafe] ANNOUNCE: hpc-strobe-0.1: Hpc-generated strobes for a running Haskell program
I am pleased to announce the initial release of hpc-strobe: Hpc-generated strobes for a running Haskell program. hpc-strobe is a rudimentary library that demonstrates the possibility of using Hpc (Haskell Program Coverage) to inspect the state of a running Haskell program. hpc-strobe-0.1 has been uploaded to hackage: http://hackage.haskell.org/packages/archive/hpc-strobe/0.1/hpc-strobe-0.1.tar.gz In ordinary use of Hpc, a single so-called tix file is produced at the end of a run. The tix file records how many times each expression has been used during the run. This can be used to mark up the source code, identifying expressions that have not been used. hpc-strobe uses the basic machinery provided by Hpc to produce multiple tix files, also called strobes, representing the coverage at different times while the program is running. By subtracting such two tix files, again using Hpc machinery, a tix file representing the expressions used between the times of recording the subtracted tix files is produced. This may be used, for example, to get a better idea of what a long-running program is doing. It could also be used as a profiling tool, getting information about how many times individual expressions are used. A program is included whose strobe differences produce a crude rendering of an analog clock when they are used to mark up the source code using Hpc. Please see the attached example (gunzip the file, point you browser to it, scroll down to view the canvas function). Use of the library involves a simple change of the main function and also requires the program to be enabled for hpc. At the time of writing, this means using a fairly recent version of GHC and compiling the Haskell code with the -fhpc option. For additional details, see the README included in the package. Best regards Thorkil Main.hs.html.gz Description: GNU Zip compressed data ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Announce] primes
Hello, On Thursday 16 April 2009 17:22, Sebastian Fischer wrote: ... Thanks! Feel free to incorporate ideas from NaurPrimes.hs. I don't understand them yet. NaurPrimes.hs is derived from the EratoS.hs that you get from unpacking thorkilnaur.dk/~tn/Haskell/EratoS/T64_20070303_1819.tar.gz. EratoS.hs is explained in thorkilnaur.dk/~tn/Haskell/EratoS/EratoS2.txt. Please don't hesitate to ask questions about this. I'll do my best to answer. ... Best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Comments from OCaml Hacker Brian Hurt
Hello, On Thursday 15 January 2009 19:59, Peter Verswyvelen wrote: It is rather funny. When we are young kids, we learn weird symbols like A B C a b c 1 2 3 which we accept after a while. Then we get to learn more complex symbols like ! ? + - / and that takes some time to get used to, but eventually, that works too. But Functor, Monoid or Monad, that we cannot accept anymore. Why, because these are not intuitive? Are the symbols above intuitive? I think there is a simple explanation of this: Consider the amount of time you spent, as a young kid, to learn to get used to these funny 1, 2, a, b, x, y, +, - and so on. I haven't got the exact schedules from school, but my impression is that we are talking about hours and hours of drill and practice, over weeks, months, years. I mean, do you show your small children (say, 5 years old) how to write numbers to represent, say, the number of oranges in a bowl and then they comprehend after, say, a couple of minutes? Or half an hour? No. Learning to get used to such things, let alone use them effectively to solve common problems, takes time. And also, of course, intense and qualified guidance, in some form. So, to learn to become familiar and effective in using new and complex concepts, we should just accept that it sometimes may take a while. And that's it. It is all a matter of practice, exposure, and guidance. ... Best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Recursive modules, GHC /= Report?
Hello, On Wednesday 14 January 2009 12:59, Mauricio wrote: Hi, Here: http://www.haskell.org/onlinereport/modules.html I read: Modules may reference other modules via explicit import declarations, each giving the name of a module to be imported and specifying its entities to be imported. Modules may be mutually recursive. However, I get this from GHC: --- Module imports form a cycle for modules: main:Main imports: Control.Concurrent.MVar GtkMostrarConfig GtkLerECG Graphics.UI.Gtk main:GtkMostrarConfig imports: Control.Concurrent.MVar Graphics.UI.Gtk Main --- Aren't cycles of modules just recursive modules? Why wasn't that allowed? Have you looked at http://www.haskell.org/ghc/docs/latest/html/users_guide/separate-compilation.html#mutual-recursion ? I never tried this myself, but it seems to explain some important details about how to compile mutually recursive modules using GHC. Thanks, Maurício ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to think about this? (profiling)
Hello, On Tuesday 16 December 2008 13:19, Felipe Lessa wrote: 2008/12/16 Magnus Therning mag...@therning.org: That is, where each value depends on _all_ preceding values. AFAIK list access is linear, is there a type that is a more suitable state for this changed problem? I realise this particular function can be written using scanl: [...] but I guess it's not always that easy to construct a solution based on scanl. You can always write something like foo :: Int - Int foo = (vals !!) where vals = map foo' [0..] foo' 0 = 0 foo' 1 = 1 foo' 2 = 2 foo' n = sum $ map foo [0..n-1] which doesn't prevent you from using whatever recursive case you want. Note that if your recursive case depends on all preceding values, then you can't do better than using a linear access data structure like a list unless you need random access. Another possibility would be: g n = t!n where t = array (0,max 2 n) $ (0,0):(1,1):(2,2):[ (i,t!(i-3) + t!(i-2) + t!(i-1)) | i - [3..n] ] using your original example. As noted in the Haskell 98 report, section 16.1 Array Construction, the array function is non-strict in the values of the association list, making this recurrence possible. ... Best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Meaning of ribbonsPerLine at Text.PrettyPrint.HughesPJ ?
Hello, On Wednesday 18 June 2008 22:13, Alfonso Acosta wrote: Hi, Can anyone give a good explanation of what ribbonsPerLine means? Maybe it would be better to simply ask for the meaning of ribbon in this context. The documentation is totally meaningless to me: reibbonsPerLine: Ratio of ribbon length to line length. In the paper The Design of a Pretty-printing Library by John Hughes (http://www.cs.chalmers.se/~rjmh/Papers/pretty.ps) that introduced this pretty printing library, the ribbon concept is introduced like this (apologies for the layout, please use the original .ps file for accuracy): 7.4 Choosing a Pretty Layout Now that we have designed combinators for constructing documents with many possible layouts, it is time to discuss choosing among those alternatives. Many prettyprinters aim simply to avoid exceeding a given page width. However, we found that using this criterion alone tends to produce layouts such as for i = 1 to 100 do for j = 1 to 100 do for k = 1 to 100 do a[i,j,k] := 0 which fits on a page, but cannot be described as pretty. We therefore impose an additional constraint limiting the number of characters on each line (excluding indentation) to a smaller number. The idea is to avoid placing too much information on a line -- even a line that begins at the left margin. Under this constraint the example above might instead be laid out as for i = 1 to 100 do for j = 1 to 100 do for k = 1 to 100 do a[i,j,k] := 0 In general a pretty layout will consist of a ribbon of text snaking across the page. To see that this is reasonable, ask yourself: `is the prettiest layout on an infinitely wide page really to place everything on one line?' So pretty printing is guided by two lengths: The line length and the (smaller) ribbon length. The ribbons per line ratio that you can specify is simply a way of specifying the ribbon length relative to the line length. So, for example, if the line length is 80 and the ratio is 1.5, the ribbon length would be 80/1.5 which is rounded to 53. ... Best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: A question about monad laws
Hello, On a tangent, probably: On Thursday 14 February 2008 10:24, Roman Leshchinskiy wrote: ... Hmm. Personally, I've never seen an algorithm where comparing for exact equality was algorithmically necessary. Sometimes (rarely) it is acceptable but necessary? Do you know of one? Finding the machine epsilon, perhaps, that is, the smallest (floating point, surely) number for which 1.0+machine_eps==1.0 would be a candidate? ... Best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast integer base-2 log function?
Hello, If the standard libraries provide such a function, I haven't found it. I must admit that I haven't studied your code in detail. I usually do as follows for integer logarithms, shamelessly stolen from the Haskell report: -- Integer log base (c.f. Haskell report 14.4): imLog :: Integer-Integer-Integer imLog b x = if x b then 0 else let l = 2 * imLog (b*b) x doDiv x l = if x b then l else doDiv (x`div`b) (l+1) in doDiv (x`div`(b^l)) l Best regards Thorkil On Monday 11 February 2008 07:15, Uwe Hollerbach wrote: Hello, haskellers, Is there a fast integer base-2 log function anywhere in the standard libraries? I wandered through the index, but didn't find anything that looked right. I need something that's more robust than logBase, it needs to handle numbers with a few to many thousands of digits. I found a thread from a couple of years ago that suggested there was no such routine, and that simply doing length (show n) might be the best. That seems kind of... less than elegant. I've come up with a routine, shown below, that seems reasonably fast (a few seconds of CPU time for a million-bit number, likely adequate for my purposes), but it seems that something with privileged access to the innards of an Integer ought to be even much faster -- it's just a simple walk along a list (array?) after all. Any pointers? Thanks! Uwe powi :: Integer - Integer - Integer powi b e | e == 0= 1 | e 0 = error negative exponent in powi | even e= powi (b*b) (e `quot` 2) | otherwise = b * (powi b (e - 1)) ilog2 :: Integer - Integer ilog2 n | n 0 = ilog2 (- n) | n 2 = 1 | otherwise = up n (1 :: Integer) where up n a = if n (powi 2 a) then bin (quot a 2) a else up n (2*a) bin lo hi = if (hi - lo) = 1 then hi else let av = quot (lo + hi) 2 in if n (powi 2 av) then bin lo av else bin av hi (This was all properly aligned when I cut'n'pasted; proportional fonts might be messing it up here.) ___ 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
readline problems building GHC on Mac OS X (was: Re: [Haskell-cafe] Re: ANNOUNCE: GHC version 6.8.2)
Hello, Although I have been building various GHC versions on various PPC Mac OS X systems for a while now, I'm afraid that I don't really have a good answer for your questions. However, your questions provide an excellect opportunity to discuss this, so that is what I am going to do. There are several questions here: (1) Which readline do we use? (2) Where do we store it? (3) What do we call it? (4) How do we make the Haskell readline library build process select the right one? And perhaps (5) How do we persuade the GHC build process to make the Haskell readline build that happens as part of building GHC select the right one? One at a time: 1. Which readline do we use? GNU readline, of course. As opposed to the readline installed as /usr/include/readline/*.h and /usr/lib/libreadline.dylib on our PPC Mac OS X machines which are said to be (and can even be observed to be) symbolic links to something called libedit and which, to me, never has managed to provide something suitable for use by GHC. But what is GNU readline, then? I don't exactly know, but my best guess is something like ftp://ftp.cwru.edu/pub/bash/readline-5.2.tar.gz. I never tried to install GNU readline directly from this file. On some occasions, I have installed readline from mac ports. Although I am fairly confident that what was installed was some version of the GNU readline, I am not sure. On other occasions, I have installed GNU readline from various sources related to GHC, some times known to me, at other times not. 2.Where do we store readline? I don't know where a readline based on the GNU download ftp://ftp.cwru.edu/pub/bash/readline-5.2.tar.gz would become installed (by default). The mac ports version installs by default at /opt/local/include/readline/*.h and /opt/local/lib/libreadline.*. Various readlines related to GHC have installed themselves (or were requested to become installed) as frameworks, this new and different Mac OS X mechanism for referring to a set of header files and corresponding library. So they have gone into /Library/Frameworks. 3. What do we call it? Here is where the interesting things start to happen: A central problem has been the ambiguity caused by Apple's decision to install symbolic links to the edit headers and edit library called readline. And various mechanisms have been used to work around this problem: (a) If you have installed a mac ports readline at /opt/local/..., with GHC 6.6 at least, you were able to use the --with-readline-* options to direct GHC/the library build process to look in these directories first and thereby avoid the edit library; (b) At some point, a (possibly modified) version of the GNU readline library appeared, intended to be installed as a framework by the name of GNUreadline (as opposed to the bare readline name used earlier). This avoids the name clash caused by the Apple linking of readline to edit. The problem that the Haskell readline library now needs to refer to a framework GNUreadline rather than ... (whatever it is that it refers to in a more Unix'y setting) is solvable. In addition, however, the readline library (or rather: The GNUreadline library derived from the readline library) refers to itself using the bare readline name, so that has to be changed also, leading to a need to maintain a complete and slightly modified version (GNUreadline) of the readline library. It seems to me that this situation is less than ideal. I mean, in theory, somebody may come along at some point with some library calling itself GNUreadline and then we would have to adapt, doing the whole thing all over again. This manner of avoiding the name clash problem does not seem tenable in the long run. Instead, what we should be able to do, is to specify, directly and to the point, that readline, wherever we stored it, is what we want. That possibility does not exist, unfortunately, so we will have to make the best use that we can of the existing mechanisms, as far as we can figure out what they are, to get the desired effect. And if it turns out that the existing mechanisms do not allow us to do what we want, we need to request extensions and modifications of the mechanisms, until they are able to support our requirements. I am not quite sure that I am done with this subject, but let me go on with 4. How do we make the Haskell readline library build process select the right one? This is where I believe we can do something useful, making the Haskell readline library more capable in selecting its foundation readline library. I haven't worked out the details, some discussion is at http://hackage.haskell.org/trac/ghc/ticket/1395 and related tickets, but I am quite sure that methods can be found to select the desired readline library, without resorting to reissuing that library in a changed form and under a new name. And if this turns out to be absolutely impossible, I would much prefer pressing for the introduction of
Re: [Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)
Hello, On Wednesday 25 July 2007 01:42, Thorkil Naur wrote: Hello Melissa, On Tuesday 24 July 2007 19:09, Melissa O'Neill wrote: ... (See ONeillPrimes.hs in http://www.cs.hmc.edu/~oneill/code/haskell- primes.zip for the complete code. I've also added Thorkil Naur's code from March, which is also a good performer, Do you have detailed measurements that you wish to share? I would be most interested, I assure you. although its another case where most readers would find a detailed explanation of the code instructive.) I'll do my very best to provide such an explanation within, say, the next couple of weeks. ... And now that time has come, so brace yourselves. For your convenience, my code from March is thorkilnaur.dk/~tn/T64_20070303_1819.tar.gz See also a preliminary description in http://www.haskell.org/pipermail/haskell-cafe/2007-March/023095.html. The new explanation is here: thorkilnaur.dk/~tn/Haskell/EratoS/EratoS2.txt Best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Using Gtk2Hs version 0.9.12 on a PPC Mac
Hello, On Saturday 28 July 2007 14:22, Duncan Coutts wrote: On Sat, 2007-07-28 at 12:16 +0200, Thorkil Naur wrote: Hello, (From the archives:) [Haskell] ANNOUNCE: Gtk2Hs version 0.9.12 released Duncan Coutts duncan.coutts at worc.ox.ac.uk Fri Jul 27 15:20:57 EDT 2007 Gtk2Hs - A GUI Library for Haskell based on Gtk+ Version 0.9.12 is now available from: ... Duncan (on behalf of the Gtk2Hs team) Following the advice of nominolo_ from #haskell yesterday, I added -L/opt/local/lib to my ghc command and then the helloworld demo of Gtk2Hs worked. The problem seems to be the order in which the two library directories /usr/X11R6/lib and /opt/local/lib appear on the link command: For the GTK+ example that worked, /opt/local/lib comes first. For the Gtk2Hs demo that failed, /usr/X11R6/lib comes first. That's very interesting. I compared these two directories and found these common files: [...] Since some of these (Xrender, fontconfig, and freetype) are actually used in GTK+ (and therefore also Gtk2Hs) applications, there is clearly a potential for conflict here. Certainly and if I recall correctly, the gdb backtrace you got showed that it was failing in a call to a fontconfig function. A good guess: (gdb) run Starting program: /Users/thorkilnaur/tn/Gtk2Hs/gtk2hs-0.9.12/demo/hello/helloworld Reading symbols for shared libraries .++...++...+.+. +.... done Program received signal EXC_BAD_ACCESS, Could not access memory. Reason: KERN_PROTECTION_FAILURE at address: 0x0001 FcFontSetSort (config=0x0, sets=0xbfffba50, nsets=2, p=0x2114fb0, trim=1, csp=0x0, result=0xbfffbb18) at fcmatch.c:696 ... In any case, adding -L/opt/local/lib to the ghc command makes this library appear before /usr/X11R6/lib on the link command and this seems to solve the problem. Subsequently, I have tried a handful of the other demos, and as far as they didn't require something that wasn't available (glade, for example), they seemed to work. So what I wonder is how we can make this work reliably. We use the flags that pkg-config tells us to use, I'd rather not add platform-specific hacks if we can get the pkg-config settings fixed. So I presume when you run pkg-config --libs gtk+-2.0 it does not list -L/opt/local/lib, or if it does it lists it after -L/usr/X11R6/lib. Is that the case? For the GTK+ tutorial helloworld.c program: $ pkg-config --libs gtk+-2.0 -L/Users/thorkilnaur/tn/install/gtk+-2.10.14/lib -L/opt/local/lib -L/usr/X11R6/lib -lgtk-x11-2.0 -lgdk-x11-2.0 -latk-1.0 -lgdk_pixbuf-2.0 -lm -lpangocairo-1.0 -lpango-1.0 -lcairo -lSM -lICE -lgobject-2.0 -lgmodule-2.0 -lglib-2.0 -lintl -liconv -lfreetype -lz -lfontconfig -lpng12 -lXrender -lX11 $ gcc -v -Wall -g helloworld.c -o helloworld `pkg-config --cflags gtk+-2.0` `pkg-config --libs gtk+-2.0` ... /usr/libexec/gcc/powerpc-apple-darwin8/4.0.1/collect2 -dynamic -arch ppc -weak_reference_mismatches non-weak -o helloworld -lcrt1.o /usr/lib/gcc/powerpc-apple-darwin8/4.0.1/crt2.o -L/Users/thorkilnaur/tn/install/gtk+-2.10.14/lib -L/opt/local/lib -L/usr/X11R6/lib -L/usr/lib/gcc/powerpc-apple-darwin8/4.0.1 -L/usr/lib/gcc/powerpc-apple-darwin8/4.0.1 -L/usr/lib/gcc/powerpc-apple-darwin8/4.0.1/../../.. /var/tmp//cctkdfsu.o -lgtk-x11-2.0 -lgdk-x11-2.0 -latk-1.0 -lgdk_pixbuf-2.0 -lm -lpangocairo-1.0 -lpango-1.0 -lcairo -lSM -lICE -lgobject-2.0 -lgmodule-2.0 -lglib-2.0 -lintl -liconv -lfreetype -lz -lfontconfig -lpng12 -lXrender -lX11 -lgcc -lSystemStubs -lSystem $ Scrutinizing the link arguments output by gcc, it appears that the -Ls and the -ls specified on the gcc command have been separated and inserted between other -Ls and -ls supplied by gcc. But the order of the -Ls produced by pkg-config is retained and, as mentioned, this is the case that works without change. For the Gtk2Hs demo World.hs program, the matter is more complex, especially since the link arguments generated by ghc presumably goes via ghc-pkg that I have never studied in detail before. But let me venture a guess anyway. First we look at the gtk package and its dependents: $ for p in gtk-0.9.12 glib-0.9.12 cairo-0.9.12; do echo $p: `ghc-pkg field $p depends`; done gtk-0.9.12: depends: base-2.0 mtl-1.0 glib-0.9.12 cairo-0.9.12 glib-0.9.12: depends: base-2.0 cairo-0.9.12: depends: base-2.0 mtl-1.0 glib-0.9.12 $ Further: $ for p in gtk-0.9.12 glib-0.9.12 cairo-0.9.12; do echo $p: `ghc-pkg field $p library-dirs`; done gtk-0.9.12: library-dirs: /Users/thorkilnaur/tn/install/gtk+-2.10.14/lib /usr/X11R6/lib /Users/thorkilnaur/tn/install/gtk2hs-0.9.12/lib/gtk2hs glib-0.9.12: library-dirs: /opt/local/lib /Users/thorkilnaur/tn/install/gtk2hs-0.9.12/lib/gtk2hs cairo-0.9.12: library-dirs: /opt/local/lib /usr/X11R6/lib /Users/thorkilnaur/tn/install/gtk2hs-0.9.12/lib/gtk2hs $ The actual link arguments constructed
Re: [Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)
Hello Melissa, On Tuesday 24 July 2007 19:09, Melissa O'Neill wrote: apfelmus wrote: After some pondering, the List a data structure for merging is really ingenious! :) Here's a try to explain how it works: Thanks apfelmus! A detailed explanation of this code is really helpful for anyone trying to understand what is going on. The VIP/ Crowd analogy is also very nice. I think that this approach has the potential to outperform O'Neill's (old?) code because it doesn't incorporates another prime number to the sieve mechanism until it really has to. I mean the following: in the 1st, 2nd, 3rd, 4th, ... step, O'Neill's code adds the multiples 2*2, 3*3, 5*5, 7*7, ... to the priority queue and uses them to sieve for potential prime numbers from then on. Yeah, that's (only) what the code in my paper does -- it's good enough for explicative purposes, but all recent versions have used a slightly augmented priority queue. It's a priority queue coupled with a feeder list that provides entries to add to the queue (in increasing order). They are only admitted to the heap data structure only once when the root of the heap gets there. The two most important bits are: type HybridQ k v = (PriorityQ k v, [(k,v)]) -- postRemoveHQ is called when the min element of the heap has changed postRemoveHQ :: Ord k = HybridQ k v - HybridQ k v postRemoveHQ mq@(pq, []) = mq postRemoveHQ mq@(pq, (qk,qv) : qs) | qk minKeyPQ pq = (insertPQ qk qv pq, qs) | otherwise= mq (See ONeillPrimes.hs in http://www.cs.hmc.edu/~oneill/code/haskell- primes.zip for the complete code. I've also added Thorkil Naur's code from March, which is also a good performer, Do you have detailed measurements that you wish to share? I would be most interested, I assure you. although its another case where most readers would find a detailed explanation of the code instructive.) I'll do my very best to provide such an explanation within, say, the next couple of weeks. the approach here adds 5*5=25 to the heap only after considering the 9th prime 23. Yep, that's what mine does too. Best Regards, Melissa. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Thanks a lot and the best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Maintaining the community
Hello, On Friday 13 July 2007 16:45, Ian Lynagh wrote: ... * At any point, create [EMAIL PROTECTED] This would have the advantage that people might not be so intimidated at making their first post here, and posts wouldn't be answered with category theory or scary type extensions. The disadvantages are that it makes an artificial barrier (when is someone ready to post to haskell@ instead?) Just an idea: How about haskell-first-post@ to encourage the second post to go to [EMAIL PROTECTED] Or is that too dictator-like? ... I'm not sure if this is a good idea. I'm not sure either ... ... Best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Maintaining the community
Hello, On Friday 13 July 2007 17:08, Neil Mitchell wrote: Hi * At any point, create [EMAIL PROTECTED] This would have the advantage that people might not be so intimidated at making their first post here, and posts wouldn't be answered with category theory or scary type extensions. The disadvantages are that it makes an artificial barrier (when is someone ready to post to haskell@ instead?) Just an idea: How about haskell-first-post@ to encourage the second post to go to [EMAIL PROTECTED] Or is that too dictator-like? Why not [EMAIL PROTECTED], for people who aren't using Haskell to do things, but are working through tutorials. The idea with haskell-first-post@ would be to make it extremely easy for people to select which list to post to. For example, with a learning list, I would be uncertain myself. Whether it would also be easy for answerers to figure out how to behave, I don't know. In any case, it is important (as others have also said) not to lose the situation that mixes new-comers with experts. A number of questions relate directly to books such as SOE, and these could be easily answered there. Thanks Neil Best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Literate Priority Queue, plus question
Hello, On Saturday 16 June 2007 14:53, Michael T. Richter wrote: I'm trying my hand at making an improved, more efficient, Sieve of Eratosthenes implementation based on Melissa O'Neil's paper (http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf) to augment the inefficient not-Sieve I've documented at http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell). ... Surely you know this already, but to make absolutely sure: There was a lot of discussion on this subject on this mailing list a while back. Melissa O'Neill's own entry into this is http://www.haskell.org/pipermail/haskell-cafe/2007-February/022666.html as far as I can tell and you can go both forwards and backwards from there. Best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How to selectively export internal entities from a module for testing?
Hello, It is common practice to export only selected entities from a Haskell module and refrain from exporting other entities so that they are only available for internal use. There are many reasons for wanting to do this, such as reducing the number of importable entities, avoiding the exposure of internal details that may therefore more easily be changed, and to enable certain optimizations (http://haskell.org/haskellwiki/Performance/Modules). However, for one particular use, namely automated testing, it often seems useful, even necessary, to allow even entities considered internal to be exported: If internal entities cannot be imported by the testing code, they can only be tested indirectly, via the exported entities, and that may turn out to be troublesome. A possibility would be to include the testing code in the module itself, but that seems clumsy and wasteful. For possible guidance, I have looked at http://darcs.haskell.org/packages/filepath and System/FilePath/Internal.hs contains -- Note: leave this section to enable some of the tests to work #ifdef TESTING -- * Drive methods splitDrive, joinDrive, takeDrive, replaceDrive, hasDrive, dropDrive, isDrive, #endif precisely to allow automated testing. And that, of course, solves the problem. But I am wondering whether other solutions to this problem could be found, perhaps even solutions that stay within the limits of the Haskell language itself? If anybody know of alternative solutions, I would very much like to hear about them. Thanks and best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] k-minima in Haskell
Hello, My Hugs tells me this: Prelude let sort [] = []; sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l in sort [1,3,2] [1,3,2] Prelude So, no, this is not a working sorting function. Inserting the few missing recursive calls: Prelude let sort [] = []; sort l@(x:_) = sort ( filter (x) l ) ++ filter (==x) l ++ sort ( filter (x) l ) in sort [1,3,2] [1,2,3] Prelude Best regards Thorkil On Friday 13 April 2007 11:38, Thomas Hartman wrote: And for reference, here is again stefan's stable quicksort from his earlier post. sort [] = [] sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l (A stable quicksort, btw) This is the code whose legitimacy I am requesting confirmation of. 2007/4/13, Thomas Hartman [EMAIL PROTECTED]: You may be missing a few recursive calls there :-) Indeed. ... ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Code and Perf. Data for PrimeFinders(was:Genuine Eratosthenes sieve)
Hello all felllow primefinders, I have followed this discussion of Haskell programs to generate small primes with the greatest interest. The thing is, I have been running my Haskell implementation of the so-called Elliptic Curve Method (ECM) of factoring for a number of years. And that method uses a sequence of small primes, precisely like the one discussed here. I have been using the method of trial division to generate primes for the ECM. I have been aware that sieving would very likely be more efficient, but since the amount of time spent generating small primes is, after all, not an extremely large part of running the ECM program, I have postponed the task of looking into this. So this discussion of Eratostenes' sieve has provided a most wonderful opportunity to do something about this. Initially, I wanted to establish some sort of base line for generating small primes. This I did by writing my own C program for generating small primes, both using sieving and trial division. The result was most sobering: Finding primes with sieving with a C program is much faster than finding them with trial division. The speed advantage factor of sieving over trial division for small numbers (say, finding the first couple of hundred thousand primes) is around 5 and it gets larger with larger numbers. (I will not quote specific measurements here, only rough tendencies. Details clutter and Melissa is much better at this anyway. I would like to state, however, that I am, in fact, measuring performance accurately, but I use ancient machinery that runs slowly: Measuring performance on fast equipment often tends to cloud significant issues, in my experience.) So there is my goal now: Find a Haskell program that generates small primes that is around 5 times faster than the one I have already that uses trial division. And I mean a Haskell program, not a C program that gets called from Haskell. Sure, if I wanted ultimate performance, I could perhaps just call some C code from Haskell. But the insistance on pure Haskell widens the perspective and makes it more likely that the programmer or the language designer and implementer learn something valuable. The C sieving program uses an array to attain its impressive performance, so let us try that in Haskell as well. Something like this has been on my mind for a long time: accumArray (\x -\y -False) True (m,n) [(q,()) | q-ps ] Haskell arrays, like every other value, cannot be changed, but accumArray provides a facility that we just might manage to use for our purpose. The particular array computed by the above expression using accumArray requires a low and high limit (m,n) of the numbers to be sieved as well as a list of sieving values - ps - numbers that need to be crossed out as composite in the interval (m,n) given. [The overhead involved in evaluating this expression with its unused () value and an indicator that is changed from True to False through throwing away two dummy values seems excessive. Any suggestion to write this up in a way that is more in agreement with the small amount of work that is actually required to do this would be most welcome. Or perhaps GHC (which is the compiler I use when I want things to run fast) takes care of things for me? In any case, this is my inner loop and even small improvements will matter.] When I tried this initially, I was actually not particularly surprised to find that it performed rather worse than trial division. Although I am unable to give a precise explanation, the GHC profiling runs indicated that, somehow, too much memory was accumulating before it was used, leading to thrashing and perhaps also a significant amount of overhead spent administering this excessive amount of memory. The initial sieve that I used had a fixed size that covered all the numbers that I wanted to test. An improvement might come about by splitting this sieve into smaller pieces that were thrown away when no longer needed. OK, what pieces? Well, a possibility would be to use the splitting of all integers into subsequences that matched the interval between squares of consecutive primes, because that would match the entry of a new prime into the set of primes that needs to be taken into consideration. And this actually worked rather well. In addition, the problem solved was now the one of expressing the generation of an infinite sequence of primes, not just the primes within some predetermined interval. Further (yes, you will get the code eventually, but be patient, I don't want to have to present more than the final version), there was the wheel idea also used by Melissa of somehow eliminating from consideration all the numbers divisible by a few of the smallest primes: If we, for example, could get away with considering only the odd numbers as candidates for being primes, this would potentially save half the work. This I didn't find to be an easy idea to implement. Essentially what I
Re: [Haskell-cafe] Fractional sqrt
Hello, On Friday 19 January 2007 16:48, [EMAIL PROTECTED] wrote: ... sqrtApprox' :: Integer - Rational sqrtApprox' n | n 0 = error sqrtApprox' | otherwise = approx n 1 where approx n acc | n 256 = (acc%1) * approxSmallSqrt (fromIntegral n) | otherwise = approx (n `div` 256) (acc*16) ... In the Haskell report section 14.4 (and also e.g. in GHC.Float), we find -- Compute the (floor of the) log of i in base b. -- Simplest way would be just divide i by b until it's smaller then b, but that would -- be very slow! We are just slightly more clever. integerLogBase :: Integer - Integer - Int integerLogBase b i | i b = 0 | otherwise = doDiv (i `div` (b^l)) l where -- Try squaring the base first to cut down the number of divisions. l = 2 * integerLogBase (b*b) i doDiv :: Integer - Int - Int doDiv x y | x b = y | otherwise = doDiv (x `div` b) (y+1) Something like this could probably be used to find a suitable sqrt approximation for an Integer: sqrtApproxViaLog i = 2^(integerLogBase 2 i `div`2) Best regards Thorkil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mozart versus Beethoven (was: Writing Haskell For Dummies ...)
Hello, In the spring of 1978, I wrote a (circa) 700-word microprogram for multiprecision integer arithmetic on paper, typed it into a computer, had it cleaned of syntax errors by the micro-code assembler, printed it, and spent much of the summer in my mother's summer house debugging this program text by hand, without the use of any automated computing device of any kind. I found lots of errors, corrected them, rechecked the result by hand, found additional errors, corrected those and, finally, (in the autumn of 1978) ran the program for the first time. Every multiprecision integer operation but division worked. After some debugging, a single (rather silly) error was found in the division routine. I never found additional errors in this code. This is not intended to imply that I am a Mozart rather than a Beethoven (most likely neither!) in the field of programming. Rather, it is an attempt to point out that the development environments that we use these days encourage a completely different mode of work than what was used some 20-30 years ago. Thus, today, I do like I have the impression most programmers do, compile and run (tests) as often as possible, even every very few keystrokes of code changes. I am not an expert in the difference between composers like Mozart and Beethoven, but my expert father tells me that Mozart, reputedly, had a phenomenal musical memory that allowed him both to recall large sequences of music played to him and, undoubtably also, work with long sequences of hypothetical music, that is, music being composed, for prolonged periods, in his head, without the need to make any notes on paper etc. It seems that such differences in modes of work does not imply any similar interesting or usefully utilizable difference in the way we should produce our programs. The analogy seems irrelevant, in other words. Best regards Thorkil On Tuesday 12 December 2006 12:07, Kirsten Chevalier wrote: ... I've been thinking about this. Are there really any programmers who are like Mozart in the way you describe? Donald Knuth might be one, or at least, he wrote that he wrote and debugged all of TeX on paper before entering it into a computer and only found 13 more bugs (or something like that), once he did. I don't remember if it was 13 exactly, but 13 more bugs might be the closest that any programmer gets to Mozart, or at least any programmer in the 20th or early 21st century. ... Cheers, Kirsten -- Kirsten Chevalier* [EMAIL PROTECTED] *Often in error, never in doubt What is research but a blind date with knowledge? -- Will Henry ___ 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
Generalized Su Doku solver (was: [Haskell-cafe] Polymorphic Sudoku solver)
Hello, Inspired by this, I have added my Su Doku solver to http://www.haskell.org/haskellwiki/Sudoku. Regards Thorkil Naur On Wednesday 31 May 2006 18:32, Chris Kuklewicz wrote: A while back there was a long thread about Sudoku solvers (some of which ended up on http://haskell.org/haskellwiki/Sudoku ). I contributed my brute-force dancing links solver at the time, and mentioned that I had a by-logic solver that, while a bit slow, was as good as most of those being discussed. At the time the code for my solver was too ugly to post. Attached is a cleaned up version. ... Chris Kuklewicz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] String to binary tree
Hello, Both my Hugs and my GHCi report a type error when presented with this. A possible repaired version looks like this: calc :: String - Float calc = g . foldl f [] . words where f (x:y:zs) + = y+x:zs f (x:y:zs) - = y-x:zs f (x:y:zs) * = y*x:zs f (x:y:zs) / = y/x:zs f xs y = read y : xs g [r] = r Not as small, but still quite nice. Regards Thorkil On Tuesday 30 May 2006 15:10, Sebastian Sylvan wrote: A bit OT perhaps, but I'd just like to point out this wonderful little code snippet from the Haskell wiki-page that I've always liked, in case nobody's seen it: calc :: String - Float calc = foldl f [] . words where f (x:y:zs) + = y+x:zs f (x:y:zs) - = y-x:zs f (x:y:zs) * = y*x:zs f (x:y:zs) / = y/x:zs f xs y = read y : xs That's it. An RPN evaluator in a couple of lines. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] String to binary tree
Hello, It seems that what you need is the technique of evaluating an expression in reverse polish notation by using a stack. This technique is well known in subjects related to compiler construction. Basically, the expression (list of operands and operators) is processed sequentially from left to right. If an operand (in your case: A character c for which isNumber c is true) is encountered, it is pushed onto the stack. If an operator (in your case: A character c for which isLetter is true) is enountered, it pops its operands (one or more) from the top of the stack and pushes the result of applying the operator to the operands back onto the stack. The following code sketch uses this idea: ... import Char ... isNumber = isDigit isLetter = isAlpha cvBase stack c | isNumber c = Folha c:stack cvBase (tr:tl:stack) c | isLetter c = Node c tl tr : stack cv s = let [t] = foldl cvBase [] s in t Example using Hugs: Main cv 12H3V Node 'V' (Node 'H' (Folha '1') (Folha '2')) (Folha '3') Main Regards Thorkil Naur On Monday 29 May 2006 20:53, Nuno Santos wrote: Hi, I have this type which represents polish expressions (floorplan representation): data PeAux a = Folha Char | Nodo Char (PeAux a) (PeAux a) deriving Show The reverse polish expression are the result of doing a post order visit to the tree One example of this reverse polish expression is 12H3V and a example of tree is pe5 = Node 'V' (Node 'H' (Folha '1') (Folha '2')) (Folha '3') the tree above is the same as the expression 12H3V What i need and i cant do is turn the expression a tree again... I have done the following: converteAux [] (x,y) = (x,y) converteAux (a:t) (x,y) | ((length (a:t))3) = converteAux [] (x,y ++ (a:t)) converteAux (a:b:t) (x,y) | ((length (a:b:t))3) = converteAux [] (x,y ++ (a:b:t)) converteAux (a:b:c:t) (x,y) | (isNumber a) (isNumber b) (isLetter c) = converteAux t (x ++ [(Nodo c (Folha a) (Folha b))],y) | otherwise = converteAux (b:c:t) (x,y++[a]) The strategy followed is to recognize operand, operand, operator and then put it as a basic element in a list, for instance, 12H - Node 'H' (Folha '1') (Folha '2') And at the end put it togheter in one tree. ( not done yet) But i'm getting to the conclusion that it doesnt cover every case... Can anybody give me a light here? Many thx, Best regards, Nuno Santos ___ 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
