RE: [Haskell-cafe] Flattening tail recursion?
I have not been following the details, but yes, the strictness analyser only runs when you say -O, and without strictness analysis you can get different space behaviour. Sometimes more, sometimes less. In this case, strictness analysis helps. Simon | -Original Message- | From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Jules | Bean | Sent: 10 December 2004 21:38 | To: GoldPython | Cc: Henning Thielemann; haskell-cafe | Subject: Re: [Haskell-cafe] Flattening tail recursion? | | | On 10 Dec 2004, at 20:33, GoldPython wrote: | | Just compiled this with -O and it ran with no stack overflow. | Evidently, no `seq` needed for this one. Using ghc 6.2.2. | | countLines l = countLines' 0 l | countLines' n [] = n | countLines' n (_:ls) = countLines' (n + 1) ls | | | That's presumably the answer. GHC's strictness analyser *can* cope with | this situation but only under -O... whereas most of us where testing | under ghci... | | Confirmation from one of the Simons? | | Jules | | ___ | Haskell-Cafe mailing list | [EMAIL PROTECTED] | http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] AbstractDataType question
Tomasz Zielonka [EMAIL PROTECTED] writes: Record field labels can be also used in pattern matching and in record update. Especially the latter is very useful. But not quite as elegant -- while record query lets you modify the underlying structure and replace the old record queries with functions, I don't think there's a way to do this for record updates (or am I wrong?) -kzm -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Flattening tail recursion?
Hi everyone, I had the idea that, instead of using 'seq', one might check for parity: countLines2 aux (_:l) | even aux = ... | odd aux = ... that prevents stack overflow, but is much slower than countLines1 aux (_:l) | aux `seq` False = ... | otherwise = ... I also tried countLines3 aux (_:l) | even aux || odd aux = ... | otherwise = ... and countLines4 aux (_:l) | even aux || True = ... | otherwise= ... which also are slower than countLines1. Well, checking for parity takes time, so that is no real surprise. What somehow puzzles me is that, compiling with -O, all versions of countLines are equally fast, if I give the type countLines :: Int - [a] - Int, but if I replace Int with Integer, the plain version without guards and the 'seq' version are equally fast whereas the parity-check versions are equally fast among themselves but slower than plain. If I omit the type-declaration, all versions perform differently, plain producing stack overflow, countLines1 being by far the fastest, countLines4 coming in second, then countLines3 and last countLines2. If I give the type Int - [a] - Int and use interpreted code, plain overflows, countLines1 is by far the fastest, but then things change. Now countLines2 comes in second, third is countLines4, relatively close, last, at a distance, is countLines3. (Qualitatively the same, but slower, without type-declaration). With type Int - [a] - Int, but compiled without -O, the results are (for countLinesX 0 [1 .. 150]) plain : stack overflow, 1 : 0.43 secs, 2 : 1.10 secs, 3 : 1.26 secs, 4 : 0.93 secs. Now obviously -O does a good job (though 'seq' isn't so bad even without -O), but why does checking for parity take extra time for Integer and not for Int? And why does compilation without -O change the order of versions 2-4 ? If anybody knows, mind telling me? Thanks in advance, Daniel Am Freitag, 10. Dezember 2004 22:37 schrieb Jules Bean: On 10 Dec 2004, at 20:33, GoldPython wrote: Just compiled this with -O and it ran with no stack overflow. Evidently, no `seq` needed for this one. Using ghc 6.2.2. countLines l = countLines' 0 l countLines' n [] = n countLines' n (_:ls) = countLines' (n + 1) ls That's presumably the answer. GHC's strictness analyser *can* cope with this situation but only under -O... whereas most of us where testing under ghci... Confirmation from one of the Simons? Jules ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] FiniteMapFiniteMap
On Mon, 2004-12-13 at 14:56 -0500, S. Alexander Jacobson wrote: Hmm cool. Binary does not appear in the GHC docs... Is it new? Ah, it's not a user library distributed with GHC, it's a library used internally in the implementation of GHC. If you want to use it you have to rip it out of the ghc source tree. :-) That said, it's actually quite a free-standing module. A version cleaned of most ghc dependencies (it still depends on FastMutInt) is available here: http://cvs.sourceforge.net/viewcvs.py/*checkout*/gtk2hs/gtk2hs/tools/c2hs/base/general/Binary.hs?rev=1.1 http://cvs.sourceforge.net/viewcvs.py/*checkout*/gtk2hs/gtk2hs/tools/c2hs/base/general/FastMutInt.hs?rev=1.1 One quick hack I made that you might need to fix is that I did: #define SIZEOF_HSINT 4 whereas of course SIZEOF_HSINT should come from /usr/lib/ghc-$VER/include/MachDeps.h or some config.h file generated by ./configure. Of course that is what the version in ghc's sources does. Duncan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] special term describing f :: (Monad m) = (a - m b) ?
What is a function of the followning type called: f :: (Monad m) = (a - m b) Is there a special term describing such a function (a function into a monad)? For f in a = f is en example. Need it for an article/report. Regards/Henning ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] special term describing f :: (Monad m) = (a - m b) ?
What is a function of the followning type called: f :: (Monad m) = (a - m b) Is there a special term describing such a function (a function into a monad)? It is often called a procedure or an effectful function (I assume that `a' and `b' are not meant to be universally quantified). I sometimes use a special arrow -| for this type. Cheers, Ralf ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Named function fields vs. type classes
Hi, I often have a situation where I'm designing specialized components to do a more general task. Examples could include mail folder code (maildir, mbox, etc), configuration file parsing, protocol handlers for URL accesses, logging backends, etc. For some of these, I've used a data object with named fields, each one of them being a function that performs various tasks (open connection to the URL, read data, whatever.) So, I get a standard interface. The advantage of this approach is that I can build a list containing all sorts of different data objects in it. For others, I've used typeclasses, and made the different specialized components a member of the typeclass. This seems to provide a cleaner interface, and one that is more readily extended (maybe I want to support IMAP folders, and support all its searching capabilities too). On the other hand, it's difficult or impossible to make a list of a bunch of different types of things that have nothing in common save being members of the class. Is there any advice on the best way to do these things? Thanks, John ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Named function fields vs. type classes
Major apologies for this repeated plug for HList. Anyway, HLists [1] are *exactly* designed for this sort of problem. Well, one can also use existential quantification + bounded polymorphism; with the shapes benchmark providing a good example [2]. The trade-offs are explored a little bit on the OOHaskell slides and in the corresponding code base [3]. Cheers, Ralf [1] http://homepages.cwi.nl/~ralf/HList/ [2] http://www.angelfire.com/tx4/cus/shapes/haskell.html [3] http://homepages.cwi.nl/~ralf/OOHaskell/ John Goerzen wrote: Hi, I often have a situation where I'm designing specialized components to do a more general task. Examples could include mail folder code (maildir, mbox, etc), configuration file parsing, protocol handlers for URL accesses, logging backends, etc. For some of these, I've used a data object with named fields, each one of them being a function that performs various tasks (open connection to the URL, read data, whatever.) So, I get a standard interface. The advantage of this approach is that I can build a list containing all sorts of different data objects in it. For others, I've used typeclasses, and made the different specialized components a member of the typeclass. This seems to provide a cleaner interface, and one that is more readily extended (maybe I want to support IMAP folders, and support all its searching capabilities too). On the other hand, it's difficult or impossible to make a list of a bunch of different types of things that have nothing in common save being members of the class. Is there any advice on the best way to do these things? Thanks, John ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The difference between ($) and application
On Tue, Dec 14, 2004 at 11:23:24AM +0100, Henning Thielemann wrote: On Tue, 14 Dec 2004, Andrew Pimlott wrote: (Of course, it's still useful, by itself or in a slice, as a higher-order operator.) You can also use 'id' in this cases, right? I'm thinking of things like zipWith ($) map ($ x) Andrew ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Named function fields vs. type classes
On the other hand, it's difficult or impossible to make a list of a bunch of different types of things that have nothing in common save being members of the class. I've recently been playing with making, for each class C, a interface datatype IC (appropriately universally and existentially qualified so as to include a dictionary for class C), and then making this IC an instance of class C. Then I can wrap any instance of C up in an IC, and make a list of those. The casts get a bit annoying, though; the compiler can't figure out that this IC is in some sense the maximum type in class C, and so can't resolve things like f :: MyClass a = [a] - b f = ... upcast :: MyClass a = a - IMyClass -- usually defined as an instance of class Cast upcast x = IMyClass x f [upcast a, upcast b] -- yields type error Instead, you have to redefine f as follows: f' :: [IMyClass] - b which is a bit annoying. HTH. --KW 8-) ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] AbstractDataType question
On Mon, Dec 13, 2004 at 11:29:56AM +0100, Ketil Malde wrote: Tomasz Zielonka [EMAIL PROTECTED] writes: Record field labels can be also used in pattern matching and in record update. Especially the latter is very useful. But not quite as elegant -- while record query lets you modify the underlying structure and replace the old record queries with functions, I don't think there's a way to do this for record updates (or am I wrong?) No, I think you are right. Best regards, Tomasz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Flattening tail recursion?
Will,
countLines [] = 0
countLines (_:ls) = 1 + countLines ls
I would have thought that this was tail recursive and would be
flattened into iteration by the compiler. Can anyone explain why? Is
it because the call is embedded in an expression?
This is the tail-recursive version:
\begin{code}
countLines = countLines' 0
where countLines' k [] = k
countLines' k (l : ls) = countLines' (k + 1) ls
\end{code}
See, for example, http://www.haskell.org/hawiki/TailRecursive.
HTH,
Stefan
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Flattening tail recursion?
On Mon, Dec 13, 2004 at 11:56:45AM +0100, Daniel Fischer wrote: I had the idea that, instead of using 'seq', one might check for parity: countLines2 aux (_:l) | even aux = ... | odd aux = ... that prevents stack overflow, but is much slower than countLines1 aux (_:l) | aux `seq` False = ... | otherwise = ... I also tried countLines3 aux (_:l) | even aux || odd aux = ... | otherwise = ... and countLines4 aux (_:l) | even aux || True = ... | otherwise= ... which also are slower than countLines1. Well, checking for parity takes time, so that is no real surprise. What somehow puzzles me is that, compiling with -O, all versions of countLines are equally fast, if I give the type countLines :: Int - [a] - Int, but if I replace Int with Integer, the plain version without guards and the 'seq' version are equally fast whereas the parity-check versions are equally fast among themselves but slower than plain. This is likely because since Int is builtin to the compiler and compiled directly into 'case' statments in core, it can deduce that one of even or odd must be true and via normal case simplifications transform (even x || odd x) directly into (x `seq` True). Integer, however is implemented partially by the gmp library, so ghc is less privy to its internals and probably was unable to deduce that one of even or odd must be true for Integer. In particular, pattern matching on Integers is implemented via nested equality tests rather than direct case statements. (AFAIK) If I omit the type-declaration, all versions perform differently, plain producing stack overflow, countLines1 being by far the fastest, countLines4 coming in second, then countLines3 and last countLines2. This is because if you omit the type declaration, ghc will deduce the much more general type of countLines :: Num a = [x] - a which in ghc's implementation of overloading will take an extra argument describing how to work on 'a's and call the overloaded functions, the compiler cannot know how they are implemented so is unable to apply certain transformations. If I give the type Int - [a] - Int and use interpreted code, plain overflows, countLines1 is by far the fastest, but then things change. Now countLines2 comes in second, third is countLines4, relatively close, last, at a distance, is countLines3. (Qualitatively the same, but slower, without type-declaration). With type Int - [a] - Int, but compiled without -O, the results are (for countLinesX 0 [1 .. 150]) plain : stack overflow, 1 : 0.43 secs, 2 : 1.10 secs, 3 : 1.26 secs, 4 : 0.93 secs. Now obviously -O does a good job (though 'seq' isn't so bad even without -O), but why does checking for parity take extra time for Integer and not for Int? see first response above for my guess :) And why does compilation without -O change the order of versions 2-4 ? This is likely because of strictness analysis. What strictness analysis does in effect is analyze the program to determine whether a result will definitly be required, it is a rather expensive operation in the presence of higher order and mutually recursive functions, but the end result is that if ghc deduces that a value will always be needed, such as the first argument to countLines', it places (the equivalant) of a seq in there for you :). This is called the 'let-to-case' transformation in the compiler because a 'case' always evaluates its argument in the internal language while a let allocates a lazy thunk. It is just something that one must get used to in haskell programming (with ghc at least) that -O can have drastic order changing effects compared to the relativly incremental ones for other languages. The various papers available on the net regarding ghc's internals are fascinating if you are interested in the various optimizations it trys. If anybody knows, mind telling me? nope :). A lot of the above is speculation, I am by no means a ghc expert, but I belive it is what is happening. -- John Meacham - repetae.netjohn ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] The difference between ($) and application
The operator ($) is often considered an application operator of a
lower precedence. Modulo precedence, there seem to be no difference
between ($) and `the white space', and so one can quickly get used to
treat these operators as being semantically the same. However, they
are not the same in all circumstances. I'd like to observe an
important case where replacing the application with ($) in a
fully-parenthesized expression can lead to a type error.
{-# OPTIONS -fglasgow-exts #-}
module Foo where
data WR = WR (Int - Int)
data W = W (forall a. a-a)
t1 = WR id
t2 = W id
We can also write
t1' = WR $ id
However, if we try
t2' = W $ id
we get an error:
/tmp/t1.hs:13:
Inferred type is less polymorphic than expected
Quantified type variable `a' escapes
Expected type: (a - a) - b
Inferred type: (forall a1. a1 - a1) - W
In the first argument of `($)', namely `W'
In the definition of `t2'': t2' = W $ id
Incidentally, Hugs -98 gives a quite bizarre error message
ERROR /tmp/t1.hs:13 - Use of W requires at least 1 argument
It didn't complain about WR $ id...
The reasons for that behavior are obvious: the compiler cannot
generalize to higher-ranked types when instantiating the type of
($). It makes a difference that the application is a built-in
construction, whereas ($) is just a regular function.
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The difference between ($) and application
On Mon, Dec 13, 2004 at 07:49:00PM -0800, [EMAIL PROTECTED] wrote: The operator ($) is often considered an application operator of a lower precedence. Modulo precedence, there seem to be no difference between ($) and `the white space', and so one can quickly get used to treat these operators as being semantically the same. However, they are not the same in all circumstances. I'd like to observe an important case where replacing the application with ($) in a fully-parenthesized expression can lead to a type error. I think this post should go under the heading ($) considered harmful. I've been bitten by this, and I never use ($) anymore in place of parentheses because it's too tempting to think of it as syntax. (Of course, it's still useful, by itself or in a slice, as a higher-order operator.) Andrew ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
