[Haskell] Newbie : How come that cyclic recursive lists are efficient ?
Hi, The classical Hamming problem have the following solution in Haskell : *** BEGIN SNAP -- hamming.hs -- Merges two infinite lists merge :: (Ord a) = [a] - [a] - [a] merge (x:xs)(y:ys) | x == y= x : merge xs ys | x y= x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys -- Lazily produce the hamming sequence hamming :: [Integer] hamming = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming)) *** END SNAP I just love these algorithms that run after their tail (they make my brain melt) but I don't know how is it that they are efficient. Here, the hamming recursively calls itself three times. For this algorithm to be efficient, the Haskell system, somehow, has to remember the already generated sequence THROUGH RECURSION (i.e. not only intermediate local results) otherwise it would end up regenerating the beginning of the sequence over and over again. Obviously, Haskell does remember what had already been generated THROUGH RECURSION since executing the program with GHCI runs quite smoothly and responsively. That Haskell manages to do that is for me magnifique. But I need to know (if only a little) about how it achieves this in order to know what I, as a lambda programmer, can do, and how to compute the Big-Oh complexity of the algorithm. Thank you, Francis Girard FRANCE ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Newbie : How come that cyclic recursive lists are efficient ?
Thank you, I understand the point. But I can't help thinking that the distinction between being a list of integers and being a function that returns a list of integers (without arguments) is not always clear in FP ... since there is not really such a thing as returning a value in declarative programming, neither in mathematical thinking. Thank you Francis Girard FRANCE Le lundi 24 Janvier 2005 18:11, Graham Klyne a écrit : Notice that 'hamming' *is* a list of integers, not a function to produce them: hamming :: [Integer] Thus, the magic here is that you can define this list as a value, without having to actually evaluate any element until it's needed, either by direct reference from another function, or indirectly by the recursive definition to obtain a value directly required. But once evaluated, the deferred evaluation is replaced by the resulting value. This is the power of lazy evaluation. Even fixed values (as opposed to function calls) aren't evaluated until they're needed. #g -- At 10:38 24/01/05 +0100, Francis Girard wrote: Hi, The classical Hamming problem have the following solution in Haskell : *** BEGIN SNAP -- hamming.hs -- Merges two infinite lists merge :: (Ord a) = [a] - [a] - [a] merge (x:xs)(y:ys) | x == y= x : merge xs ys | x y= x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys -- Lazily produce the hamming sequence hamming :: [Integer] hamming = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming)) *** END SNAP I just love these algorithms that run after their tail (they make my brain melt) but I don't know how is it that they are efficient. Here, the hamming recursively calls itself three times. For this algorithm to be efficient, the Haskell system, somehow, has to remember the already generated sequence THROUGH RECURSION (i.e. not only intermediate local results) otherwise it would end up regenerating the beginning of the sequence over and over again. Obviously, Haskell does remember what had already been generated THROUGH RECURSION since executing the program with GHCI runs quite smoothly and responsively. That Haskell manages to do that is for me magnifique. But I need to know (if only a little) about how it achieves this in order to know what I, as a lambda programmer, can do, and how to compute the Big-Oh complexity of the algorithm. Thank you, Francis Girard FRANCE ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell Graham Klyne For email: http://www.ninebynine.org/#Contact ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: To show or not to show french accents
Hello, What I don't understand is why you want show for this. As I mentioned earlier, to output strings and get accented characters, all you have to do is to output the string with putStr, and voilà, les signes diacritiques. Sometimes, I want to do cheap and dirty test programs that shows data structures involving some strings. Again, the cheap and dirty way to do this is to derive the data structure from Show using the deriving keyword. But then, you are sometimes barely able to just read the outputed string. Therefore I have to redefine show myself ... Which is a lot less cheap and a lot more dirty. The problem is that if you are reading single bytes, 233 is not necessarily é. It might be 'shch' if you are in Russia, What the byte should represents is not relevant here. All I wanted to point out, is that it is easier to read a character as a one byte (or two) instead of 4 and translate 4 characters into a numerical value, NO MATTER WHAT THE BYTE IS SUPPOSED TO REPRESENT. This was to answer an opposition that was maintaining that show was meant to be Read. I simply answered that that was not a valid argument. arithmetic right). Since Haskell specifies unicode, if you are operating in a Russian locale that's what ought to happen. I naively tought that unicode would solve these kind of problems. But yet we're stucked with these pesky 7 bits ... Regards, Francis Girard LE CONQUET France Selon Jon Fairbairn [EMAIL PROTECTED]: On 2003-12-18 at 16:40+0100 [EMAIL PROTECTED] wrote: Good evening, OK. I don't know Haskell enough to argue. But I can't resist pointing out that reading a single byte having the value 233 (that is 'é') The problem is that if you are reading single bytes, 233 is not necessarily é. It might be 'shch' if you are in Russia, or iota if you are in Greece. While it's (almost) completely reasonable to expect 233 to display as é in Western Europe, it's completely unreasonable to hold that expectation across borders. is certainly simpler than reading the four characters \233, parse it, and translate it into a single byte but it isn't a single byte internally. Indeed, if you are in Russia you could reasonably expect reading a single byte 233 to be converted to the internal code 1257 (if I got the arithmetic right). Since Haskell specifies unicode, if you are operating in a Russian locale that's what ought to happen. What I don't understand is why you want show for this. As I mentioned earlier, to output strings and get accented characters, all you have to do is to output the string with putStr, and voilà, les signes diacritiques. Jón -- Jón Fairbairn [EMAIL PROTECTED] ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: To show or not to show french accents
Good evening, OK. I don't know Haskell enough to argue. But I can't resist pointing out that reading a single byte having the value 233 (that is 'é') is certainly simpler than reading the four characters \233, parse it, and translate it into a single byte having the value 233 representing no matter what character in your character table. But, I don't care that much and I'm sorry for this. Best regards, Francis Girard LE CONQUET France Selon Carsten Schultz [EMAIL PROTECTED]: Hallo! On Thu, Dec 18, 2003 at 01:55:27PM +0100, [EMAIL PROTECTED] wrote: Well, I think there should probably be some internationalisation mechanism that tells the show function (to name one), according to some configuration, how to interpret a byte as a character. My understanding is that `show' should work with `read' and possibly produce output that can be parsed by the Haskell parser. It is not a pretty printing function. Frankly, I see no good reason why we should be satisfied we the dinosaurus 7 bits except perhaps because 7 bits is sufficient for english. I am talking about respect for non english speaking people. But if nobody cares ... I, too, speak a language that can't be fully expressed in ASCII, but I do not think that the behaviour of `show' should be changed in this respect. Greetings, Carsten -- Carsten Schultz (2:38, 33:47), FB Mathematik, FU Berlin http://carsten.fu-mathe-team.de/ PGP/GPG key on the pgp.net key servers, fingerprint on my home page. Original message : The following haskell program : -- module Main where accentLetters :: String accentLetters = éàô main :: IO () main = do putStr (show accentLetters) -- after being compiled will give the result : \233\224\244 But, exactly the same program, without the show function will give the result: éàô Is there some way to have show show all the printable characters, even those represented by a value greater than the US-ASCII 7 bits (127) ? ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: How do I find out a function's strictness?
Hi, Thank you all for your answers. I recompiled with -O option and now I can see the strictness analysis in the interface files. Notice however that if I compile with the -prof -auto-all -O flags then I got the following error message when I try to examine the interface file (with --show-iface) : mismatched interface file versions: expected 5043, found 5043p Thank you Francis Girard [EMAIL PROTECTED] LE CONQUET, France Le 17 Juin 2003 13:00, Simon Marlow a écrit : In the ghc manual I read : How do I find out a function's strictness? Don't guess-look it up. Look for your function in the interface file, then for the third field in the pragma; it should say __S string. The string gives the strictness of the function's arguments. L is lazy (bad), S and E are strict (good), P is primitive (good), U(...) is strict and unpackable (very good), and A is absent (very good). -- When I look in the *.hi binary files generated by ghc with ghc --show-iface, I don't see anything like __S anywhere. Where should I look ? Make sure the module is compiled with -O, otherwise the strictness analyser isn't run and you don't get any strictness info. Cheers, Simon ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
How do I find out a function's strictness?
Hi, In the ghc manual I read : How do I find out a function's strictness? Don't guess-look it up. Look for your function in the interface file, then for the third field in the pragma; it should say __S string. The string gives the strictness of the function's arguments. L is lazy (bad), S and E are strict (good), P is primitive (good), U(...) is strict and unpackable (very good), and A is absent (very good). -- When I look in the *.hi binary files generated by ghc with ghc --show-iface, I don't see anything like __S anywhere. Where should I look ? Thank you Francis Girard [EMAIL PROTECTED] LE CONQUET, France ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: ANNOUNCE: GHC version 5.04.2 released
Why is the windows .msi file is more than twice as big as the Linux binary file ? ~35 Mb / ~16 Mb. With my slow and unstable french internet connection, 35 Mb is more than I can afford. Thank you Francis Girard Le Conquet France Le 5 Décembre 2002 02:54, Sigbjorn Finne a écrit : Simon Marlow [EMAIL PROTECTED] writes: == The (Interactive) Glasgow Haskell Compiler -- version 5.04.2 == ... A Win32 installer is now available via the downloads page http://haskell.org/ghc/download_ghc_504.html The installer this time also includes ObjectIO. --sigbjorn ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: diff in Haskell: clarification
You caught my attention. It would be nice if you write your own version from scratch to make all of us profit of this. Thank you. Francis Girard Le Conquet France Le 22 Novembre 2002 16:03, George Russell a écrit : I think in fact I'm going to give up on stealing other people's code and write my own version from Myer's paper. George ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
EVACUATED object entered! (when doing FFI)
Good morning, I wrote a very small program, and it executed ok. I wanted to export a function in C, and therefore wrote a C wrapper function over it to invoke peekCString and peekArray on the input; newCString and newArray on the output. I then did a small C driver program. Everything compiled and linked correctly. But at execution the program prints : EVACUATED object entered! as soon as startupHaskell is invoked (i.e. even before I call my foreign exported function !) What is the meaning of this message ? Thank you Francis Girard Le Conquet France ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
FFI : A failing example
Hello, I'm a beginner trying to use FFI. I copied the example given in : The Glasgow Haskell Compiler User's Guide, Version 5.04 Chapter 8. Foreign function interface (FFI) -- module Foo where foreign export ccall foo :: Int - IO Int foo :: Int - IO Int foo n = return (length (f n)) f :: Int - [Int] f 0 = [] f n = n:(f (n-1)) -- Copied it verbatim. And simply tried to compile it using ghc -c Foo.hs -o Foo.o and always got the error : Type signature given for an expression (at the line following the foreign export) I then tried to import the Foreign and Foreign.C modules but it didn't change anything. I am missing something and I would be VERY grateful to anyone that tells me what. Thank you Francis Girard Le Conquet (France) [EMAIL PROTECTED] ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Is their a *good* online tutorial and reference for Haskell?
"Frank A. Christoph" wrote: These fonts are especially recommended for use with pdfTeX. In fact, for PDF output one should not even consider applying the bitmap fonts for they produce terrible results, whether generated with pdfTeX or with the Distiller program. Is this why the PDF version of the Haskell report looks so strange? On my system (Win98 and Acrobat Reader 4.0) it looks like the baseline oscillates up and down between each letter. I find it very difficult to read. I've seen the same effect on other PDF-converted technical reports which were obviously produced with TeX/LaTeX. With Acrobat Reader 3.0 on Solaris, I don't see the same effect, although the lettering looks very cruddy (even with anti-aliasing on) and is equally hard to read. I had been meaning to mention these facts earlier... It would be nice if someone could regenerate the Reports. --FC Yes, I think it is probably the reason although I can't be sure. It certainly won't hurt to try these fonts especially designed for pdfTeX when compiling the LaTeX sources of the documents By the way, I agree with you that some people will never be satisfied, probably because they are scared of the necessary effort required by a paradigm shift as a shift from an imperative language to a declarative one. I am myself new to Haskell. It requires a lot of effort and that sometimes hurt a guy with a lot of experience with imperative languages like me. Cheers Francis Girard Rimouski, Québec, Canada [EMAIL PROTECTED]
