Re: FFI question -- was: [Haskell-cafe] New slogan for haskell.org
On Thu, 20 Dec 2007 03:41:21 + Duncan Coutts [EMAIL PROTECTED] wrote: The main advantage of c2hs over hsc2hs is that c2hs generates the correct Haskell types of foreign imports by looking at the C types in the header file. This guarantees cross language type safety for function calls. It also eliminates the need to write foreign imports directly which saves a lot of code. hsc2hs provides no help for writing function imports. The main disadvantage of c2hs compared to hsc2hs is that c2hs's support for marshaling structures is less than stellar while hsc2hs is pretty good at that. In gtk2hs we use both. We use c2hs for all function calls and we use hsc2hs to help us write Storable instances for a few structures. It looks that c2hs does more than hsc2hs and misses less than hsc2hs. Why not equip c2hs to do the rest and have one complete tool instead of the two uncomplete ones? (I understand that time-factor could be the reason.) I am for the choice, but there are several library-areas (database binding is one) in Haskell where we could (maybe) apply/strive for less is better slogan ;) Sincerely, Gour ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: MonadFix
On 12/20/07, Joost Behrends [EMAIL PROTECTED] wrote:
The syntax with the block in
newtype State s a = State { runState :: s - (a,s) }
is not in the tutorials i read.
newtype creates a new type which is treated exactly the same as an existing
type at runtime, but which is distinct to the typechecker.
For example, this code:
newtype X = MkX [Int]
-- MkX :: [Int] - X
unX :: X - [Int]
unX (MkX val) = val
Now, you cannot call sum (MkX [1,2,3]) because sum takes a list and you're
passing an X. But you can call sum (unX (MkX [1,2,3])). Since this is
a newtype, the work done in unX and MkX is entirely erased at runtime;
no allocation or pointer-following takes place.
The syntax given is slightly more complicated:
newtype State s a = State { runState :: s - (a,s) }
This is using the record syntax for data constructors, but it's basically
the same as the following:
newtype State s a = State (s - (a,s))
runState (State f) = f
So, runState is just unwrapping the function from the newtype. Since this
is a newtype, there's no actual pointer traversal taking place; the
distinction is only made during typechecking.
The following two functions should compile to exactly the same machine code:
test1 :: Int - ((), Int)
test1 = \x - ((), x+1)
test2 :: Int - ((), Int)
test2 = runState (State (\x - ((), x+1)))
And i do not understand
... passed the DivIter directly along . Passed along ??
Recall your original code:
divisions :: State DivIter DivIter
divisions = do
y - get
if divisor y = bound y then do
put ( divstep y )
divisions
else
return y
Lets de-sugar that:
divisions = get = \y -
if divisor y = bound y
then (put (divstep y) divisions)
else return y
Inlining get, put, and return:
divisions = (State (\s - (s,s))) = \y -
if divisor y = bound y
then (State (\s - ((), divstep y)) divisions)
else State (\s - (y, s))
After inlining (=) and (), and running a few simplification passes (in
particular, runState (State x) = x, and beta-reduction), you end up with
this:
divisions = State (\y -
if divisor y = bound y
then runState divisions (divstep y)
else (y,y))
You can remove the State monad from this pretty trivially:
divisions :: DivIter - (DivIter, DivIter)
divisions y =
if divisor y = bound y
then divisions (divstep y)
else (y,y)
or,
divisions y
| divisor y = bound y = divisions (divstep y)
| otherwise = (y,y)
This version of the code threads the DivIter state manually through each
call, but it's exactly the same as what the State version is doing. No
destructive updates anywhere to be seen!
-- ryan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: MonadFix
Joost Behrends wrote: apfelmus writes: How about separating the candidate prime numbers from the recursion factorize :: Integer - [Integer] factorize = f primes' where primes' = 2:[3,5..] f (p:ps) n | r == 0= p : f (p:ps) q | p*p n = [n] | otherwise = f ps n where (q,r) = n `divMod` p (besides: p intsqrt n must stay, otherwise you have the expensive p*p at every step) Huh? p intsqrt n is evaluated just as often as p*p n , with changing n . Why would that be less expensive? Btw, the code above test for r==0 first, which means that the following p*p n is tested exactly once for every prime candidate p . Providing effectively primes' for that is simply impossible talking about really big numbers as i did in my post. There are no fast generators iterating just through the primes firstly Sure, that's why I called it primes' . It's indented to be an easily computable list of prime candidates and as you write below, we can do better than using all odd numbers for that. and these lists get much too big also (for 2^120 you cannot even begin to use a list of the primes up to 2^(any appropriate x) ). Thanks to lazy evaluation, the list will be generated on demand and its elements are garbage collect once used. So, the code above will run in constant space. The list is more like a suspended loop. What can be done is to iterate through odd numbers meeting as many primes as possible. We could do this: iterdivisors x | x == 0 = 3 | x == 1 = 5 | otherwise x = iterdivisors (x-1) + ((cycle [2,4]) !! x) This gives 7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,63,67 ... i.e. exactly all primes and odds with greater primefactors as 3. We can improve that cycle avoiding the multiples of 5: ... | otherwise x = iterdivisors (x-1) + ((cycle [2,4,2,4,2,4,6,2,6] !! x) and we can do better by avoiding the multiples of 7 and so on (the length of these lists grows fast - it gets multiplied by every new avoided prime -, but we could provide that lists programmatically). And we must be sure, that cycle doesn't eat up memory for each new pass through the list. And we should use a more efficient representaion for the list of summands than a list. Huh, this looks very expensive. I'd avoid indices like x altogether and use a plain list instead, we don't need random access to the prime candidates, after all. But the title of my post and much more interesting topic for learning Haskell is, how to avoid memory exhaustion by recursion. Maybe you stumbled over common examples for a stack overflow like foldr (+) 0 foldl (+) 0 whereas foldl' (+) 0 runs without. See also http://en.wikibooks.org/wiki/Haskell/Performance_Introduction http://www.haskell.org/haskellwiki/Stack_overflow THIS was my intention and the reason why i erroneously brought MonadFix into the game. The recursion i described as follows divisions = do y - get if divisor y = bound y then do put ( divstep y ) divisions else return y makes a DESTRUCTIVE UPDATE of the DivIters (by put) Huh? The State monad doesn't do destructive updates, to the contrary. (neither do IORefs or STRefs, only STArrays or something do). and this kind of recursion seems not to remember itself (as i have understood, that is achieved by tail recursion). I just didn't like making DivIters to States. It's kind of lying code. Because of lazy evaluation, tail recursion is not what it seems to be in Haskell. However it worked and improved performance by a factor around 10 (or oo - perhaps a normal recursion exhausts 512MB memory for 2^120+1, as it will do for much smaller Integers, if they are prime) not to talk about footprint. Compiled for running standalone, it took 17 minutes, an equivalent python script 2 hours. This factor near 7 is not fully satisfactory. Using the State monad introduces unnecessary overhead. Also, I assume that you ran the compiler with the -O2 flag to enable optimizations? Or is there still a way of getting a tail recursive Haskell function for iterating through the DivIters (outside any monads) ?? I would not get stroke dead by surprise if yes, but i couldn't find any. I don't understand why you use a complicated DivIters data structure. Passing two simple parameters does the job just fine. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Applying a Dynamic function to a container of Dynamics
Hi all, dynApp allows to apply a Dynamic function to a Dynamic argument: dynApp :: Dynamic - Dynamic - Dynamic I don't seem to find a way (without modifying Data.Dynamic itself) to code this function import Data.Typeable import Data.Dynamic import Data.Foldable dynApp1 :: (Typeable1 container, Foldable container) = Dynamic - container Dynamic - Dynamic dynApp1 f-- originally of type :: container a - b val --- all its values _must_ have type :: b -- I get stuck when trying to transform val to type Dynamic (transform :: container Dynamic - Dynamic) in order to apply f nor even the more concrete case of lists dynAppList :: Dynamic - [Dynamic] - Dynamic Any suggestions? Thanks, Fons ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: MonadFix
Am Freitag, 21. Dezember 2007 11:33 schrieb apfelmus: Joost Behrends wrote: apfelmus writes: How about separating the candidate prime numbers from the recursion factorize :: Integer - [Integer] factorize = f primes' where primes' = 2:[3,5..] f (p:ps) n | r == 0= p : f (p:ps) q | p*p n = [n] | otherwise = f ps n where (q,r) = n `divMod` p (besides: p intsqrt n must stay, otherwise you have the expensive p*p at every step) Huh? p intsqrt n is evaluated just as often as p*p n , with changing n . Why would that be less expensive? Btw, the code above test for r==0 first, which means that the following p*p n is tested exactly once for every prime candidate p . However, when you do the sensible thing (which Joost did) and have the intsqrt a parameter of the function, like in factorize :: Integer - [Integer] factorize n = f n (intsqrt n) primes' where primes' = something more or less clever here f m sr (p:ps) | r == 0= p:f q (intsqrt q) (p:ps) | p sr= if m == 1 then [] else [m] | otherwise = f m sr ps where (q,r) = m `quotRem` p , then you only have the expensive intsqrt for each prime factor, and the test for each candidate is only one comparison instead of one multiplication and one comparison. Since usually the number of prime factors is minuscule compared to the number of candidates to be tested, that's indeed faster for most inputs (in my tests ~28.5% less run time). Some speed is also gained by using quotRem instead of divMod (pace, Henning, I agree divMod is preferable, but quotRem is a primitive). But of course, the most could be gained from a better algorithm. Regards, apfelmus Cheers, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: announcing darcs 2.0.0pre2
On Mon, Dec 17, 2007 at 12:29:20PM +, Simon Marlow wrote: David Roundy wrote: I am pleased to announce the availability of the second prerelease of darcs two, darcs 2.0.0pre2. Thanks! Continuing my performance tests, I tried unpulling and re-pulling a bunch of patches in a GHC tree. I'm unpulling about 400 patches using --from-tag, and then pulling them again from a local repo. Summary: darcs2 is about 10x slower than darcs1 on unpull, and on pull it is 100x slower in user time but only 20x slower in elapsed time. I'm not seeing this behavior right now, but am unsure whether it's because of something in my testing, or if I've improved something. I definitely fixed a problem in the no-patches-to-pull case, where we were unnecessarily reading the entire repository because of inadequate laziness. Another possibility is that the problem is one that shows up because of the way the repositories were generated. Incidentally, I *think* that with the latest convert, optimize should be a noop, and if it's not, I'd be interested to hear (but haven't gotten around to testing...). I suspect that if you perform the same sequence in the reverse direction (unpull and repull, but running the commands in the other repository), then you'll see much better performance. My suspicion is that the trouble is that optimize only optimizes for changes since the last tag, so by unpulling this many patches you're going back into unoptimized territory. I'm toying with making optimize do a deep optimize, but then it'll always be O(N^2), which is a little scary. On the other hand, since we now auto-optimize, making the real thing more expensive shouldn't hurt as much (since it'll not be needed very often). Anyhow, could you retry this test with the above change in methodology, and let me know if (a) the pull is still slow the first time and (b) if it's much faster the second time (after the reverse unpull/pull)? Thanks! David (who is doing darcs hacking in the morning, before the other grownups wake up) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: MonadFix
@apfelmus, please read my code. I introduced DivIter to separate divstep from divisions. But it stores intsqrt dividend also. Thus the sqrt is only recomputed, when a new factor is found. Concerning primes': With the sieve of Eratosthenes we cannot make a lazy list, we need the whole list at any point of computation. And beyond the end we fall back to x - x+2. This is the difference to the list of summands i proposed. And we have the arbitrary choice of [2,4], [2,4,2,4,2,4,2,6,2,6] or any longer. Concerning State: There is useful instruction by Ryan Ingram too here. I will study that and yours. Thank you ! Cheers, Joost ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: MonadFix
@apfelmus, please read my code. I introduced DivIter to separate divstep from divisions. But it stores intsqrt dividend also. Thus the sqrt is only recomputed, when a new factor is found. Concerning primes': With the sieve of Eratosthenes we cannot make a lazy list, we need the whole list at any point of computation. And beyond the end we fall back to x - x+2. This is the difference to the list of summands i proposed. And we have the arbitrary choice of [2,4], [2,4,2,4,2,4,2,6,2,6] or any longer. Concerning State: There is useful instruction by Ryan Ingram too here. I will study that and yours. Thank you ! Cheers, Joost ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] nice simple problem for someone struggling....
I'm just trying to pick up the basicsand I've managed to write this code...which remarkably works.. module Main where data SquareType = SquareConstructor Int class ShapeInterface shape where area :: shape-Int data ShapeType = forall a. ShapeInterface a = ShapeType a instance ShapeInterface SquareType where area (SquareConstructor sideLength) = sideLength * sideLength main = do putStrLn (show (area (SquareConstructor 4))) name - getLine putStrLn But my next iteration was to try to parametise SquareType So something like data SquareType a = Num a = SquareConstructor a but of course doing this breaks everything...sepecifically the instance declaration `SquareType' is not applied to enough type arguments Expected kind `*', but `SquareType' has kind `* - *' In the instance declaration for `ShapeInterface SquareType' And I can't seem to get it to work. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nice simple problem for someone struggling....
Nicholls, Mark wrote: *instance* ShapeInterface SquareType *where* area (SquareConstructor sideLength) = sideLength * sideLength *data* SquareType a = Num a = SquareConstructor a Now you have changed your type from SquareType to SquareType a, you need to change the instance to: instance ShapeInterface (SquareType a) where... Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: MonadFix
Daniel Fischer wrote: apfelmus writes: | r == 0= p : f (p:ps) q | p*p n = [n] | otherwise = f ps n However, when you do the sensible thing (which Joost did) and have the intsqrt a parameter of the function, like in factorize :: Integer - [Integer] factorize n = f n (intsqrt n) primes' where primes' = something more or less clever here f m sr (p:ps) | r == 0= p:f q (intsqrt q) (p:ps) | p sr= if m == 1 then [] else [m] | otherwise = f m sr ps where (q,r) = m `quotRem` p , then you only have the expensive intsqrt for each prime factor, and the test for each candidate is only one comparison instead of one multiplication and one comparison. Ah thanks, sorry for not seeing it earlier. My thinking was that intsqrt q is calculated multiple times (for q , q/p, q/p^2, ...) per prime candidate p when n is divisible by a large power of p . But I didn't see that, in return, intsqrt q stays the same for candidates that aren't factors of n . Compared to that, p*p is only calculated once per candidate, but then for every candidate. The former is clearly preferable to the latter. In fact, thanks to lazy evaluation, the above code (test r==0 before p sr) evaluates intsqrt q at most once per prime candidate and thus combines both advantages. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: How to make Prelude.read: no parse more verbose ...
Ketil Malde [EMAIL PROTECTED] wrote: Georg Sauthoff [EMAIL PROTECTED] writes: Well, how do I compile a Haskell program in such a way, that I get a useful error message from read? I mean, like the filename/linenumber of the calling expression for starters. It's dirty, it's mean, but you can use CPP. (On one line, and with ghc -cpp): [..] Thanks! Indeed, it looks mean, but it helps, because I am currently using ghc 6.8 ... Best regards Georg Sauthoff -- Fortune : 'Real programmers don't comment their code. It was hard to write, it should be hard to understand.' ;) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: MonadFix
apfelmus apfelmus at quantentunnel.de writes: Huh? p intsqrt n is evaluated just as often as p*p n , with changing n . Why would that be less expensive? Btw, the code above test for r==0 first, which means that the following p*p n is tested exactly once for every prime candidate p . No. One point in the introduction of DivIter is, that intsqrt dividend is stored there and only recomputed, when a new factor is found. And concerning my cycled lists of summands as [2,4] or [2,4,2,4,2,4,2,6,2,6]: There simply is no function easily yielding primes for your list primes'. If we use the sieve of Eratosthenes, we must have the whole list of found primes up to a certain point in memory for proceeding beyond that certain point. We cannot gain anything by lazy evaluation. Not with the sieve of Eratosthenes - and there is no other reliable mechanism. What is more - if we have a list of primes, possibly up to 1,000,000 - what shall we do for efficiently yielding divisors beyond 1,000,000 ? We would have to fall back to x - x+2. Thus an easily computable function stepping through all primes can only be a function, which yields primes plus some more odd numbers. This is, what i tried. Alternating addition of 2 and 4 to the current divisor can be continued beyond any bound. And i am not forced to use any of the longer list of summands - indeed, which of these lists to choose should be adapted to the size of the number to decompose. Concerning the State monad: Yes, i was wrong here completely. Ryan Ingram gave detailed instructions why. And Albert Y.C. Lai pointed out, that normal recursion for division works tail recursive too. It didn't on my computer - perhaps i misconfigured ghci (where i tried it). Let us close discussion of this point. Cheers, Joost ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] nice simple problem for someone struggling....
ReallyI'm sure I tried that...(as it seemed obvious) ... and it failedbut I'll have another go -Original Message- From: Jules Bean [mailto:[EMAIL PROTECTED] Sent: 21 December 2007 15:33 To: Nicholls, Mark Cc: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] nice simple problem for someone struggling Nicholls, Mark wrote: *instance* ShapeInterface SquareType *where* area (SquareConstructor sideLength) = sideLength * sideLength *data* SquareType a = Num a = SquareConstructor a Now you have changed your type from SquareType to SquareType a, you need to change the instance to: instance ShapeInterface (SquareType a) where... Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] nice simple problem for someone struggling....
Now I have module Main where data SquareType numberType = Num numberType = SquareConstructor numberType data RectangleType = RectangleConstructor Int Int class ShapeInterface shape where area :: shape-Int data ShapeType = forall a. ShapeInterface a = ShapeType a instance ShapeInterface (SquareType numberType) where area (SquareConstructor sideLength) = sideLength * sideLength main = do putStrLn (show (area (SquareConstructor 4))) name - getLine putStrLn but get the errors In the expression: sideLength * sideLength In the definition of `area': area (SquareConstructor sideLength) = sideLength * sideLength In the definition for method `area' And Couldn't match expected type `Int' against inferred type `numberType' `numberType' is a rigid type variable bound by But to be fairI almost understand the errorswhich is not bad for me.surely class ShapeInterface shape where area :: shape-Int now looks dubiousI want it to be something like class ShapeInterface shape where area :: Num numberType = shape-Int ? but my instance declaration still complains with the errors above and I now get an error in the class declaration `numberType1' is a rigid type variable bound by It's slightly doing my head inand reminds me of trying to learn C++ oncenot a pleasant experiencethough I did eventually succeedto a degree. -Original Message- From: Jules Bean [mailto:[EMAIL PROTECTED] Sent: 21 December 2007 15:33 To: Nicholls, Mark Cc: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] nice simple problem for someone struggling Nicholls, Mark wrote: *instance* ShapeInterface SquareType *where* area (SquareConstructor sideLength) = sideLength * sideLength *data* SquareType a = Num a = SquareConstructor a Now you have changed your type from SquareType to SquareType a, you need to change the instance to: instance ShapeInterface (SquareType a) where... Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] nice simple problem for someone struggling....
Oh You are correct... I thought from Num numberType = SquareConstructor numberType We could deduce that (in English rather than get Haskell and FOL confusion) all values of SquareConstructor athe type of a would have be be in class Num?.. is this not correct?if notwhy not? From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of David Menendez Sent: 21 December 2007 17:05 To: Nicholls, Mark Cc: Jules Bean; haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] nice simple problem for someone struggling On Dec 21, 2007 11:50 AM, Nicholls, Mark [EMAIL PROTECTED] wrote: Now I have module Main where data SquareType numberType = Num numberType = SquareConstructor numberType This is a valid declaration, but I don't think it does what you want it to. The constraint on numberType applies only to the data constructor. That is, given an unknown value of type SquareType a for some a, we do not have enough information to infer Num a. For your code, you want something like: instance (Num a) = ShapeInterface (SquareType a) where area (SquareConstructor side) = side * side -- Dave Menendez [EMAIL PROTECTED] http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing cellular automata the beauty of unlifted types
On Dec 20, 2007 7:42 PM, Sterling Clover [EMAIL PROTECTED] wrote: I'm curious how much of the unboxing helped performance and how much didn't. In my experience playing with this stuff, GHC's strictness analyzer has consistently been really excellent, given the right hints. Unboxed tuples are generally a win, but GHC was often smarter at unboxing ints than I was. It really did help. I started with an implementation that used Ints, and this sped the program up by at least 2x. I think that's because of the bit-manipulation I'm doing. For example, Data.Bits defines the bitwise and operation on Ints as: (I# x#) .. (I# y#) = I# (word2Int# (int2Word# x# `and#` int2Word# y#)) Which you can see has 3 conversions in it. The I# deconstruction/construction is also suspicious to me, but I don't know if there are performance costs there or not. Regardless, using Word# directly lets me write (assuming w1# and w2# are already words): w1# `and#` w2# Maybe better rewrite rules in the Data.Bits library would eliminate unnecessary conversions and this wouldn't be necessary/ Also, higher-order functions can be used fine, assuming they're not awful recursive, as long as you set GHC's unfolding threshold high enough. You can also manually force their inlining, to really get control. I found there tended to be a sweet I didn't know about unfolding, and I'll have to try that sometime. I found that inlining seemed to have negative affects as often as it did positive. I spent most of my time so far coming up with different algorithms - now that I've got a decent one, I'll have to play with inlining. spot for any given program, where much higher or lower would degrade performance. As far as removing the word2int# and soforth, you could probably just use words throughout? I try to. I just couldn't figure out how to write a Word# value literally. For example, eqWord# compares Word# values. But this gives a type error: 1# `eqWord#` 1# I have to write int2word# 1# `eqWord#` int2word# 1# Also, as we discovered the other week, you may want to be careful with bang patterns, as forcing strictness on already evaluated values takes some time. Although, SPJ did point out that this was significantly improved in the new GHC. Good point, thanks. Justin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] FFIpointer data types question
Hi, If I am calling a ANSI function that requires a pointer to a C struct, which FFI pointer type should use? Kind regards, Vasya ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nice simple problem for someone struggling....
On Dec 21, 2007 11:50 AM, Nicholls, Mark [EMAIL PROTECTED] wrote: Now I have module Main where data SquareType numberType = Num numberType = SquareConstructor numberType This is a valid declaration, but I don't think it does what you want it to. The constraint on numberType applies only to the data constructor. That is, given an unknown value of type SquareType a for some a, we do not have enough information to infer Num a. For your code, you want something like: instance (Num a) = ShapeInterface (SquareType a) where area (SquareConstructor side) = side * side -- Dave Menendez [EMAIL PROTECTED] http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Why does this blow the stack?
Given this function: dropTest n = head . drop n $ [1..] I get a stack overflow when n is greater than ~ 550,000 . Is that inevitable behavior for large n? Is there a better way to do it? Justin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does this blow the stack?
On Fri, 2007-12-21 at 09:13 -0800, Justin Bailey wrote: Given this function: dropTest n = head . drop n $ [1..] I get a stack overflow when n is greater than ~ 550,000 . Is that inevitable behavior for large n? Is there a better way to do it? A similar example is discussed on http://www.haskell.org/haskellwiki/Stack_overflow at the bottom. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nice simple problem for someone struggling....
class ShapeInterface shape where area :: shape-Int now looks dubiousI want it to be something like class ShapeInterface shape where area :: Num numberType = shape-Int ? Rather, I think you probably want class ShapeInterface shape where area :: Num numberType = shape - numberType -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does this blow the stack?
On Dec 21, 2007 9:48 AM, Brad Larsen [EMAIL PROTECTED] wrote: I'm curious as well. My first thought was to try the (!!) operator. Typing Prelude [1..] !! 55 overflows the stack on my computer, as does dropTest 55. I think its [1..] which is building up the unevaluated thunk. Using this definition of dropTest does not blow the stack: dropTest n = head . drop n $ repeat 1 Justin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does this blow the stack?
On Dec 21, 2007 9:51 AM, Justin Bailey [EMAIL PROTECTED] wrote: I think its [1..] which is building up the unevaluated thunk. Using this definition of dropTest does not blow the stack: It also works if you do [(1::Int) ..] !! n, but not with [(1::Integer) ..] !! n Sounds like GHC is being smart about strictness for Ints, but doesn't know that Integer is equally strict. If that's right, it's a bug in GHC. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] nice simple problem for someone struggling....
Yes sorrybut this still fails with `numberType1' is a rigid type variable bound by From: Brent Yorgey [mailto:[EMAIL PROTECTED] Sent: 21 December 2007 17:29 To: Nicholls, Mark Cc: Jules Bean; haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] nice simple problem for someone struggling class ShapeInterface shape where area :: shape-Int now looks dubiousI want it to be something like class ShapeInterface shape where area :: Num numberType = shape-Int ? Rather, I think you probably want class ShapeInterface shape where area :: Num numberType = shape - numberType -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does this blow the stack?
Justin Bailey wrote: Given this function: dropTest n = head . drop n $ [1..] I get a stack overflow when n is greater than ~ 550,000 . Is that inevitable behavior for large n? Is there a better way to do it? Just for fun, throw in dropTest :: Int - Int and experiment again! :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] nice simple problem for someone struggling....
Let me resend the code...as it stands module Main where data SquareType numberType = Num numberType = SquareConstructor numberType class ShapeInterface shape where area :: Num numberType = shape-numberType data ShapeType = forall a. ShapeInterface a = ShapeType a instance (Num a) = ShapeInterface (SquareType a) where area (SquareConstructor side) = side * side and the errors are for the instance declaration... [1 of 1] Compiling Main ( Main.hs, C:\Documents and Settings\nichom\Haskell\Shapes2\out/Main.o ) Main.hs:71:36: Couldn't match expected type `numberType' against inferred type `a' `numberType' is a rigid type variable bound by the type signature for `area' at Main.hs:38:15 `a' is a rigid type variable bound by the instance declaration at Main.hs:70:14 In the expression: side * side In the definition of `area': area (SquareConstructor side) = side * side I'm becoming lost in errors I don't comprehend What bamboozles me is it seemed such a minor enhancement. From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of David Menendez Sent: 21 December 2007 17:05 To: Nicholls, Mark Cc: Jules Bean; haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] nice simple problem for someone struggling On Dec 21, 2007 11:50 AM, Nicholls, Mark [EMAIL PROTECTED] wrote: Now I have module Main where data SquareType numberType = Num numberType = SquareConstructor numberType This is a valid declaration, but I don't think it does what you want it to. The constraint on numberType applies only to the data constructor. That is, given an unknown value of type SquareType a for some a, we do not have enough information to infer Num a. For your code, you want something like: instance (Num a) = ShapeInterface (SquareType a) where area (SquareConstructor side) = side * side -- Dave Menendez [EMAIL PROTECTED] http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does this blow the stack?
On Fri, 21 Dec 2007 12:13:04 -0500, Justin Bailey [EMAIL PROTECTED] wrote: Given this function: dropTest n = head . drop n $ [1..] I get a stack overflow when n is greater than ~ 550,000 . Is that inevitable behavior for large n? Is there a better way to do it? Justin I'm curious as well. My first thought was to try the (!!) operator. Typing Prelude [1..] !! 55 overflows the stack on my computer, as does dropTest 55. The code for (!!) is apparently as follows: xs !! n | n 0 = error Prelude.!!: negative index [] !! _ = error Prelude.!!: index too large (x:_) !! 0 = x (_:xs) !! n = xs !! (n-1) Isn't this tail recursive? What is eating up the stack? Brad Larsen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does this blow the stack?
derek.a.elkins:
On Fri, 2007-12-21 at 09:56 -0800, David Benbennick wrote:
On Dec 21, 2007 9:51 AM, Justin Bailey [EMAIL PROTECTED] wrote:
I think its [1..] which is building up the unevaluated thunk. Using
this definition of dropTest does not blow the stack:
It also works if you do [(1::Int) ..] !! n, but not with [(1::Integer) ..]
!! n
Sounds like GHC is being smart about strictness for Ints, but doesn't
know that Integer is equally strict. If that's right, it's a bug in
GHC.
It is a bug in GHC. From
http://darcs.haskell.org/packages/base/GHC/Enum.lhs
enumFrom (I# x) = eftInt x maxInt#
where I# maxInt# = maxInt
-- Blarg: technically I guess enumFrom isn't strict!
...
eftInt x y | x # y= []
| otherwise = go x
where
go x = I# x : if x ==# y then [] else go (x +# 1#)
As usual, this is an issue with the irregular numeric-operation
strictness applied to Integer.
Consider this Integer enumFrom:
main = print x
where x = head (drop 100 (enumFrom' 1))
enumFrom' :: Integer - [Integer]
enumFrom' x = enumDeltaInteger x 1
enumDeltaInteger :: Integer - Integer - [Integer]
enumDeltaInteger x d = x `seq` x : enumDeltaInteger (x+d) d
Is fine. The Int instance is already strict like this.
I'll file a patch. I hate these slightly too lazy issues
with Integer, that aren't present with Int.
The atomic strictness of Integer is only irregularly
applied through the base libraries. For example,
in Data.List, this was considered acceptable:
maximum :: (Ord a) = [a] - a
maximum [] = errorEmptyList maximum
maximum xs = foldl1 max xs
{-# RULES
maximumInt maximum = (strictMaximum :: [Int] - Int);
maximumInteger maximum = (strictMaximum :: [Integer] - Integer)
#-}
Really, if we let Int be strict on (+) and (*)-style operations,
and Integer sometimes strict on those, we should just declare
that these atomic numeric types (and Word, Word8,..)
should be strict on (+) and so on.
-- Don
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does this blow the stack?
On Fri, 2007-12-21 at 09:56 -0800, David Benbennick wrote: On Dec 21, 2007 9:51 AM, Justin Bailey [EMAIL PROTECTED] wrote: I think its [1..] which is building up the unevaluated thunk. Using this definition of dropTest does not blow the stack: It also works if you do [(1::Int) ..] !! n, but not with [(1::Integer) ..] !! n Sounds like GHC is being smart about strictness for Ints, but doesn't know that Integer is equally strict. If that's right, it's a bug in GHC. It is a bug in GHC. From http://darcs.haskell.org/packages/base/GHC/Enum.lhs enumFrom (I# x) = eftInt x maxInt# where I# maxInt# = maxInt -- Blarg: technically I guess enumFrom isn't strict! ... eftInt x y | x # y= [] | otherwise = go x where go x = I# x : if x ==# y then [] else go (x +# 1#) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nice simple problem for someone struggling....
module Main where data SquareType numberType = Num numberType = SquareConstructor numberType class ShapeInterface shape where area :: Num numberType = shape-numberType data ShapeType = forall a. ShapeInterface a = ShapeType a instance (Num a) = ShapeInterface (SquareType a) where area (SquareConstructor side) = side * side Awesome! That's the first e-mail I see that looks good in HTML!___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nice simple problem for someone struggling....
On Dec 21, 2007 12:08 PM, Nicholls, Mark [EMAIL PROTECTED] wrote: I thought from Num numberType = SquareConstructor numberType We could deduce that (in English rather than get Haskell and FOL confusion) all values of SquareConstructor a….the type of a would have be be in class Num?.. is this not correct?if not….why not? That's a reasonable thing to assume. It just happens that Haskell doesn't work that way. There's an asymmetry between constructing and pattern-matching, and it's one that many people have complained about. Personally, I never use class contexts in data declarations, simply because it's too easy to get confused about what they do and do not guarantee. -- Dave Menendez [EMAIL PROTECTED] http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nice simple problem for someone struggling....
On Dec 21, 2007 12:47 PM, Nicholls, Mark [EMAIL PROTECTED] wrote: Let me resend the code…as it stands…. *module* Main *where* *data* SquareType numberType = Num numberType = SquareConstructor numberType *class* ShapeInterface shape *where* area :: Num numberType = shape*-*numberType *data* ShapeType = forall a. ShapeInterface a = ShapeType a *instance* (Num a) = ShapeInterface (SquareType a) *where* area (SquareConstructor side) = side * side Part of the problem is that GHC's error messages have to account for a lot of complex typing extensions you aren't using, so they aren't clear. I'll try to explain what's going wrong. If you look at the function, area (SquareConstructor side) = side * side in isolation (that is, not as part of the class instance), it has the type forall a. Num a = SquareConstructor a - a. The function in the class declaration has type forall a b. (ShapeInterface a, Num b) = a - b. The problem is that a and b are independent variables, but the instance declaration for SquareType a requires them to be related. I'm not sure which way you were trying to parameterize things, but here are some possibilities: (1) If every shape type is parameteric, then you can make ShapeInterface a class of type constructors. class ShapeInterface shape where area :: Num a = shape a - a instance ShapeInterface SquareType where area (SquareConstructor side) = side * side (2) If only some shape types are parametric, you can use a multi-parameter type class to express a relationship between the shape type and the area type: class ShapeInterface shape area where area :: shape - area instance (Num a) = ShapeInterface (SquareType a) a where area (SquareConstructor side) = side * side (3) If you only need to be parameteric over some subset of numeric types, you can use conversion functions: class ShapeIterface shape where area :: shape - Rational class (Real a) = ShapeInterface (SquareType a) where area (SquareConstructor side) = toRational (side * side) (Equivalently, you can replace Rational and Real with Integer and Integral.) It may be that none of these are what you want. There are other, more complex possibilities, but I expect they're overkill. -- Dave Menendez [EMAIL PROTECTED] http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing cellular automata the beauty of unlifted types
On Dec 21, 2007 3:00 PM, Justin Bailey [EMAIL PROTECTED] wrote:
It really did help. I started with an implementation that used Ints,
and this sped the program up by at least 2x. I think that's because of
the bit-manipulation I'm doing. For example, Data.Bits defines the
bitwise and operation on Ints as:
(I# x#) .. (I# y#) = I# (word2Int# (int2Word# x# `and#` int2Word# y#))
Which you can see has 3 conversions in it. The I#
deconstruction/construction is also suspicious to me, but I don't know
if there are performance costs there or not. Regardless, using Word#
directly lets me write (assuming w1# and w2# are already words):
w1# `and#` w2#
Maybe better rewrite rules in the Data.Bits library would eliminate
unnecessary conversions and this wouldn't be necessary
Wouldn't it be sufficient to use Data.Word and rely on GHC unboxing
capabilities? Compiling
import Data.Bits
import Data.Word
main = do
a - getLine
b - getLine
print (read a .. read b :: Word)
with GHC 6.6.1 gives me
(case GHC.Read.read @ GHC.Word.Word GHC.Word.$f40 a_afE
of wild1_a1tT { GHC.Word.W# x#_a1tV -
case GHC.Read.read @ GHC.Word.Word GHC.Word.$f40 a87_a1ub
of wild11_a1tW { GHC.Word.W# y#_a1tY -
GHC.Word.$w$dmshow1 (GHC.Prim.and# x#_a1tV y#_a1tY)
}
})
which of course does the right thing.
Cheers,
--
Felipe.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] functional maps
A while back I was playing with Data.Map was getting irritated about lookups that fail having the type of values, but wrapped in an extra monad. I decided to work around this by putting a default in the data type itself, so we have a functional map data FMap k a = FMap (k - a) (Map k a) This has been really convenient - it's a monad, and failed lookups have the same type as successful ones. lookup :: (Ord k) = k - FMap k a - a lookup k (FMap f m)= Map.findWithDefault (f k) k m This also makes it much nicer to build a function that tabulates a list of pairs (nicer than I've found using Data.Map, anyway): fromPairs :: (Ord k) = [(k,a)] - FMap k [a] fromPairs = foldl' (flip . uncurry $ insertWith (:)) $ return [] insertWith :: (Ord k) = (a - b - b) - k - a - FMap k b - FMap k b insertWith f k x m = case lookup k m of v - insert k (f x v) m Ok, great, but fromPairs is blowing the stack. It does fine for a while, but today I was trying to use it for a few million pairs. It runs for a while, eats a couple gigs of ram, and then I get a stack overflow. Any advice for tracking this down? Thanks! Chad ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nice simple problem for someone struggling....
David Menendez wrote: That's a reasonable thing to assume. It just happens that Haskell doesn't work that way. There's an asymmetry between constructing and pattern-matching, and it's one that many people have complained about. With GADTs turned on (-XGADTS in 6.8, -fglasgow-exts in 6.6) pattern matchings will give rise to class contexts as you would naively expect. Contexts on constructors aren't actualy haskell98, it is a bug that GHC 6.6 accepts them without any extensions being activated. Or that's my understanding, see http://hackage.haskell.org/trac/ghc/ticket/1901 Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does this blow the stack?
Am Freitag, 21. Dezember 2007 schrieb Justin Bailey:
Given this function:
dropTest n = head . drop n $ [1..]
I get a stack overflow when n is greater than ~ 550,000 . Is that
inevitable behavior for large n? Is there a better way to do it?
Justin
[1..] equals [1, (1)+1, (1+1)+1, (1+1+1)+1, (1+1+1+1)+1, ...] where the
brackets are a reference to the previous entry in the list.
so, if you want to reach the nth element in [1..], then the garbage collector
automagically collects the unused list entries... but there are no unused.
[1..]!!10 = ((1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1
now, that one long formula needs to be completely build in the stack prior to
evaluation.
to prevent this, each value has to be evaluated before stepping deeper into the
list. i.e. like with this bang pattern:
let ((!x):xs)!!!i = case i of {0-x;_-xs!!!pred i} in [1..]!!!10
or simply like this trick:
[1..maxBound]!!10
this causes every single entry to be checked against the list-end-condition,
just before the calculation of the next list entry.
- marc
signature.asc
Description: This is a digitally signed message part.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: functional maps
Chad Scherrer chad.scherrer at gmail.com writes: A while back I was playing with Data.Map was getting irritated about lookups that fail having the type of values, but wrapped in an extra monad. I decided to work around this by putting a default in the data type itself, so we have a functional map data FMap k a = FMap (k - a) (Map k a) ... Sorry to respond to my own message, but I think I might have figured it out. This should be strict in the Map parameter, so this works better: data FMap k a = FMap (k - a) !(Map k a) It still takes lots of memory for what I'm trying to do, but that's another problem. At least the stack seems happy. Chad ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does this blow the stack?
coeus:
Am Freitag, 21. Dezember 2007 schrieb Justin Bailey:
Given this function:
dropTest n = head . drop n $ [1..]
I get a stack overflow when n is greater than ~ 550,000 . Is that
inevitable behavior for large n? Is there a better way to do it?
Justin
[1..] equals [1, (1)+1, (1+1)+1, (1+1+1)+1, (1+1+1+1)+1, ...] where the
brackets are a reference to the previous entry in the list.
so, if you want to reach the nth element in [1..], then the garbage collector
automagically collects the unused list entries... but there are no unused.
[1..]!!10 = ((1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1
now, that one long formula needs to be completely build in the stack prior to
evaluation.
to prevent this, each value has to be evaluated before stepping deeper into
the list. i.e. like with this bang pattern:
let ((!x):xs)!!!i = case i of {0-x;_-xs!!!pred i} in [1..]!!!10
or simply like this trick:
[1..maxBound]!!10
this causes every single entry to be checked against the list-end-condition,
just before the calculation of the next list entry.
There's no good reason for the accumulator for Integer to be lazy,
especially when you see that adding an upper bound (enumFromTo) or
using Int uses a strict accumulator.
I've filled a bug report and fix for this.
http://hackage.haskell.org/trac/ghc/ticket/1997
there's an ad hoc sprinkling of strict and lazy Num ops for Integer
through the base library, while Int is fairly consistently strict.
-- Don
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: ANNOUNCE: GHC version 6.8.2
(Moving to the cafe) On a related topic, I've been trying to build 6.8.2 on Leopard lately. I've been running up against the infamous OS X readline issues. I know some builders here have hacked past it, but I'm looking for a good workaround... ideally one that works without changes outside the GHC build area (besides installing a real readline). Here's what I noticed before I started drowning in the build platform. (I'm no gnu-configure expert nor GHC insider.) I can get gnu-readline installed from Macports, no problem. The top-level configure in GHC doesn't respond to my various attempts: o using --with-readline-libraries and --with-readline-includes (Although it looks like the libraries/readline/configure script might recognize these, I can't get an option to pass through.) o setting LDFLAGS and CPPFLAGS environment variables (with -L/opt/local/lib and -I/opt/local/include resp.) in my shell before running configure o playing with the above settings and others in a mk/build.mk Until Apple fixes their broken-readline issue (maybe when the readline compatibility of libedit improves)... maybe the top-level configure can pass through flags or settings somehow? For those who've built with readline on OS X: have you had to resort to blasting the existing readline library link, or is there a configuration option within the GHC tree that you've gotten to work? Should I be filing a trac bug instead of asking here? Thanks for any help. There's no urgency for me; I'm just trying to get a working environment at home; I'd prefer to be able to bootstrap from the ground up; and I'd like to be able to contribute to testing/debugging on OSX. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Haskell performance
Jon Harrop wrote: On Thursday 20 December 2007 19:02, Don Stewart wrote: Ok, so I should revive nobench then, I suspect. http://www.cse.unsw.edu.au/~dons/nobench/x86_64/results.html that kind of thing? Many of those benchmarks look good. However, I suggest avoiding trivially reducible problems like computing constants (e, pi, primes, fib) true in general, but I know I use computed constants in real code because it's cleaner than using their expanded value, so it's worth checking whether a compiler can (still) do (how much of) that. Isaac ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nice simple problem for someone struggling....
On Dec 21, 2007 2:38 PM, Jules Bean [EMAIL PROTECTED] wrote: David Menendez wrote: That's a reasonable thing to assume. It just happens that Haskell doesn't work that way. There's an asymmetry between constructing and pattern-matching, and it's one that many people have complained about. With GADTs turned on (-XGADTS in 6.8, -fglasgow-exts in 6.6) pattern matchings will give rise to class contexts as you would naively expect. Contexts on constructors aren't actualy haskell98, it is a bug that GHC 6.6 accepts them without any extensions being activated. Or that's my understanding, see http://hackage.haskell.org/trac/ghc/ticket/1901 I think I saw [1] and just mentally substituted [2]. In fact, until just now I didn't know [1] was even possible. (Wasn't there some problem with class contexts in GADTs?) [1] data SquareType a = (Num a) = SquareConstructor a [2] data (Num a) = SquareType a = SquareConstructor a Okay, so pattern-matching in case [1] does guarantee Num a. In that case, the original code didn't work because it was trying to unify Int with an arbitrary instance of Num. -- Dave Menendez [EMAIL PROTECTED] http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does this blow the stack?
dbenbenn: On Dec 21, 2007 12:02 PM, Don Stewart [EMAIL PROTECTED] wrote: There's no good reason for the accumulator for Integer to be lazy, especially when you see that adding an upper bound (enumFromTo) or using Int uses a strict accumulator. I've filled a bug report and fix for this. http://hackage.haskell.org/trac/ghc/ticket/1997 there's an ad hoc sprinkling of strict and lazy Num ops for Integer through the base library, while Int is fairly consistently strict. Thanks for fixing this. But doesn't GHC have strictness analysis? Sure does! Even if there was consistent strictness for Integer in the base library, that wouldn't help for code not in the base library. In other words, I want to be able to define mysum :: (Num a) = [a] - a mysum = foldl (+) 0 in my own programs, and have GHC automatically make it strict if a happens to be Int or Integer. Is there any chance of GHC getting that ability? Thankfully, GHC does that already :) mysum :: (Num a) = [a] - a mysum = foldl (+) 0 main = print (mysum [1..1000]) In ghc 6.6, $ time ./A +RTS -M20M Heap exhausted; Current maximum heap size is 19996672 bytes (19 Mb); use `+RTS -Msize' to increase it. and in GHC 6.8, ghc can see through to the strictness of (+) $ time ./A +RTS -M20M 500500 ./A +RTS -M20M 0.95s user 0.00s system 99% cpu 0.959 total The problem here was an explicit recusive loop though, with just not enough for the strictness analyser to get going. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing cellular automata the beauty of unlifted types
Justin Bailey wrote: On Dec 20, 2007 7:42 PM, Sterling Clover [EMAIL PROTECTED] wrote: I'm curious how much of the unboxing helped performance and how much didn't. In my experience playing with this stuff, GHC's strictness analyzer has consistently been really excellent, given the right hints. Unboxed tuples are generally a win, but GHC was often smarter at unboxing ints than I was. It really did help. I started with an implementation that used Ints, and this sped the program up by at least 2x. I think that's because of the bit-manipulation I'm doing. For example, Data.Bits defines the bitwise and operation on Ints as: (I# x#) .. (I# y#) = I# (word2Int# (int2Word# x# `and#` int2Word# y#)) Which you can see has 3 conversions in it. I believe you're barking up the wrong tree here. Consider | module Q (f, g) where | | import GHC.Base | | f :: Word# - Word# - Word# | f a b = a `and#` b | | g :: Int# - Int# - Int# | g a b = word2Int# (int2Word# a `and#` int2Word# b) If you look at the generated machine code, you'll find that f and g are identical functions. The sole purpose of the int2Word# and word2Int# operations is to satisfy the type checker. (This is even true at the core level. The core language is typed, so you still need to do the conversions there. No code is generated for them though.) The I# deconstruction/construction is also suspicious to me, but I don't know if there are performance costs there or not. Regardless, using Word# directly lets me write (assuming w1# and w2# are already words): w1# `and#` w2# The I# deconstruction has a cost, but with proper strictness annotations ghc should optimize those away - check the intermediate Core to see whether it actually does. In fact most of the speedup you got seems to come from the use of uncheckedShiftL# and uncheckedShiftRL# - just using shiftL, shiftR :: Int - Int - Int I# a `shiftR` I# b = I# (word2Int# (int2Word# a `uncheckedShiftRL#` b)) I# a `shiftL` I# b = I# (word2Int# (int2Word# a `uncheckedShiftL#` b)) speeds up the stepWithUArray code by a factor of 2 here, starting with the first program at http://hpaste.org/4151. The normal shiftL and shiftR implementations include bounds checks to get the results for shifts that are bigger than the word size correct. (For example 1 `shiftL` 65 = 0, while 1 `uncheckedShiftL#` 65 = 2 (probably. it depends on your architecture)). Eliminating those checks results in a major speedup. Apparently those bounds checks aren't eliminated even if the shifting width is constant. I wonder why, there's clearly some room for optimization here. (I used ghc 6.8.1 on an Athlon XP. I used ghc -O2, no fancy options.) enjoy, Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does this blow the stack?
On Dec 21, 2007 12:02 PM, Don Stewart [EMAIL PROTECTED] wrote: There's no good reason for the accumulator for Integer to be lazy, especially when you see that adding an upper bound (enumFromTo) or using Int uses a strict accumulator. I've filled a bug report and fix for this. http://hackage.haskell.org/trac/ghc/ticket/1997 there's an ad hoc sprinkling of strict and lazy Num ops for Integer through the base library, while Int is fairly consistently strict. Thanks for fixing this. But doesn't GHC have strictness analysis? Even if there was consistent strictness for Integer in the base library, that wouldn't help for code not in the base library. In other words, I want to be able to define mysum :: (Num a) = [a] - a mysum = foldl (+) 0 in my own programs, and have GHC automatically make it strict if a happens to be Int or Integer. Is there any chance of GHC getting that ability? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does this blow the stack?
On Dec 21, 2007 2:30 PM, Don Stewart [EMAIL PROTECTED] wrote: dbenbenn: Thanks for fixing this. But doesn't GHC have strictness analysis? Sure does! The problem here was an explicit recusive loop though, with just not enough for the strictness analyser to get going. The explicit loop you're talking about is: enumDeltaInteger :: Integer - Integer - [Integer] enumDeltaInteger x d = x : enumDeltaInteger (x+d) d That code isn't very complicated, and I would hope to be able to write code like that in my own programs without having to worry about strictness. Given that the compiler even has an explicit signature, why can't it transform that code to enumDeltaInteger x d = let s = x + d in x : (seq s $ enumDeltaInteger s d) since it knows that (Integer+Integer) is strict? Of course, improving the strictness analysis is harder, but it pays off more, too. ___ 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] Optimizing cellular automata the beauty of unlifted types
On Dec 21, 2007 2:55 PM, Bertram Felgenhauer [EMAIL PROTECTED] wrote: If you look at the generated machine code, you'll find that f and g are identical functions. The sole purpose of the int2Word# and word2Int# operations is to satisfy the type checker. (This is even true at the core level. The core language is typed, so you still need to do the conversions there. No code is generated for them though.) Good to know. They are scary! The I# deconstruction has a cost, but with proper strictness annotations ghc should optimize those away - check the intermediate Core to see whether it actually does. If I see things like GHC.Prim.Intzh, is that a clue its the unlifted type? In fact most of the speedup you got seems to come from the use of uncheckedShiftL# and uncheckedShiftRL# - just using shiftL, shiftR :: Int - Int - Int I# a `shiftR` I# b = I# (word2Int# (int2Word# a `uncheckedShiftRL#` b)) I# a `shiftL` I# b = I# (word2Int# (int2Word# a `uncheckedShiftL#` b)) speeds up the stepWithUArray code by a factor of 2 here, starting with the first program at http://hpaste.org/4151. That is great. I tried your speedup and you are right - just redefining those makes the lifted version faster than the unlifted. Too bad there isn't an unsafe version of the shifts available. Justin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] eager/strict eval katas
great advice. I played with this a bit, desugared to haskell 98, and got -- okay for 1..10^6, not ok (stack overflows) if either the fold or g is left lazy. -- Thanks, Dan Weston. avg6 = uncurry (/) . foldl' g (0,0) where g (!sum,!count) next = ( (sum+next),(count+1)) -- same thing, in haskell98 (works without LANGUAGE BangPatterns) -- thanks #haskell.oerjan avg7 = uncurry (/) . foldl' g (0,0) where g (sum,count) next = sum `seq` count `seq` ( (sum+next),(count+1)) t = avg7 testlist testlist = [1..10^6] 2007/12/12, Dan Weston [EMAIL PROTECTED]: Dan Weston wrote: scanl above is not strict in its second argument. The data dependencies cause the strictness. Cf: Prelude head ([1,3] ++ head ((scanl undefined undefined) undefined)) 1 The first claim is of course false, nore would the example show it anyway. scanl is not strict in its third argument (I forgot about the initial value as the second argument): Prelude Data.List let z = [1,4,undefined,8,9] in scanl (\x y - 5) 8 z [8,5,5,5,5,5] It is the data dependence in the first argument of scanl that would make the above strict: Prelude Data.List let z = [1,4,undefined,8,9] in scanl (+) 8 z [8,9,13,*** Exception: Prelude.undefined Also note that it is better not to introduce the / operator in your test, as it fails with large numbers. Multiply both sides by the denominator before the comparison and leave everything as Num a instead of Floating a. You can do the division at the end. Thomas Hartman wrote: Note that 1 + ··· + n = n * (n+1) / 2, so the average of [1..n] is (n+1) / 2 fair enough. But I believe if I restate the problem so that you need to find the average of an arbitrary list, your clever trick doesn't work and we need eager eval or we blow the stack. Not true: Prelude Data.List let f a = (\(a,b,c)-c) . head . dropWhile (\(s,n,_) - s =n*a) . scanl (\(s,n,_) x -(s+x,n+1,x)) (0,0,0) in f (10^5) [1,3..] 21 Also... on second thought, I actually solved a slightly different problem than what I originally said: the problem of detecting when the moving average of an increasing list is greater than 10^6; but my solution doesn't give the index of the list element that bumped the list over the average. However I suspect my code could be tweaked to do that (still playing around with it): Also I actually used a strict scan not a strict fold and... ach, oh well. scanl above is not strict in its second argument. The data dependencies cause the strictness. Cf: Prelude head ([1,3] ++ head ((scanl undefined undefined) undefined)) 1 As you see I wrote a customized version of foldl' that is strict on the tuple for this to work. I don't think this is necessarily faster than what you did (haven't quite grokked your use of unfold), but it does have the nice property of doing everything in one one fold step (or one scan step I guess, but isn't a scan http://thomashartman-learning.googlecode.com/svn/trunk/haskell/lazy-n-strict/average.hs You have Prelude Control.Arrow Data.List let avg5 = uncurry (/) . foldl' (\(s,n) x - (s + x,n + 1)) (0,0) in avg5 [1..1000] *** Exception: stack overflow -- This fails in 100 sec Try this. It is not foldl' that needs to be strict, but the function folded: Prelude Data.List let avg5 = uncurry (/) . foldl' (\(!s,!n) x - (s + x,n + 1)) (0,0) in avg5 [1..1000] You will need -fbang-patterns for this (there are other ways to do this in Haskell 98 though). t. t1 = average_greater_than (10^7) [1..] average_greater_than max xs = find (max) $ averages xs averages = map fst . myscanl' lAccumAvg (0,0) average = fst . myfoldl' lAccumAvg (0,0) lAccumAvg (!avg,!n) r = ( (avg*n/n1) + (r/n1),(n1)) where n1 = n+1 myfoldl' f (!l,!r) [] = (l,r) myfoldl' f (!l,!r) (x:xs) = ( myfoldl' f q xs ) where q = (l,r) `f` x myscanl f z [] = z : [] myscanl f z (x:xs) = z : myscanl f (f z x) xs myscanl' f (!l,!r) [] = (l,r) : [] myscanl' f (!l,!r) (x:xs) = (l,r) : myscanl' f q xs where q = (l,r) `f` x *Felipe Lessa [EMAIL PROTECTED]* 12/12/2007 02:24 PM To Thomas Hartman/ext/[EMAIL PROTECTED] cc haskell-cafe@haskell.org Subject Re: [Haskell-cafe] eager/strict eval katas On Dec 12, 2007 2:31 PM, Thomas Hartman [EMAIL PROTECTED] wrote: exercise 2) find the first integer such that average of [1..n] is [10^6] (solution involves building an accum list of (average,listLength) tuples. again you can't do a naive fold due to stack overflow, but in this case even strict foldl' from data.list isn't strict enough, I had to define my own custom fold to be strict on the tuples.) What is wrong with Prelude snd . head $ dropWhile (( 10^6) . fst) [((n+1) / 2, n) | n - [1..]] 199.0 Note that 1 + ··· + n = n * (n+1) / 2, so the average of [1..n] is
Re: [Haskell-cafe] Why does this blow the stack?
On Fri, Dec 21, 2007 at 03:16:17PM -0800, David Benbennick wrote: On Dec 21, 2007 2:30 PM, Don Stewart [EMAIL PROTECTED] wrote: dbenbenn: Thanks for fixing this. But doesn't GHC have strictness analysis? Sure does! The problem here was an explicit recusive loop though, with just not enough for the strictness analyser to get going. The explicit loop you're talking about is: enumDeltaInteger :: Integer - Integer - [Integer] enumDeltaInteger x d = x : enumDeltaInteger (x+d) d That code isn't very complicated, and I would hope to be able to write code like that in my own programs without having to worry about strictness. Given that the compiler even has an explicit signature, why can't it transform that code to enumDeltaInteger x d = let s = x + d in x : (seq s $ enumDeltaInteger s d) since it knows that (Integer+Integer) is strict? Of course, improving the strictness analysis is harder, but it pays off more, too. Because they simply aren't the same. Try applying your functions to undefined undefined. Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: readline problems building GHC on Mac OS X (was: Re: [Haskell-cafe] Re: ANNOUNCE: GHC version 6.8.2)
On Dec 21, 2007, at 3:40 PM, Thorkil Naur wrote: 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. I should point out that other components on Mac OS X successfully use libedit for readline functionality. While I agree fully with the desire to have full readline functionality in libedit, would it make sense for GHC to offer an option to use Mac OS X's native readline, with concomitant loss of functionality? Some users might prefer giving up some function in return for one less thing to be installed external to GHC. I probably would. Just a thought... Deborah ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: ANNOUNCE: GHC version 6.8.2
I neglected to CC the below email to haskell-cafe; apologies if anyone gets this twice. -- Forwarded message -- From: Judah Jacobson [EMAIL PROTECTED] Date: Dec 21, 2007 2:12 PM Subject: Re: [Haskell-cafe] Re: ANNOUNCE: GHC version 6.8.2 To: John Dorsey [EMAIL PROTECTED] On Dec 21, 2007 12:48 PM, John Dorsey [EMAIL PROTECTED] wrote: On a related topic, I've been trying to build 6.8.2 on Leopard lately. I've been running up against the infamous OS X readline issues. I know some builders here have hacked past it, but I'm looking for a good workaround... ideally one that works without changes outside the GHC build area (besides installing a real readline). Here's what I noticed before I started drowning in the build platform. (I'm no gnu-configure expert nor GHC insider.) I can get gnu-readline installed from Macports, no problem. The top-level configure in GHC doesn't respond to my various attempts: o using --with-readline-libraries and --with-readline-includes (Although it looks like the libraries/readline/configure script might recognize these, I can't get an option to pass through.) Actually, this is supposed to work. When running the top-level ghc configure, you should be able to just say ./configure --with-readline-libraries=/opt/local/lib --with-readline-includes=/opt/local/include and have those arguments automatically passed to the readline configure script. I just checked that this works on my machine (Tiger x86) when building 6.8.2 against MacPorts' readline. If it doesn't work for you, what errors are you getting? Also, a couple of other generic questions: - Are you on x86 or PPC? (The latter is not working right yet with Leopard.) - How are you bootstrapping the build of 6.8.2: are you using a pre-built binary of ghc-6.8.1, or some other way? Best, -Judah ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
