Re: [Haskell-cafe] capri cabal-dev virtualenv cab
Hey, Rustom Does anyone give me a little comparison of these? What would all Rustom my requirements be? Not sure... these seem important for me Rustom 1. Need to sandbox not just haskell-projects but ghc (different Rustom compilations/versions) itself 2. Stability of the (sandboxing) Rustom tool 3. Correcting the deficiencies of cabal (eg inability to Rustom uninstall, quarrels between cabal and apt etc) I'll also appreciate users recommandations here. In spite of some decent experience with Haskell and administration, I keep falling regulary into various traps, particulary when in comes to managing cabal with multiple GHCs. Lately, 2 days after a fresh GHC install, a cabal install failed because of version mismatch in a package between system and user database, and I was forced to clear up the whole thing. I'd much prefer to spend my time hacking my haskell software ;) At the moment, my strategy to swap GHC is purely based on the PATH environment, and that works well if you don't forget to set this env before hacking a project. My strategy for cabal is a bit more convoluted, because I had *so many* troubles with multiple databases (AKA system db and user db), I decided that everything would go in the 'system' one, which is actually just in my user-local GHC install, for which my user obviously have required permissions. Things seem to work a bit better that way, I guess because cabal has easier time handling dependencies. So far I avoided the project-local database strategy because my system does not have much computational power, and I'm bored of waiting for ubiquitous packages to compile in all my folders. Arguably, that would be the only safe and simple way to avoid clashes, but I'd appreciate some shared cache to avoid recompiling the same stuff multiple times. Is there some wrappers that can take care of that ? Cheers, -- Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] capri cabal-dev virtualenv cab
nixos.org (eg hack-nix) addresses those issues (but may introduce some more less important ones). You can setup multiple project specific build environments easily. If you're interested contact me on irc.freenode.net or by mail. (nick MarcWeber) I don't know the other solutions so I can't comment on them. Marc Weber ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] cabal install: Could not find module `Text.XML.HXT.Arrow'
Hi, On Mac OSX, ghc-6.12.3, I have successfully installed the 'hxt' package: http://hackage.haskell.org/package/hxt-8.5.2 Registering hxt-9.1.4... Installing library in /Users/user/.cabal/lib/hxt-9.1.4/ghc-6.12.3 Now when I try to install hSimpleDB ( http://hackage.haskell.org/package/hSimpleDB) I get the following error: cabal install hSimpleDB ... Registering HTTP-4000.0.9... Installing library in /Users/user/.cabal/lib/HTTP-4000.0.9/ghc-6.12.3 Registering HTTP-4000.0.9... Configuring hSimpleDB-0.3... Preprocessing library hSimpleDB-0.3... Building hSimpleDB-0.3... src/Network/AWS/Authentication.hs:47:7: Could not find module `Text.XML.HXT.Arrow': Use -v to see a list of the files searched for. cabal: Error: some packages failed to install: hSimpleDB-0.3 failed during the building phase. The exception was: ExitFailure 1 Any ideas how to solve this? Thanks! Dmitri ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cabal install: Could not find module `Text.XML.HXT.Arrow'
On 8 November 2011 21:58, dokondr doko...@gmail.com wrote: Hi, On Mac OSX, ghc-6.12.3, I have successfully installed the 'hxt' package: http://hackage.haskell.org/package/hxt-8.5.2 Registering hxt-9.1.4... Installing library in /Users/user/.cabal/lib/hxt-9.1.4/ghc-6.12.3 Now when I try to install hSimpleDB (http://hackage.haskell.org/package/hSimpleDB) I get the following error: cabal install hSimpleDB ... Registering HTTP-4000.0.9... Installing library in /Users/user/.cabal/lib/HTTP-4000.0.9/ghc-6.12.3 Registering HTTP-4000.0.9... Configuring hSimpleDB-0.3... Preprocessing library hSimpleDB-0.3... Building hSimpleDB-0.3... src/Network/AWS/Authentication.hs:47:7: Could not find module `Text.XML.HXT.Arrow': Use -v to see a list of the files searched for. cabal: Error: some packages failed to install: hSimpleDB-0.3 failed during the building phase. The exception was: ExitFailure 1 Any ideas how to solve this? Looks like it's missing a dep on hxt. cabal unpack hSimpleDB then go into the directory, edit the .cabal file to add the dep, and cabal install in that directory. -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cabal install: Could not find module `Text.XML.HXT.Arrow'
This is because hSimpleDB doesn't specify version ranges on its dependencies, when it should. Since hxt changed its module structure going from 9.0 to 9.1, hSimpleDB doesn't build against 9.0. You can try to build it by adding '--constraint=hxt==9.0.\*' after your cabal-install command. You can also ask the author to add version ranges to the package. Erik On Tue, Nov 8, 2011 at 11:58, dokondr doko...@gmail.com wrote: Hi, On Mac OSX, ghc-6.12.3, I have successfully installed the 'hxt' package: http://hackage.haskell.org/package/hxt-8.5.2 Registering hxt-9.1.4... Installing library in /Users/user/.cabal/lib/hxt-9.1.4/ghc-6.12.3 Now when I try to install hSimpleDB (http://hackage.haskell.org/package/hSimpleDB) I get the following error: cabal install hSimpleDB ... Registering HTTP-4000.0.9... Installing library in /Users/user/.cabal/lib/HTTP-4000.0.9/ghc-6.12.3 Registering HTTP-4000.0.9... Configuring hSimpleDB-0.3... Preprocessing library hSimpleDB-0.3... Building hSimpleDB-0.3... src/Network/AWS/Authentication.hs:47:7: Could not find module `Text.XML.HXT.Arrow': Use -v to see a list of the files searched for. cabal: Error: some packages failed to install: hSimpleDB-0.3 failed during the building phase. The exception was: ExitFailure 1 Any ideas how to solve this? Thanks! Dmitri ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cabal install: Could not find module `Text.XML.HXT.Arrow'
On 8 November 2011 22:10, Erik Hesselink hessel...@gmail.com wrote: This is because hSimpleDB doesn't specify version ranges on its dependencies, when it should. Since hxt changed its module structure going from 9.0 to 9.1, hSimpleDB doesn't build against 9.0. You can try to build it by adding '--constraint=hxt==9.0.\*' after your cabal-install command. You can also ask the author to add version ranges to the package. Is the escape needed if you're using single quotes? -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cabal install: Could not find module `Text.XML.HXT.Arrow'
On Tue, Nov 8, 2011 at 12:16, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: On 8 November 2011 22:10, Erik Hesselink hessel...@gmail.com wrote: This is because hSimpleDB doesn't specify version ranges on its dependencies, when it should. Since hxt changed its module structure going from 9.0 to 9.1, hSimpleDB doesn't build against 9.0. You can try to build it by adding '--constraint=hxt==9.0.\*' after your cabal-install command. You can also ask the author to add version ranges to the package. Is the escape needed if you're using single quotes? I don't know. I always escape *s in shell commands to be sure the shell doesn't expand them, but in most of the cases, it probably works without them. It will likely even work without quotes and without the escape, unless you have files matching the pattern. Erik ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Project Euler Problem 357 in Haskell
Hello all
Being a Haskell enthusiastic , first I tried to solve this problem in
Haskell but it running for almost 10 minutes on my computer but not getting
the answer. A similar C++ program outputs the answer almost instant so
could some one please tell me how to improve this Haskell program.
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad
prime :: Int - UArray Int Bool
prime n = runSTUArray $ do
arr - newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool )
forM_ ( takeWhile ( \x - x*x = n ) [ 2 .. n ] ) $ \i - do
ai - readArray arr i
when ( ai ) $ forM_ [ i^2 , i^2 + i .. n ] $ \j - do
writeArray arr j False
return arr
pList :: UArray Int Bool
pList = prime $ 10 ^ 8
divPrime :: Int - Bool
divPrime n = all ( \d - if mod n d == 0 then pList ! ( d + div n d )
else True ) $ [ 1 .. truncate . sqrt . fromIntegral $ n ]
main = putStrLn . show . sum $ [ if and [ pList ! i , divPrime . pred $ i
] then pred i else 0 | i - [ 2 .. 10 ^ 8 ] ]
C++ program which outputs the answer almost instant.
#includecstdio
#includeiostream
#includevector
#define Lim 10001
using namespace std;
bool prime [Lim];
vectorint v ;
void isPrime ()
{
for( int i = 2 ; i * i = Lim ; i++)
if ( !prime [i]) for ( int j = i * i ; j = Lim ; j += i )
prime [j] = 1 ;
for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] ) v.push_back(
i ) ;
//coutv.size()endl;
//for(int i=0;i10;i++) coutv[i] ;coutendl;
}
int main()
{
isPrime();
int n = v.size();
long long sum = 0;
for(int i = 0 ; i n ; i ++)
{
int k = v[i]-1;
bool f = 0;
for(int i = 1 ; i*i= k ; i++)
if ( k % i == 0 prime[ i + ( k / i ) ] ) {
f=1 ; break ; }
if ( !f ) sum += k;
}
coutsumendl;
}
Regards
Mukesh Tiwari
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cabal install: Could not find module `Text.XML.HXT.Arrow'
Thanks, Alas adding '--constraint=hxt==9.0.\*' after cabal-install command does not help. I get the same error. On Tue, Nov 8, 2011 at 2:10 PM, Erik Hesselink hessel...@gmail.com wrote: This is because hSimpleDB doesn't specify version ranges on its dependencies, when it should. Since hxt changed its module structure going from 9.0 to 9.1, hSimpleDB doesn't build against 9.0. You can try to build it by adding '--constraint=hxt==9.0.\*' after your cabal-install command. You can also ask the author to add version ranges to the package. Erik On Tue, Nov 8, 2011 at 11:58, dokondr doko...@gmail.com wrote: Hi, On Mac OSX, ghc-6.12.3, I have successfully installed the 'hxt' package: http://hackage.haskell.org/package/hxt-8.5.2 Registering hxt-9.1.4... Installing library in /Users/user/.cabal/lib/hxt-9.1.4/ghc-6.12.3 Now when I try to install hSimpleDB (http://hackage.haskell.org/package/hSimpleDB) I get the following error: cabal install hSimpleDB ... Registering HTTP-4000.0.9... Installing library in /Users/user/.cabal/lib/HTTP-4000.0.9/ghc-6.12.3 Registering HTTP-4000.0.9... Configuring hSimpleDB-0.3... Preprocessing library hSimpleDB-0.3... Building hSimpleDB-0.3... src/Network/AWS/Authentication.hs:47:7: Could not find module `Text.XML.HXT.Arrow': Use -v to see a list of the files searched for. cabal: Error: some packages failed to install: hSimpleDB-0.3 failed during the building phase. The exception was: ExitFailure 1 Any ideas how to solve this? Thanks! Dmitri ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Project Euler Problem 357 in Haskell
Could Int be overflowing?
On Tue, Nov 8, 2011 at 7:21 PM, mukesh tiwari
mukeshtiwari.ii...@gmail.com wrote:
Hello all
Being a Haskell enthusiastic , first I tried to solve this problem in
Haskell but it running for almost 10 minutes on my computer but not getting
the answer. A similar C++ program outputs the answer almost instant so could
some one please tell me how to improve this Haskell program.
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad
prime :: Int - UArray Int Bool
prime n = runSTUArray $ do
arr - newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool )
forM_ ( takeWhile ( \x - x*x = n ) [ 2 .. n ] ) $ \i - do
ai - readArray arr i
when ( ai ) $ forM_ [ i^2 , i^2 + i .. n ] $ \j - do
writeArray arr j False
return arr
pList :: UArray Int Bool
pList = prime $ 10 ^ 8
divPrime :: Int - Bool
divPrime n = all ( \d - if mod n d == 0 then pList ! ( d + div n d ) else
True ) $ [ 1 .. truncate . sqrt . fromIntegral $ n ]
main = putStrLn . show . sum $ [ if and [ pList ! i , divPrime . pred $ i ]
then pred i else 0 | i - [ 2 .. 10 ^ 8 ] ]
C++ program which outputs the answer almost instant.
#includecstdio
#includeiostream
#includevector
#define Lim 10001
using namespace std;
bool prime [Lim];
vectorint v ;
void isPrime ()
{
for( int i = 2 ; i * i = Lim ; i++)
if ( !prime [i]) for ( int j = i * i ; j = Lim ; j += i )
prime [j] = 1
;
for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] ) v.push_back(
i ) ;
//coutv.size()endl;
//for(int i=0;i10;i++) coutv[i] ;coutendl;
}
int main()
{
isPrime();
int n = v.size();
long long sum = 0;
for(int i = 0 ; i n ; i ++)
{
int k = v[i]-1;
bool f = 0;
for(int i = 1 ; i*i= k ; i++)
if ( k % i == 0 prime[ i + ( k / i ) ] ) {
f=1 ; break ; }
if ( !f ) sum += k;
}
coutsumendl;
}
Regards
Mukesh Tiwari
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cabal install: Could not find module `Text.XML.HXT.Arrow'
On Tue, Nov 8, 2011 at 2:31 PM, Audun Skaugen audunskau...@gmail.comwrote: Erik Hesselink wrote: On Tue, Nov 8, 2011 at 12:16, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: On 8 November 2011 22:10, Erik Hesselink hessel...@gmail.com wrote: This is because hSimpleDB doesn't specify version ranges on its dependencies, when it should. Since hxt changed its module structure going from 9.0 to 9.1, hSimpleDB doesn't build against 9.0. You can try to build it by adding '--constraint=hxt==9.0.\*' after your cabal-install command. You can also ask the author to add version ranges to the package. Is the escape needed if you're using single quotes? I don't know. I always escape *s in shell commands to be sure the shell doesn't expand them, but in most of the cases, it probably works without them. It will likely even work without quotes and without the escape, unless you have files matching the pattern. The single quote doesn't expand anything, so you don't need to escape the *. Actually, this will result in the backslash also being passed to cabal, so I would be surprised if your command works at all. No matter how you escape *, you get the same error: Preprocessing library hSimpleDB-0.3... Building hSimpleDB-0.3... src/Network/AWS/Authentication.hs:47:7: Could not find module `Text.XML.HXT.Arrow': ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Project Euler Problem 357 in Haskell
I am not sure about Int overflow. There is no case of Int overflow in
prime , pList and divPrime function however lets assuming Int overflow in
main but then still answer should be outputted.
Regards
Mukesh Tiwari
On Tue, Nov 8, 2011 at 5:08 PM, Lyndon Maydwell maydw...@gmail.com wrote:
Could Int be overflowing?
On Tue, Nov 8, 2011 at 7:21 PM, mukesh tiwari
mukeshtiwari.ii...@gmail.com wrote:
Hello all
Being a Haskell enthusiastic , first I tried to solve this problem in
Haskell but it running for almost 10 minutes on my computer but not
getting
the answer. A similar C++ program outputs the answer almost instant so
could
some one please tell me how to improve this Haskell program.
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad
prime :: Int - UArray Int Bool
prime n = runSTUArray $ do
arr - newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool )
forM_ ( takeWhile ( \x - x*x = n ) [ 2 .. n ] ) $ \i - do
ai - readArray arr i
when ( ai ) $ forM_ [ i^2 , i^2 + i .. n ] $ \j - do
writeArray arr j False
return arr
pList :: UArray Int Bool
pList = prime $ 10 ^ 8
divPrime :: Int - Bool
divPrime n = all ( \d - if mod n d == 0 then pList ! ( d + div n d )
else
True ) $ [ 1 .. truncate . sqrt . fromIntegral $ n ]
main = putStrLn . show . sum $ [ if and [ pList ! i , divPrime . pred $
i ]
then pred i else 0 | i - [ 2 .. 10 ^ 8 ] ]
C++ program which outputs the answer almost instant.
#includecstdio
#includeiostream
#includevector
#define Lim 10001
using namespace std;
bool prime [Lim];
vectorint v ;
void isPrime ()
{
for( int i = 2 ; i * i = Lim ; i++)
if ( !prime [i]) for ( int j = i * i ; j = Lim ; j += i
) prime [j] = 1
;
for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] )
v.push_back( i ) ;
//coutv.size()endl;
//for(int i=0;i10;i++) coutv[i] ;coutendl;
}
int main()
{
isPrime();
int n = v.size();
long long sum = 0;
for(int i = 0 ; i n ; i ++)
{
int k = v[i]-1;
bool f = 0;
for(int i = 1 ; i*i= k ; i++)
if ( k % i == 0 prime[ i + ( k / i ) ]
) { f=1 ; break ; }
if ( !f ) sum += k;
}
coutsumendl;
}
Regards
Mukesh Tiwari
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cabal install: Could not find module `Text.XML.HXT.Arrow'
Package Text.XML.HXT.Arrow existed only in 8.5.2 version of hxt: http://hackage.haskell.org/packages/archive/hxt/8.5.2/doc/html/Text-XML-HXT-Arrow.html Yet trying to install with this version produce even more problems: ~cabal --constraint=hxt==8.5.2 install hSimpleDB Resolving dependencies... cabal: cannot configure Crypto-4.2.3. It requires QuickCheck =2.4.0.1 For the dependency on QuickCheck =2.4.0.1 there are these packages: QuickCheck-2.4.0.1, QuickCheck-2.4.1 and QuickCheck-2.4.1.1. However none of them are available. QuickCheck-2.4.0.1 was excluded because tagsoup-0.8 requires QuickCheck ==2.1.* QuickCheck-2.4.1 was excluded because tagsoup-0.8 requires QuickCheck ==2.1.* QuickCheck-2.4.1.1 was excluded because tagsoup-0.8 requires QuickCheck ==2.1.* On Tue, Nov 8, 2011 at 2:43 PM, dokondr doko...@gmail.com wrote: On Tue, Nov 8, 2011 at 2:31 PM, Audun Skaugen audunskau...@gmail.comwrote: Erik Hesselink wrote: On Tue, Nov 8, 2011 at 12:16, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: On 8 November 2011 22:10, Erik Hesselink hessel...@gmail.com wrote: This is because hSimpleDB doesn't specify version ranges on its dependencies, when it should. Since hxt changed its module structure going from 9.0 to 9.1, hSimpleDB doesn't build against 9.0. You can try to build it by adding '--constraint=hxt==9.0.\*' after your cabal-install command. You can also ask the author to add version ranges to the package. Is the escape needed if you're using single quotes? I don't know. I always escape *s in shell commands to be sure the shell doesn't expand them, but in most of the cases, it probably works without them. It will likely even work without quotes and without the escape, unless you have files matching the pattern. The single quote doesn't expand anything, so you don't need to escape the *. Actually, this will result in the backslash also being passed to cabal, so I would be surprised if your command works at all. No matter how you escape *, you get the same error: Preprocessing library hSimpleDB-0.3... Building hSimpleDB-0.3... src/Network/AWS/Authentication.hs:47:7: Could not find module `Text.XML.HXT.Arrow': ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Project Euler Problem 357 in Haskell
May I suggest you try a non-ST solution first (e.g. using Data.IntMap)
first (assuming an auxiliary data-structure is required)?
Also, I'm not sure if the logic in the two versions is the same: I'm
not sure about how you handle the boolean aspect in C++, but you have
a third for-loop there that doesn't seem to correspond to anything in
the Haskell version.
On 8 November 2011 22:50, mukesh tiwari mukeshtiwari.ii...@gmail.com wrote:
I am not sure about Int overflow. There is no case of Int overflow in prime
, pList and divPrime function however lets assuming Int overflow in main but
then still answer should be outputted.
Regards
Mukesh Tiwari
On Tue, Nov 8, 2011 at 5:08 PM, Lyndon Maydwell maydw...@gmail.com wrote:
Could Int be overflowing?
On Tue, Nov 8, 2011 at 7:21 PM, mukesh tiwari
mukeshtiwari.ii...@gmail.com wrote:
Hello all
Being a Haskell enthusiastic , first I tried to solve this problem in
Haskell but it running for almost 10 minutes on my computer but not
getting
the answer. A similar C++ program outputs the answer almost instant so
could
some one please tell me how to improve this Haskell program.
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad
prime :: Int - UArray Int Bool
prime n = runSTUArray $ do
arr - newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool )
forM_ ( takeWhile ( \x - x*x = n ) [ 2 .. n ] ) $ \i - do
ai - readArray arr i
when ( ai ) $ forM_ [ i^2 , i^2 + i .. n ] $ \j - do
writeArray arr j False
return arr
pList :: UArray Int Bool
pList = prime $ 10 ^ 8
divPrime :: Int - Bool
divPrime n = all ( \d - if mod n d == 0 then pList ! ( d + div n d )
else
True ) $ [ 1 .. truncate . sqrt . fromIntegral $ n ]
main = putStrLn . show . sum $ [ if and [ pList ! i , divPrime . pred $
i ]
then pred i else 0 | i - [ 2 .. 10 ^ 8 ] ]
C++ program which outputs the answer almost instant.
#includecstdio
#includeiostream
#includevector
#define Lim 10001
using namespace std;
bool prime [Lim];
vectorint v ;
void isPrime ()
{
for( int i = 2 ; i * i = Lim ; i++)
if ( !prime [i]) for ( int j = i * i ; j = Lim ; j += i
) prime [j] = 1
;
for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] )
v.push_back( i ) ;
//coutv.size()endl;
//for(int i=0;i10;i++) coutv[i] ;coutendl;
}
int main()
{
isPrime();
int n = v.size();
long long sum = 0;
for(int i = 0 ; i n ; i ++)
{
int k = v[i]-1;
bool f = 0;
for(int i = 1 ; i*i= k ; i++)
if ( k % i == 0 prime[ i + ( k / i ) ]
) { f=1 ; break ; }
if ( !f ) sum += k;
}
coutsumendl;
}
Regards
Mukesh Tiwari
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
IvanMiljenovic.wordpress.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Project Euler Problem 357 in Haskell
Logic is same. The idea is generate the primes less than 10^8. Now from
each prime , subtract 1 ( when d is 1 then d + n / d = n + 1 should be
prime ) and check for all the divisor. If all divisor are prime then return
True else False
divPrime n = all ( \d - if mod n d == 0 then pList ! ( d + div n d )
else True ) $ [ 1 .. truncate . sqrt . fromIntegral $ n ]
Corresponding C++ statement
for(int i = 1 ; i*i= k ; i++) if ( k % i == 0 prime[ i + ( k / i )
] ) { f=1 ; break ; }
If al the divPrime returns true then sum this number other wise not. The
only difference is after generating the prime in c++ , I collected all the
primes in vector how ever i don't think it could be issue for not getting
output in Haskell.
On Tue, Nov 8, 2011 at 5:29 PM, Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com wrote:
May I suggest you try a non-ST solution first (e.g. using Data.IntMap)
first (assuming an auxiliary data-structure is required)?
Also, I'm not sure if the logic in the two versions is the same: I'm
not sure about how you handle the boolean aspect in C++, but you have
a third for-loop there that doesn't seem to correspond to anything in
the Haskell version.
Which loop ?
On 8 November 2011 22:50, mukesh tiwari mukeshtiwari.ii...@gmail.com
wrote:
I am not sure about Int overflow. There is no case of Int overflow in
prime
, pList and divPrime function however lets assuming Int overflow in main
but
then still answer should be outputted.
Regards
Mukesh Tiwari
On Tue, Nov 8, 2011 at 5:08 PM, Lyndon Maydwell maydw...@gmail.com
wrote:
Could Int be overflowing?
On Tue, Nov 8, 2011 at 7:21 PM, mukesh tiwari
mukeshtiwari.ii...@gmail.com wrote:
Hello all
Being a Haskell enthusiastic , first I tried to solve this problem in
Haskell but it running for almost 10 minutes on my computer but not
getting
the answer. A similar C++ program outputs the answer almost instant so
could
some one please tell me how to improve this Haskell program.
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad
prime :: Int - UArray Int Bool
prime n = runSTUArray $ do
arr - newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool )
forM_ ( takeWhile ( \x - x*x = n ) [ 2 .. n ] ) $ \i - do
ai - readArray arr i
when ( ai ) $ forM_ [ i^2 , i^2 + i .. n ] $ \j - do
writeArray arr j False
return arr
pList :: UArray Int Bool
pList = prime $ 10 ^ 8
divPrime :: Int - Bool
divPrime n = all ( \d - if mod n d == 0 then pList ! ( d + div n d
)
else
True ) $ [ 1 .. truncate . sqrt . fromIntegral $ n ]
main = putStrLn . show . sum $ [ if and [ pList ! i , divPrime .
pred $
i ]
then pred i else 0 | i - [ 2 .. 10 ^ 8 ] ]
C++ program which outputs the answer almost instant.
#includecstdio
#includeiostream
#includevector
#define Lim 10001
using namespace std;
bool prime [Lim];
vectorint v ;
void isPrime ()
{
for( int i = 2 ; i * i = Lim ; i++)
if ( !prime [i]) for ( int j = i * i ; j = Lim ; j +=
i
) prime [j] = 1
;
for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] )
v.push_back( i ) ;
//coutv.size()endl;
//for(int i=0;i10;i++) coutv[i] ;coutendl;
}
int main()
{
isPrime();
int n = v.size();
long long sum = 0;
for(int i = 0 ; i n ; i ++)
{
int k = v[i]-1;
bool f = 0;
for(int i = 1 ; i*i= k ; i++)
if ( k % i == 0 prime[ i + ( k / i )
]
) { f=1 ; break ; }
if ( !f ) sum += k;
}
coutsumendl;
}
Regards
Mukesh Tiwari
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
IvanMiljenovic.wordpress.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Project Euler Problem 357 in Haskell
On 8 November 2011 23:29, mukesh tiwari mukeshtiwari.ii...@gmail.com wrote: Also, I'm not sure if the logic in the two versions is the same: I'm not sure about how you handle the boolean aspect in C++, but you have a third for-loop there that doesn't seem to correspond to anything in the Haskell version. Which loop ? for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] ) v.push_back( i ) ; -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Project Euler Problem 357 in Haskell
In that loop , I am collecting all the primes in vector how ever I changed
the c++ code and now it resembles to Haskell code. This code still gives
the answer within a second.
#includecstdio
#includeiostream
#includevector
#define Lim 10001
using namespace std;
bool prime [Lim];
vectorint v ;
void isPrime ()
{
for( int i = 2 ; i * i = Lim ; i++)
if ( !prime [i]) for ( int j = i * i ; j = Lim ; j += i ) prime
[j] = 1 ;
//for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] ) v.push_back( i
) ;
//coutv.size()endl;
//for(int i=0;i10;i++) coutv[i] ;coutendl;
}
int main()
{
isPrime();
int n = v.size();
long long sum = 0;
for(int i = 0 ; i Lim ; i ++)
if ( ! prime [i])
{
int k = i-1;
bool f = 0;
for(int i = 1 ; i*i= k ; i++)
if ( k % i == 0 prime[ i + ( k / i ) ] ) { f=1 ; break
; }
if ( !f ) sum += k;
}
coutsumendl;
}
Regards
Mukesh Tiwari
On Tue, Nov 8, 2011 at 6:03 PM, Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com wrote:
On 8 November 2011 23:29, mukesh tiwari mukeshtiwari.ii...@gmail.com
wrote:
Also, I'm not sure if the logic in the two versions is the same: I'm
not sure about how you handle the boolean aspect in C++, but you have
a third for-loop there that doesn't seem to correspond to anything in
the Haskell version.
Which loop ?
for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] ) v.push_back( i ) ;
--
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
IvanMiljenovic.wordpress.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Project Euler Problem 357 in Haskell
If I compile with optimizations:
ghc --make -O3 primes.hs
I get an answer that is off by one from the C++ program in a few seconds.
On Tue, Nov 8, 2011 at 7:46 AM, mukesh tiwari
mukeshtiwari.ii...@gmail.com wrote:
In that loop , I am collecting all the primes in vector how ever I changed
the c++ code and now it resembles to Haskell code. This code still gives
the answer within a second.
#includecstdio
#includeiostream
#includevector
#define Lim 10001
using namespace std;
bool prime [Lim];
vectorint v ;
void isPrime ()
{
for( int i = 2 ; i * i = Lim ; i++)
if ( !prime [i]) for ( int j = i * i ; j = Lim ; j += i ) prime
[j] = 1 ;
//for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] ) v.push_back( i
) ;
//coutv.size()endl;
//for(int i=0;i10;i++) coutv[i] ;coutendl;
}
int main()
{
isPrime();
int n = v.size();
long long sum = 0;
for(int i = 0 ; i Lim ; i ++)
if ( ! prime [i])
{
int k = i-1;
bool f = 0;
for(int i = 1 ; i*i= k ; i++)
if ( k % i == 0 prime[ i + ( k / i ) ] ) { f=1 ; break ;
}
if ( !f ) sum += k;
}
coutsumendl;
}
Regards
Mukesh Tiwari
On Tue, Nov 8, 2011 at 6:03 PM, Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com wrote:
On 8 November 2011 23:29, mukesh tiwari mukeshtiwari.ii...@gmail.com
wrote:
Also, I'm not sure if the logic in the two versions is the same: I'm
not sure about how you handle the boolean aspect in C++, but you have
a third for-loop there that doesn't seem to correspond to anything in
the Haskell version.
Which loop ?
for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] ) v.push_back( i ) ;
--
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
IvanMiljenovic.wordpress.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Project Euler Problem 357 in Haskell
I forgot to add, I'm on 32-bit GHC and the sum will overflow there, so
I changed main:
main = putStrLn . show . sum $ ([ if and [ pList ! i , divPrime .
pred $ i ] then (fromIntegral $ pred i) else 0 | i - [ 2 .. 10 ^ 8 ]
] :: [Integer])
On Tue, Nov 8, 2011 at 8:19 AM, Ryan Yates fryguy...@gmail.com wrote:
If I compile with optimizations:
ghc --make -O3 primes.hs
I get an answer that is off by one from the C++ program in a few seconds.
On Tue, Nov 8, 2011 at 7:46 AM, mukesh tiwari
mukeshtiwari.ii...@gmail.com wrote:
In that loop , I am collecting all the primes in vector how ever I changed
the c++ code and now it resembles to Haskell code. This code still gives
the answer within a second.
#includecstdio
#includeiostream
#includevector
#define Lim 10001
using namespace std;
bool prime [Lim];
vectorint v ;
void isPrime ()
{
for( int i = 2 ; i * i = Lim ; i++)
if ( !prime [i]) for ( int j = i * i ; j = Lim ; j += i ) prime
[j] = 1 ;
//for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] ) v.push_back( i
) ;
//coutv.size()endl;
//for(int i=0;i10;i++) coutv[i] ;coutendl;
}
int main()
{
isPrime();
int n = v.size();
long long sum = 0;
for(int i = 0 ; i Lim ; i ++)
if ( ! prime [i])
{
int k = i-1;
bool f = 0;
for(int i = 1 ; i*i= k ; i++)
if ( k % i == 0 prime[ i + ( k / i ) ] ) { f=1 ; break ;
}
if ( !f ) sum += k;
}
coutsumendl;
}
Regards
Mukesh Tiwari
On Tue, Nov 8, 2011 at 6:03 PM, Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com wrote:
On 8 November 2011 23:29, mukesh tiwari mukeshtiwari.ii...@gmail.com
wrote:
Also, I'm not sure if the logic in the two versions is the same: I'm
not sure about how you handle the boolean aspect in C++, but you have
a third for-loop there that doesn't seem to correspond to anything in
the Haskell version.
Which loop ?
for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] ) v.push_back( i ) ;
--
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
IvanMiljenovic.wordpress.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Project Euler Problem 357 in Haskell
Thank you Ryan . I never compiled my program with -O3 option before and
now i can feel the power of compiler optimisation.
Regards
Mukesh Tiwari
On Tue, Nov 8, 2011 at 6:50 PM, Ryan Yates fryguy...@gmail.com wrote:
I forgot to add, I'm on 32-bit GHC and the sum will overflow there, so
I changed main:
main = putStrLn . show . sum $ ([ if and [ pList ! i , divPrime .
pred $ i ] then (fromIntegral $ pred i) else 0 | i - [ 2 .. 10 ^ 8 ]
] :: [Integer])
On Tue, Nov 8, 2011 at 8:19 AM, Ryan Yates fryguy...@gmail.com wrote:
If I compile with optimizations:
ghc --make -O3 primes.hs
I get an answer that is off by one from the C++ program in a few seconds.
On Tue, Nov 8, 2011 at 7:46 AM, mukesh tiwari
mukeshtiwari.ii...@gmail.com wrote:
In that loop , I am collecting all the primes in vector how ever I
changed
the c++ code and now it resembles to Haskell code. This code still
gives
the answer within a second.
#includecstdio
#includeiostream
#includevector
#define Lim 10001
using namespace std;
bool prime [Lim];
vectorint v ;
void isPrime ()
{
for( int i = 2 ; i * i = Lim ; i++)
if ( !prime [i]) for ( int j = i * i ; j = Lim ; j += i )
prime
[j] = 1 ;
//for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] )
v.push_back( i
) ;
//coutv.size()endl;
//for(int i=0;i10;i++) coutv[i] ;coutendl;
}
int main()
{
isPrime();
int n = v.size();
long long sum = 0;
for(int i = 0 ; i Lim ; i ++)
if ( ! prime [i])
{
int k = i-1;
bool f = 0;
for(int i = 1 ; i*i= k ; i++)
if ( k % i == 0 prime[ i + ( k / i ) ] ) { f=1 ;
break ;
}
if ( !f ) sum += k;
}
coutsumendl;
}
Regards
Mukesh Tiwari
On Tue, Nov 8, 2011 at 6:03 PM, Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com wrote:
On 8 November 2011 23:29, mukesh tiwari mukeshtiwari.ii...@gmail.com
wrote:
Also, I'm not sure if the logic in the two versions is the same: I'm
not sure about how you handle the boolean aspect in C++, but you
have
a third for-loop there that doesn't seem to correspond to anything
in
the Haskell version.
Which loop ?
for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] ) v.push_back( i ) ;
--
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
IvanMiljenovic.wordpress.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Putting constraints on internal type variables in GADTs
Hi all, I was trying to do something very simple with GADTs when I ran into this problem - -- My datatype data T o where Only ∷ o → T o TT ∷ T o1 → (o1 → o2) → T o2 -- Show instance for debugging instance Show o ⇒ Show (T o) where show (Only o) = Only ⊕ (show o) show (TT t1 f) = TT ( ⊕ (show t1) ⊕ ) When I try to compile this I get the following - Could not deduce (Show o1) arising from a use of `show' from the context (Show o) While I understand why I get this error, I have no idea how to fix it! I cannot put a Show constraint on o1 because that variable is not exposed in the type of the expression. I can work around this by changing my data type declaration to include Show constraints but I don't want to restrict my data type to only Showable things just so I could have a Show instance for debugging - Only ∷ Show o ⇒ o → T o TT ∷ (Show o1, Show o2) ⇒ T o1 → (o1 → o2) → T o2 What else can I do to declare a Show instance for my datatype? Thanks, Anupam Jain ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Project Euler Problem 357 in Haskell
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 11/08/2011 02:19 PM, Ryan Yates wrote: If I compile with optimizations: ghc --make -O3 primes.hs I get an answer that is off by one from the C++ program in a few seconds. nice one. Though i wonder. The problem seems to be that without optimization sum is not tail-recursive. Is sum meant to not be tail-recursive? ghci sum [1..] eats up all the memory within seconds while ghci foldl' (+) 0 [1..] does not So Mukesh if you want your program to run without -Ox you should probably define your one sum' import Data.List sum' = foldl' (+) 0 Silvio -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQIcBAEBAgAGBQJOuTSFAAoJEDLsP+zrbatW3W8P/04IPhOqSvAI5Cau+GusInCr CVu932qNVROMb++NHulEtxKQTS7o/WRqrM5OxKclnOi5Rfi/1Da7ozBKfuLtLSo5 W+bJ8AGYTQAGOoIxbsvhAcCBtA35gColc/56cFUbLexZsd4au6SNRxUe+SdhKDIE YWPoDW/NU5xJCrW7VtJ8G2qWhkDTOtFWqhp63yG+f6ZbJQpK+j0Z7KVPQ42qUb02 vPddhukb3iqlK990r9/vAeXiiKM9wLA4YQSAgRurmn5R2R++ftq78TWOS9J0H3IF zspAr19FmEHoHxX3ZiGqyG9thmNwTTz/n2EU4U/Pm070bV2AYKfGeT95XJrp4AkH Na0wixLJQmN1A22yHbojHkWzykQM8CRlfqiJRZfP/mpYwOSj41/uaZnyyVxD/R/u BT94XoOEIU/XfGN2l/25O3x6oxWOzhdZ9JVFdeNepdsWHzPFf9oLZIUpyAFRyz7p 0i2Xw5chxpN/kCX0cNOrf0RTo1LqBGcLWmePEL540S3aVKMhfv7Pb/PebWy4nfkI JMKYiiNmQWs3rYpsX252w8H1hO8R/DpdAF7YvMHAyQ84noTy9B7fbYxN4631Md8G jG94E7IVOcXx/uQXiMIvJ0P62Bg4Lw5VVLPkOlVPqK36BPcWzsbzXkLCUyIcR0wo QSbAsBYeUjXtnsUCbhkz =G+dA -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Putting constraints on internal type variables in GADTs
On Tue, Nov 8, 2011 at 11:49 AM, Anupam Jain ajn...@gmail.com wrote: While I understand why I get this error, I have no idea how to fix it! I cannot put a Show constraint on o1 because that variable is not exposed in the type of the expression. That means 'o1' is an existencial variable. I can work around this by changing my data type declaration to include Show constraints but I don't want to restrict my data type to only Showable things just so I could have a Show instance for debugging - Only ∷ Show o ⇒ o → T o TT ∷ (Show o1, Show o2) ⇒ T o1 → (o1 → o2) → T o2 What else can I do to declare a Show instance for my datatype? That's the only way of showing o1. Note that you don't need 'Show o2' constraint on 'TT', so this would suffice: data T o where Only :: o - T o TT :: Show o1 = T o1 - (o1 - o2) - T o2 instance Show o = Show (T o) where ... Without the inner Show constraint on TT you can't do any showing with o1. Since it is an existencial, it could be anything, even things that don't have Show instances. I think you may do something more complicated with the new ConstraintKinds extesions, something like data T c o where Only :: o - T o TT :: c o1 = T o1 - (o1 - o2) - T o2 instance Show o = Show (T Show o) where ... This is completely untested. And even if it works, I don't know if it is useful =). HTH, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Project Euler Problem 357 in Haskell
On Tuesday 08 November 2011, 12:21:14, mukesh tiwari wrote:
Hello all
Being a Haskell enthusiastic , first I tried to solve this problem in
Haskell but it running for almost 10 minutes on my computer but not
getting the answer.
Hmm, finishes in 13.36 seconds here, without any changes.
Of course, it has to be compiled with optimisations, ghc -O2.
A similar C++ program outputs the answer almost instant
2.85 seconds. g++ -O3.
So, yes, much faster, but not orders of magnitude.
so could some one please tell me how to improve this Haskell
program.
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad
prime :: Int - UArray Int Bool
prime n = runSTUArray $ do
arr - newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool )
forM_ ( takeWhile ( \x - x*x = n ) [ 2 .. n ] ) $ \i - do
ai - readArray arr i
when ( ai ) $ forM_ [ i^2 , i^2 + i .. n ] $ \j - do
writeArray arr j False
return arr
Hmm, would have to look at the core, if the optimiser isn't smart enough to
eliminate the lists, you get considerable overhead from that.
Anyway, readArray/writeArray perform bounds checks, you don't have that in
C++, so if you use unsafeRead and unsafeWrite instead, it'll be faster.
(You're doing the checks in *your* code, no point in repeating it.)
pList :: UArray Int Bool
pList = prime $ 10 ^ 8
divPrime :: Int - Bool
divPrime n = all ( \d - if mod n d == 0 then pList ! ( d + div n d )
else True ) $ [ 1 .. truncate . sqrt . fromIntegral $ n ]
Use rem and quot instead of mod and div.
That doesn't make too much difference here, but it gains a bit.
That allocates a list, if you avoid that and check in a loop, like in C++,
it'll be a bit faster.
And instead of (!), use unsafeAt to omit a redundant bounds-check.
main = putStrLn . show . sum $ [ if and [ pList ! i , divPrime . pred $
i ] then pred i else 0 | i - [ 2 .. 10 ^ 8 ] ]
Dont use
and [condition1, condition2]
that's more readable and faster if written as
condition1 condition2
Don't use pred, use (i-1) instead.
And you're gratuitously adding a lot of 0s, filter the list
sum [i | i - [1 .. ], pList ! (i+1) divPrime i]
However, you're allocating a lot of list cells here, it will be faster if
you calculate the sum in a loop, like you do in C++.
Eliminating the unnecessary bounds-checks and the intermediate lists, it
runs in 4.3 seconds here, not too bad compared to the C++.
However, use a better algorithm.
As is, for each prime p you do trial division on (p-1). For every (p-1)
satisfying the criterion, you do about sqrt(p-1) divisions, that costs a
lot of time. You can make the factorisation (and hence finding of divisors)
cheap if you slightly modify your sieve.
C++ program which outputs the answer almost instant.
#includecstdio
#includeiostream
#includevector
#define Lim 10001
using namespace std;
bool prime [Lim];
vectorint v ;
void isPrime ()
{
for( int i = 2 ; i * i = Lim ; i++)
if ( !prime [i]) for ( int j = i * i ; j = Lim ; j += i )
prime
[j]
= 1 ;
for( int i = 2 ; i = Lim ; i++) if ( ! prime[i] ) v.push_back(
i )
;
//coutv.size()endl;
//for(int i=0;i10;i++) coutv[i] ;coutendl;
}
int main()
{
isPrime();
int n = v.size();
long long sum = 0;
for(int i = 0 ; i n ; i ++)
{
int k = v[i]-1;
bool f = 0;
for(int i = 1 ; i*i= k ; i++)
if ( k % i == 0 prime[ i + ( k / i ) ] ) {
f=1 ; break ; }
if ( !f ) sum += k;
}
coutsumendl;
}
Regards
Mukesh Tiwari
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Putting constraints on internal type variables in GADTs
Hi, Anupam Jain wrote: -- My datatype data T o where Only ∷ o → T o TT ∷ T o1 → (o1 → o2) → T o2 -- Show instance for debugging instance Show o ⇒ Show (T o) where show (Only o) = Only ⊕ (show o) show (TT t1 f) = TT ( ⊕ (show t1) ⊕ ) As you noticed, the last line doesn't work because t1 is of some unknown type o1, and we know nothing about o1. In particular, we don't know how to show values of type t1, neither at compile time nor at runtime. I can't see a way around that. However, for debugging, you could do: show (TT t1 f) = TT ( ++ show (f t1) ++ ) This is not perfect, but at least it should work. Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Project Euler Problem 357 in Haskell
On Tuesday 08 November 2011, 14:54:18, Silvio Frischknecht wrote: On 11/08/2011 02:19 PM, Ryan Yates wrote: If I compile with optimizations: ghc --make -O3 primes.hs So far, -O3 is not different from -O2 (-On gives you -O2 for n 2). *Never* compile code you want to use without optimisations. Compiling without optimisations is strictly for development, when compilation time matters because of frequent recompilation. Once things have stabilised, compile them with optimisations only. I get an answer that is off by one from the C++ program in a few seconds. nice one. Though i wonder. The problem seems to be that without optimization sum is not tail-recursive. Is sum meant to not be tail-recursive? Well, it is tail recursive (foldl, basically), but not strict. So without optimisations you get the worst of boths worlds (tail recursion means no incremental output, as could be possible with foldr for lazy number types, not being strict in the accumulator means it builds huge thunks, like foldr with a function strict in the second argument). ghci sum [1..] eats up all the memory within seconds while ghci foldl' (+) 0 [1..] does not So Mukesh if you want your program to run without -Ox you should probably define your one sum' import Data.List sum' = foldl' (+) 0 That'd help, it would still be dog-slow, though, since optimisation is also crucial for the sieve. Silvio ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
Hi,
Thanks for your reply!
I made some changes according to your suggest. Now I get rid of
argument p. Unfortunately, GHC is not smart enough to memorize
this true polymorphic constant.
Can you give some hints on what kind of specialize pragmas I should
use?
Regards,
Bin Jin
On Tue, Nov 8, 2011 at 2:35 PM, o...@okmij.org wrote:
Bin Jin wrote:
Here is a function that will be called everytime by `(*)` in `Num`
typeclass
montgKeys :: (PostiveN p, Integral a, Bits a) = p - a
as you can imagine, I always pass (undefined :: p) as parameter to
`montgKeys`, so if it's handled well, it should be memorized for
future usage. But tracing shows that both `p2num` and `montgKeys` are
evaluated every time being called.
First of all, let us get rid of the argument p. Let's define
newtype W p a = W{unW:: a}
then we can easily re-write montgKeys to give it the following signature:
montgKeys :: (PostiveN p, Integral a, Bits a) = W p a
You can use ScopedTypevariables to set the needed 'p' from the context.
So, montgKeys becomes a polymorphic constant, quite like minBound.
Now, the hope is that when the types p and a are determined, GHC could
specialize montgKeys and turn it into a real constant. Perhaps some
RULE or specialize pragmas may help...
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Putting constraints on internal type variables in GADTs
2011-11-08 14:59, Felipe Almeida Lessa skrev:
On Tue, Nov 8, 2011 at 11:49 AM, Anupam Jainajn...@gmail.com wrote:
I can work around this by changing my data type declaration to include Show
constraints but I don't want to restrict my data type to only Showable
things just so I could have a Show instance for debugging -
Only ∷ Show o ⇒ o → T o
TT ∷ (Show o1, Show o2) ⇒ T o1 → (o1 → o2) → T o2
What else can I do to declare a Show instance for my datatype?
[...]
I think you may do something more complicated with the new
ConstraintKinds extesions, something like
data T c o where
Only :: o - T o
TT :: c o1 = T o1 - (o1 - o2) - T o2
instance Show o = Show (T Show o) where
...
This is completely untested. And even if it works, I don't know if it
is useful =).
If you don't have the development version of GHC, this can be done
without ConstraintKinds using the Sat class available in Syntactic
(cabal install syntactic). I attach such a solution where the GADT is
defined as follows:
data T ctx o where
Only :: Sat ctx o = o - T ctx o
TT :: Sat ctx o1 = T ctx o1 - (o1 - o2) - T ctx o2
Whether this solution is too complicated is up to you to decide :)
/ Emil
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies #-}
import Language.Syntactic
data T ctx o where
Only :: Sat ctx o = o - T ctx o
TT :: Sat ctx o1 = T ctx o1 - (o1 - o2) - T ctx o2
-- | Representation of a 'Show' constraint
data ShowCtx
instance Show a = Sat ShowCtx a
where
data Witness ShowCtx a = Show a = ShowWit
witness = ShowWit
show' :: forall a . Sat ShowCtx a = a - String
show' a = case witness :: Witness ShowCtx a of
ShowWit - show a
instance Show (T ShowCtx o) where
show (Only o) = Only ++ (show' o)
show (TT t1 f) = TT ( ++ (show' t1) ++ )
t :: Sat ctx Int = T ctx Bool
t = TT (Only (3 :: Int)) even
test = show (t :: T ShowCtx Bool)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Label macro expansion bug In HList.
Hi all, I am exploring OOHaskell and ran into some compilation issues with some of the samples. I hope this is the right place to report it. For example OCamlTutorial.hs generates the following error: ../samples/OCamlTutorial.hs:98:3: Multiple declarations of `foo' Declared at: ../samples/OCamlTutorial.hs:54:1 ../samples/OCamlTutorial.hs:98:3 Failed, modules loaded: OOHaskell, Dynamic, Print, DeepNarrow, Nominal, New. This is happening because the label macro on line 98: $(label varX) doesn't expand correctly and clashes with the foo function on line 54: foo f = f # field1 The label function is found in the Data.HList.MakeLabels module and should work this way according to the docs: runQ (label test) = putStrLn . pprint data Test deriving (Data.Typeable.Internal.Typeable) test = Data.HList.FakePrelude.proxy :: Data.HList.FakePrelude.Proxy Test But I get: data Foo_0 deriving (Data.Typeable.Internal.Typeable) foo_1 = Data.HList.FakePrelude.proxy :: Data.HList.FakePrelude.Proxy Foo_0 This still doesn't cleanly explain why OCamlTutorial.hs is failing since it seems to be generating unique datatypes and functions by suffixing them with a number, but it seems to point to the problem. I'm hoping someone who knows HList better might understand it better. Thanks, -deech ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] A Brazilian community for Haskell
Hello, To gather all Haskellers in Brazil, a new mailing list has been created: http://projects.haskell.org/cgi-bin/mailman/listinfo/haskell-br There is also the #haskell-br channel on Freenode as well as Twitter and Google+ feeds to keep everybody updated on recent activities. More information at: http://www.haskell-br.org/ []'s -- Giovanni ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Symbol collisions with -fhpc
Does anyone know what causes these? This used to work, like, a month ago. It builds fine without the -fhpc. $ ghc -fhpc -O2 -odir /tmp -hidir /tmp --make -o bin/spline3 src/*.hs [ 1 of 17] Compiling ScaleFactor ( src/ScaleFactor.hs, /tmp/ScaleFactor.o ) ... [13 of 17] Compiling Tetrahedron ( src/Tetrahedron.hs, /tmp/Tetrahedron.o ) /tmp/ghc29431_0/ghc29431_0.s: Assembler messages: /tmp/ghc29431_0/ghc29431_0.s:48147:0: Error: symbol `d2ln_info' is already defined /tmp/ghc29431_0/ghc29431_0.s:48158:0: Error: symbol `d2ll_info' is already defined /tmp/ghc29431_0/ghc29431_0.s:48169:0: Error: symbol `d2lh_info' is already defined ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] capri cabal-dev virtualenv cab
On Tue, Nov 8, 2011 at 1:43 AM, Paul R paul.r...@gmail.com wrote: At the moment, my strategy to swap GHC is purely based on the PATH environment, and that works well if you don't forget to set this env before hacking a project. This is the best solution I'm currently aware of, but there are ways we could improve on this (involving new sandboxing tools; similar to NixOS). My strategy for cabal is a bit more convoluted, because I had *so many* troubles with multiple databases (AKA system db and user db), I decided that everything would go in the 'system' one, which is actually just in my user-local GHC install, for which my user obviously have required permissions. I strongly caution against doing this. My advice is: (explanations below) 1) /never/ install anything into your system db: 2) /never/ explicitly install packages that come with ghc (the packages that are in your system db) 3) don't rely on your user package db for development -- it's a convenient place to put things you want to use in ghci, and it's the simplest thing to use when installing Haskell applications (such as cabal, cabal-dev, cab, etc...) 4) use cabal-dev for all development. Explanations: (1): Installing to your system package db will prevent you from sandboxing builds in the context of the Haskell package system. You can restrict to individual ghcs, since each ghc has it's own system db, but you can't prevent your installed package versions from causing your builds to behave differently than my builds -- as a result, you may not realize that your package version bounds are broken, for example. You'll also not notice when new versions of dependencies cause your build to break, and you may experience failures when building other packages because you have a different set of installed dependencies than the developer expected. (1 2): These things, together, will prevent you from having version conflicts between the system and user dbs. Furthermore, cabal-dev doesn't hide the system db (the tools cabal-dev uses don't expose an api that enables that in the way that the user db can be hidden, and the libraries installed in the system db by ghc usually can't be upgraded/reinstalled without upgrading ghc anyway). (3) It's impractical to keep your user db clean enough to accomplish the same objectives of sandboxed builds -- you /can/ do it, but I don't think it's worth the effort when other tools exist to help (cabal-dev being my current hammer, capri should also do it, but I haven't personally had success with capri). (4) I'm sorry that cabal-dev adds computational overhead -- this generally isn't an issue when compared to the long-term issues that come up as a result of dependency resolution /without/ a sandbox, but I realize that there are situations where cabal-dev can cause build times to take significantly longer. Ideas / suggestions / patches / etc. are happily considered :) --Rogan Things seem to work a bit better that way, I guess because cabal has easier time handling dependencies. So far I avoided the project-local database strategy because my system does not have much computational power, and I'm bored of waiting for ubiquitous packages to compile in all my folders. Arguably, that would be the only safe and simple way to avoid clashes, but I'd appreciate some shared cache to avoid recompiling the same stuff multiple times. Is there some wrappers that can take care of that ? Cheers, -- Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] capri cabal-dev virtualenv cab
On Mon, Nov 7, 2011 at 11:40 PM, Rustom Mody rustompm...@gmail.com wrote: Does anyone give me a little comparison of these? capri cabal-dev: Capri and cabal-dev both sandbox Haskell builds by restricting the set of packages that cabal can see -- I haven't had much luck with capri personally, and it appears to take a bit more doing to get a project instantiated, but it does seem to restrict access to the system package db, which cabal-dev does not do. It doesn't look like capri is under active development (only one release, roughly 18 months ago). cabal-dev was created and is primarily maintained by Galois (I'm one of the maintainers), and it's used extensively for day-to-day development. cabal-dev works by wrapping invocations of cabal with the necessary configuration files and command line arguments to restrict cabal's access to package databases to the system package db and a per-project db. In practice, this solves the vast majority of version conflict issues, and it also allows you to confidently state that your software will build with the software currently on Hackage. However, it does /not/ provide any facilities for restricting or switching the versions of ghc, and it also doesn't sandbox any other external build tools (such as alex / happy). That's not necessarily out of scope, but we haven't needed it enough yet to implement. virtualenv: I'm not familiar with virtualenv, but from skimming the site, it looks like it does something very similar to cabal-dev, but focused on python. I'm not sure if it can be used with other languages / arbitrary tools or not. cab: Others know cab much better than I do, but I'll take a shot. I think cab primarily provides a set of higher-level commands for managing a ghc package database. Amongst other things, it will show the complete dependency tree for a package that is installed, and I think it wraps 'ghc-pkg unregister' more nicely, so you can unregister a package and the packages that depend on it with one command. It also wraps cabal-dev, I think, but I haven't used that bit, so I don't know if it covers all the cabal-dev functionality yet. --Rogan What would all my requirements be? Not sure... these seem important for me 1. Need to sandbox not just haskell-projects but ghc (different compilations/versions) itself 2. Stability of the (sandboxing) tool 3. Correcting the deficiencies of cabal (eg inability to uninstall, quarrels between cabal and apt etc) OS: Debian/testing System haskell: 7.0.4 My question on beginners for a little more context: http://www.haskell.org/pipermail/beginners/2011-November/008943.html capri: http://www.haskell.org/haskellwiki/Capri virtualenv: https://github.com/Paczesiowa/virthualenv cabal-dev: http://corp.galois.com/blog/2010/12/20/cabal-dev-sandboxed-development-builds-for-haskell.html cab: http://www.mew.org/~kazu/proj/cab/en/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] capri cabal-dev virtualenv cab
On Tue, Nov 08, 2011 at 10:04:20AM -0800, Rogan Creswick wrote: On Mon, Nov 7, 2011 at 11:40 PM, Rustom Mody rustompm...@gmail.com wrote: Does anyone give me a little comparison of these? virtualenv: I'm not familiar with virtualenv, but from skimming the site, it looks like it does something very similar to cabal-dev, but focused on python. I'm not sure if it can be used with other languages / arbitrary tools or not. I'm guessing the OP was actually referring to 'virthualenv', which was recently released and works with Haskell (but is similar to virtualenv for python). It seems that virthualenv lets you set up independent environments including sandboxed builds and custom versions of GHC, etc., and switch between them. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell Platform for OSX ?
Hi, I am running GHC 6.12.3 at Mac OSX and have numerous problems with 'cabal install' of different packages. For example: ~cabal install mongoDB Resolving dependencies... Configuring mongoDB-1.1.0... Preprocessing library mongoDB-1.1.0... Building mongoDB-1.1.0... ... Control/Monad/MVar.hs:16:34: Module `Control.Exception.Control' does not export `mask' cabal: Error: some packages failed to install: mongoDB-1.1.0 failed during the building phase. The exception was: ExitFailure 1 Questions about current Haskell Platform for OSX 2011.2.0.1. : (http://hackage.haskell.org/platform/mac.html) 1) Where can I find release notes to understand what version of GHC Haskell Platform for OSX 2011.2.0.1 includes? 2) Will I be able to install mongoDB-1.1.0 on this release? 3) How to install it into a separate location so it would not ruin my current platform? Thanks! Dmitri ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Send SMTP email with plain text authentication
Hi All, I am attempting to send email to an SMTP server that uses plain text authentication. So far I have tried both the SMTPClient ( http://hackage.haskell.org/package/SMTPClient-1.0.4) and HaskellNet ( http://hackage.haskell.org/package/HaskellNet). The SMTPClient library works fine for connecting to a non-restricted local SMTP server, but doesn't seem to have any ability to authenticate, so unless it gets updated I believe it's out of the picture (unless I'm wrong about it not being able to authenticate). The HaskellNet SMTP bindings are having problems connecting to my local postfix server even without authentication involved. I get a connect: does not exist (Connection refused) error. This seems odd to me since the SMTPClient code connects to my local server just fine, so I don't believe this is a postfix configuration issue (I could be wrong here of course). Here is the code I am currently using: http://hpaste.org/53764 Any help is appreciated. Thanks, ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Depth first search
Hello all I am trying to implement depth search in Haskell. My issue here is kind of backtracking. Haskell code for depth first search import Data.List import Data.Array import Control.Monad type Node = Int type Graph = Array Int [ Node ] dfs' :: Graph - Node - [ Node ] - [ Node ] dfs' g v vis = dfsfun lst where lst = g ! v dfsfun [] = vis dfsfun ( x : xs ) | elem x vis = dfsfun xs | otherwise = dfs' g y ( v : vis ) --set the flag true if the graph is direct otherwise false buildGraph :: ( Int , Int ) - [ ( Node , Node ) ] - Bool - Graph buildGraph bnds xs f | f = accumArray ( flip (:) ) [] bnds xs --direct graph a-b | otherwise = accumArray ( flip (:) ) [] bnds xss where --indirect a - b and b - a xss = foldr ( \ ( x , y ) b - ( y , x ) : b ) xs xs dfsSearch :: Graph - Int - [ Node ] dfsSearch g v = dfs' g v [] Lets create a indirect graph ghcilet g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 4 ) ] False ghcig array (0,5) [(0,[4,3,2,1]),(1,[0]),(2,[0]),(3,[0]),(4,[0]),(5,[])] ghcidfsSearch g 0 [0] Here I am getting only 0 but it should return [ 0 , 1 , 2 , 3 , 4 ] . What is happening here when i am passing 0 as root node to function , at first level i get lst = [ 4 , 3, 2, 1 ] . First element of this list is 4 so 0 is added to vis list and now 4 is passed to dfs' as parent. When it goes down , we get lst = [0] and since 0 is member of vis list so it returns the vis as result . When we write dfs in c/c++ then it returns to calling function and again loops through remaining element which i am not able visualize in Haskell. Could some one please help me how to solve this issue . Regards Mukesh Tiwari ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] capri cabal-dev virtualenv cab
On Tue, Nov 8, 2011 at 10:57 AM, Brent Yorgey byor...@seas.upenn.edu wrote: I'm guessing the OP was actually referring to 'virthualenv', which was recently released and works with Haskell (but is similar to virtualenv for python). It seems that virthualenv lets you set up independent environments including sandboxed builds and custom versions of GHC, etc., and switch between them. Ah! Thanks, I wasn't aware of virthualenv. So far, it looks cool. I have a bit of a knee-jerk reaction to the statefull approach it takes (heavily tweaking your active shell environment to do the sandboxing), but it does do things that cabal-dev doesn't. Playing with it more now. --Rogan -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Depth first search
Major error is in the line of code: `| otherwise = dfs' g y ( v : vis )` You need something closer to: let vsx = dfs' g x (x : vis) in dfs' g v vsx That is, first visit everything you can reach from x, then backtrack to add anything else you can reach from v. This implementation will forget which nodes you've already visited from v, though that might not be a big issue. If you want to fix it, separate the `list = g ! v` into the caller, rather than the callee, such that there are two lists at `dfs'` - a to-visit list and a visited list. This fixes a few minor errors (you did not define y, and you added `v` to the visitors list). Also, fix dfsSearch: dfsSearch g v = reverse $ dfs' g v [v] That is, add the node you're starting with to those you've already visited, and since you're adding to the front of the list the element visited last, you may wish to fix that. Order in this case is [0,4,3,2,1] due to the order from buildGraph. On Tue, Nov 8, 2011 at 1:04 PM, mukesh tiwari mukeshtiwari.ii...@gmail.comwrote: Hello all I am trying to implement depth search in Haskell. My issue here is kind of backtracking. Haskell code for depth first search import Data.List import Data.Array import Control.Monad type Node = Int type Graph = Array Int [ Node ] dfs' :: Graph - Node - [ Node ] - [ Node ] dfs' g v vis = dfsfun lst where lst = g ! v dfsfun [] = vis dfsfun ( x : xs ) | elem x vis = dfsfun xs | otherwise = dfs' g y ( v : vis ) --set the flag true if the graph is direct otherwise false buildGraph :: ( Int , Int ) - [ ( Node , Node ) ] - Bool - Graph buildGraph bnds xs f | f = accumArray ( flip (:) ) [] bnds xs --direct graph a-b | otherwise = accumArray ( flip (:) ) [] bnds xss where --indirect a - b and b - a xss = foldr ( \ ( x , y ) b - ( y , x ) : b ) xs xs dfsSearch :: Graph - Int - [ Node ] dfsSearch g v = dfs' g v [] Lets create a indirect graph ghcilet g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 4 ) ] False ghcig array (0,5) [(0,[4,3,2,1]),(1,[0]),(2,[0]),(3,[0]),(4,[0]),(5,[])] ghcidfsSearch g 0 [0] Here I am getting only 0 but it should return [ 0 , 1 , 2 , 3 , 4 ] . What is happening here when i am passing 0 as root node to function , at first level i get lst = [ 4 , 3, 2, 1 ] . First element of this list is 4 so 0 is added to vis list and now 4 is passed to dfs' as parent. When it goes down , we get lst = [0] and since 0 is member of vis list so it returns the vis as result . When we write dfs in c/c++ then it returns to calling function and again loops through remaining element which i am not able visualize in Haskell. Could some one please help me how to solve this issue . Regards Mukesh Tiwari ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell Platform for OSX ?
On Tue, Nov 8, 2011 at 6:31 PM, dokondr doko...@gmail.com wrote: Hi, I am running GHC 6.12.3 at Mac OSX and have numerous problems with 'cabal install' of different packages. [...] Questions about current Haskell Platform for OSX 2011.2.0.1. : (http://hackage.haskell.org/platform/mac.html) 1) Where can I find release notes to understand what version of GHC Haskell Platform for OSX 2011.2.0.1 includes? I couldn't find a release notes document for Mac OS X but unpacking the .pkg file shows it has GHC 7.0.3. 2) Will I be able to install mongoDB-1.1.0 on this release? Hackage shows that mongoDB-1.0.1 has been the latest package compiled with GHC 7.0. For GHC 6.x it's mongoDB-0.8.1. You might have more luck upgrading the Haskell Platform or choosing a older version of mongoDB. 3) How to install it into a separate location so it would not ruin my current platform? You can install it under a different username. -- Giovanni ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell Platform for OSX ?
On Tue, Nov 8, 2011 at 4:30 PM, Giovanni Tirloni gtirl...@sysdroid.com wrote: 3) How to install it into a separate location so it would not ruin my current platform? You can install it under a different username. You can also use a sandboxed build tool like cabal-dev or virthualenv -- both of which are on hackage. (While the HP provides a great way to install Haskell, and it defines a set of mature packages, it is not necessary for development -- cabal install doesn't pay any special attention to HP packages, for example.). Having the HP installed is convenient, particularly if you run ghci a lot, but all you need is ghc, cabal-install, and a connection to hackage. --Rogan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Label macro expansion bug In HList.
I believe this is the case of OOHaskell gotten a bit out of sync with HList and GHC. Please use the latest code bases http://code.haskell.org/HList http://code.haskell.org/OOHaskell OCamlTutorial and all other OOHaskell code should work (with GHC 7.0.4). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Symbol collisions with -fhpc
On Tue, Nov 8, 2011 at 9:40 AM, Michael Orlitzky mich...@orlitzky.com wrote: Does anyone know what causes these? This used to work, like, a month ago. It builds fine without the -fhpc. What has changed in that time? New Ghc? New updates from your OS? New code in your project? Because it builds fine without -fhpc it sounds like a ghc bug. What version of ghc and on what OS? Is this 64 bit or 32bit? Basically, I think we need more information to be helpful. Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
It seems GHC can be pursuaded to do proper specialization and
memoization. We can see that, first, using trace:
class (Ord b, Integral b, Num b, Bits b) = PositiveN a b where
p2num :: Dep a b
instance (Ord b, Integral b, Num b, Bits b) = PositiveN One b where
p2num = trace p2num 1 $ Dep 1
If we define
:: PositiveN p Int = ModP2 p Int - ModP2 p Int
x = x * x * x * x
:: PositiveN p Int = ModP2 p Int - ModP2 p Int
x = x + x + x + x
test2 = x + x
where x = 1 :: ModP2 (D1 One) Int
and run test2 in GHCi, we see
*Math.Montg test2
p2num 1
1+p2num 1
4Z
That is, p2num was invoked only twice; I guess one invocation is for
converting 1 to a modular number, and the other invocation was used
for all 4 additions and 3 multiplications, distributed across
multiple functions.
Looking at the core is a better test:
ghc -O2 -c -ddump-prep Montg.hs
Math.Montg.test2
:: Math.Montg.ModP2 (Math.Montg.D1 Math.Montg.One) GHC.Types.Int
[GblId, Str=DmdType]
Math.Montg.test2 =
case Math.Montg.test14 of _ { GHC.Types.I# ww_s1Ww -
case Math.Montg.$w$s ww_s1Ww of ww1_s1WB { __DEFAULT -
case Math.Montg.$w$s ww_s1Ww of ww2_s1WC { __DEFAULT -
case Math.Montg.$fNumModP2_$spmask
`cast` (Math.Montg.NTCo:Dep
(Math.Montg.D1 Math.Montg.One) GHC.Types.Int
:: Math.Montg.Dep (Math.Montg.D1 Math.Montg.One) GHC.Types.Int
~
GHC.Types.Int)
of _ { GHC.Types.I# y#_s1WF -
case GHC.Prim.int2Word# y#_s1WF of sat_s2m8 { __DEFAULT -
case GHC.Prim.+# ww1_s1WB ww2_s1WC of sat_s2m9 { __DEFAULT -
case GHC.Prim.int2Word# sat_s2m9 of sat_s2ma { __DEFAULT -
case GHC.Prim.and# sat_s2ma sat_s2m8 of sat_s2mb { __DEFAULT -
case GHC.Prim.word2Int# sat_s2mb of sat_s2mc { __DEFAULT -
(GHC.Types.I# sat_s2mc)
As you can see, the program used Math.Montg.$fNumModP2_$spmask.
Here is thus definition in core:
Math.Montg.$fNumModP2_$spmask
:: Math.Montg.Dep (Math.Montg.D1 Math.Montg.One) GHC.Types.Int
[GblId, Str=DmdType]
Math.Montg.$fNumModP2_$spmask =
case Math.Montg.$wbitLen
@ GHC.Types.Int
GHC.Base.$fEqInt
GHC.Num.$fNumInt_$cfromInteger
You only need to look at the type to see that GHC has specialized
pmask to the particular instance Dep (D1 One) Int -- just as we
wanted.
Here is the prefix of your code with my modifications
module Math.Montg where
import Data.Bits
import Debug.Trace
newtype Dep a b = Dep { unDep :: b }
data One = One
data D0 a = D0 a
data D1 a = D1 a
class (Ord b, Integral b, Num b, Bits b) = PositiveN a b where
p2num :: Dep a b
instance (Ord b, Integral b, Num b, Bits b) = PositiveN One b where
p2num = trace p2num 1 $ Dep 1
instance PositiveN p b = PositiveN (D0 p) b where
p2num = Dep (unDep (p2num :: Dep p b) * 2)
instance PositiveN p b = PositiveN (D1 p) b where
p2num = Dep (unDep (p2num :: Dep p b) * 2 + 1)
ctz :: (Num a, Bits a) = a - Int
ctz x | testBit x 0 = 0
| otherwise = ctz (x `shiftR` 1)
bitLen :: (Num a, Bits a) = a - Int
bitLen 0 = 0
bitLen x = bitLen (x `shiftR` 1) + 1
pmask :: forall p b. (PositiveN p b) = Dep p b
pmask | bitLen n == ctz n + 1 = Dep (bit (ctz n) - 1)
| otherwise = Dep (bit (bitLen n) - 1)
where
n = unDep (p2num :: Dep p b)
addmod2 :: forall p b. (PositiveN p b) = Dep p b - Dep p b - Dep p b
addmod2 (Dep a) (Dep b) = Dep ((a + b) .. unDep (pmask :: Dep p b))
{-# INLINE addmod2 #-}
submod2 :: forall p b. (PositiveN p b) = p - b - b - b
submod2 _ a b = (a - b) .. unDep (pmask :: Dep p b)
{-# INLINE submod2 #-}
mulmod2 :: forall p b. (PositiveN p b) = Dep p b - Dep p b - Dep p b
mulmod2 (Dep a) (Dep b) = Dep $ (a * b) .. unDep (pmask :: Dep p b)
{-# INLINE mulmod2 #-}
addmod :: forall p b. (PositiveN p b) = p - b - b - b
addmod _ a b | a + b = p = a + b - p
| otherwise = a + b
where
p = unDep (p2num :: Dep p b)
{-# INLINE addmod #-}
submod :: forall p b. (PositiveN p b) = p - b - b - b
submod _ a b | a b = a + unDep (p2num :: Dep p b) - b
| otherwise = a - b
{-# INLINE submod #-}
-- | extended euclidean algorithm
-- `extgcd a b` returns `(g, x, y)` s.t. `g = gcd a b` and `ax + by = g`
--
extgcd :: Integral a = a - a - (a, a, a)
extgcd a b | a 0 = let (g, x, y) = extgcd (-a) b in (g, -x, y)
extgcd a b | b 0 = let (g, x, y) = extgcd a (-b) in (g, x, -y)
extgcd a 0 = (a, 1, 0)
extgcd a b = let
(adivb, amodb) = a `divMod` b
(g, y, x) = extgcd b amodb
-- (a - a / b * b) * x + b * y
-- = a * x - a / b * b * x + b * y
-- = a * x + (y - a / b * x) * b
in
(g, x, y - adivb * x)
newtype PositiveN p a = ModP2 p a = ModP2 { unModP2 :: a } deriving Eq
instance PositiveN p a = Show (ModP2 p a) where
show (ModP2 r) = show r ++ + ++ show (unDep (pmask :: Dep p a) + 1) ++ Z
-- In principle, Dep and
