[Haskell-cafe] Re: ANNOUNCE: GHC version 6.8.2

[Judah Jacobson]

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

Re: readline problems building GHC on Mac OS X (was: Re: [Haskell-cafe] Re: ANNOUNCE: GHC version 6.8.2)

[Deborah Goldsmith]

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

Re: [Haskell-cafe] Why does this blow the stack?

[Stefan O'Rear]

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

readline problems building GHC on Mac OS X (was: Re: [Haskell-cafe] Re: ANNOUNCE: GHC version 6.8.2)

[Thorkil Naur]

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 in

Re: [Haskell-cafe] Optimizing cellular automata & the beauty of unlifted types

[Justin Bailey]

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

[Thomas Hartman]

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 

Re: [Haskell-cafe] Why does this blow the stack?

[David Benbennick]

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

Re: [Haskell-cafe] Optimizing cellular automata & the beauty of unlifted types

[Bertram Felgenhauer]

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?

[Don Stewart]

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 -M' 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] Why does this blow the stack?

[David Benbennick]

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] Re: Haskell performance

[Isaac Dupree]

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....

[David Menendez]

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]>

___
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

[John Dorsey]

(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

[Haskell-cafe] Re: functional maps

[Chad Scherrer]

Chad Scherrer  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?

[Don Stewart]

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

Re: [Haskell-cafe] Why does this blow the stack?

[Marc A. Ziegert]

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

Re: [Haskell-cafe] nice simple problem for someone struggling....

[Jules Bean]

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] Optimizing cellular automata & the beauty of unlifted types

[Felipe Lessa]

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

[Chad Scherrer]

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]

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]>

___
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]

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]>

___
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?

[Don Stewart]

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] nice simple problem for someone struggling....

[Miguel Mitrofanov]

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] Why does this blow the stack?

[Derek 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#)

___
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?

[Albert Y. C. Lai]

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] Why does this blow the stack?

[David Benbennick]

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] Why does this blow the stack?

[Justin Bailey]

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?

[Brad Larsen]

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] nice simple problem for someone struggling....

[Nicholls, Mark]

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]>
 

___
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]

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] nice simple problem for someone struggling....

[Brent Yorgey]

>
> "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?

[Derek Elkins]

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

[Haskell-cafe] Why does this blow the stack?

[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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] FFI"pointer" data types question

[Galchin Vasili]

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....

[Nicholls, Mark]

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 a"the 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]>
 

___
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]

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]>

___
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]

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

RE: [Haskell-cafe] nice simple problem for someone struggling....

[Nicholls, Mark]

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....

[Nicholls, Mark]

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

[Haskell-cafe] Re: How to make Prelude.read: no parse more verbose ...

[Georg Sauthoff]

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

[Joost Behrends]

apfelmus  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

[Haskell-cafe] Re: MonadFix

[apfelmus]

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

Re: [Haskell-cafe] nice simple problem for someone struggling....

[Jules Bean]

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] nice simple problem for someone struggling....

[Nicholls, Mark]

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] Re: announcing darcs 2.0.0pre2

[David Roundy]

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

[Joost Behrends]

@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

[Joost Behrends]

@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

Re: [Haskell-cafe] Re: MonadFix

[Daniel Fischer]

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

[Haskell-cafe] Applying a Dynamic function to a container of Dynamics

[Alfonso Acosta]

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] Smart Constructor Puzzle

[Henning Thielemann]

On Thu, 20 Dec 2007, Stefan O'Rear wrote:

> On Thu, Dec 20, 2007 at 11:39:42PM -0500, Ronald Guida wrote:
> > > data PZero   = PZero   deriving (Show)
> > > data PSucc a = PSucc a deriving (Show)
> > >
> > > type P1 = PSucc PZero
> > > type P2 = PSucc P1
> > > type P3 = PSucc P2
> > > -- etc
>
> ...
>
> > Now here's the puzzle.  I want to create a function "vecLength" that
> > accepts a vector and returns its length.  The catch is that I want to
> > calculate the length based on the /type/ of the vector, without
> > looking at the number of elements in the list.
> >
> > So I started by defining a class that allows me to convert a Peano
> > number to an integer.  I couldn't figure out how to define a function
> > that converts the type directly to an integer, so I am using a
> > two-step process.  Given a Peano type /t/, I would use the expression
> > "pToInt (pGetValue :: t)".
> >
> > > class Peano t where
> > > pGetValue :: t
> > > pToInt :: t -> Int
> > >
> > > instance Peano PZero where
> > > pGetValue = PZero
> > > pToInt _ = 0
> > >
> > > instance (Peano t) => Peano (PSucc t) where
> > > pGetValue = PSucc pGetValue
> > > pToInt (PSucc a) = 1 + pToInt a

Why the two methods pGetValue and pToInt? I thought that pGetValue should
have signature pGetValue :: t -> Peano and that pToInt can convert the
result from pGetValue to Int.

> > Finally, I tried to define vecLength, but I am getting an error.
> >
> > > vecLength :: (Peano s) => Vec s t -> Int
> > > vecLength _ = pToInt (pGetValue :: s)
>
> 1. pGetValue is unneccessary, undefined :: s will work just as well.
>This is a fairly standard approach; the precision values in Floating,
>bitSize :: Bits a => a -> Int, and sizeOf :: Storable a => a -> Int
>all work this way.

What about functions of type
   bitSize :: Bits a => (a, Int)

This would also make explicit, that you don't have to provide a value of
type 'a'.

'sizeOf' might still return different size depending on the value, right?
E.g. when converting a sum data type to a (C++) object.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: Dynamic typing of polymorphic functions

[Alfonso Acosta]

Hi Oleg!

Thanks a lot for your answer, you turn out to end up solving every
problem I get stuck in :)

This bit was the essential part of it.

On Dec 20, 2007 11:47 AM,  <[EMAIL PROTECTED]> wrote:

> -- it is important to give the signature to (,) below: we pack the cons
> -- function of the right type!
> cons :: forall a b. (Typeable a, Typeable b) =>
> Signal a -> Signal b -> Signal (a,b)
> cons (Signal sig1) (Signal sig2) =
> Signal (PrimSignal (Cons (toDyn ((,)::a->b->(a,b))) sig1 sig2))
>
> mapSnd :: (Typeable a, Typeable b) => Signal (b, a) -> Signal a
> mapSnd = mapSY snd
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: MonadFix

[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 .



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

Re: [Haskell-cafe] Re: MonadFix

[Ryan Ingram]

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

Re: FFI question -- was: [Haskell-cafe] New slogan for haskell.org

[Gour]

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