Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Haskell for Android (Miroslav Karpis)
2. Re: Haskell for Android (Henk-Jan van Tuyl)
3. Re: Question about time consume when calculate prime numbers
(Fletcher Stump Smith)
4. cyclic imports (Christopher Howard)
5. Re: cyclic imports (Chadda? Fouch?)
----------------------------------------------------------------------
Message: 1
Date: Wed, 12 Sep 2012 19:21:28 +0200
From: Miroslav Karpis <miroslav.kar...@gmail.com>
Subject: [Haskell-beginners] Haskell for Android
To: Beginners@haskell.org
Message-ID: <462f4004-91b0-42aa-a947-251be3fc9...@gmail.com>
Content-Type: text/plain; charset=windows-1252
Hi haskellers, please can you help me with this? I read several posts about it,
but unfortunately it is still not clear. What is (if there is) the most
straight way to port haskell code to android?
Translate haskell to c or javascript? Not sure how debugging will work this
way?. ?
thanks,
m.
------------------------------
Message: 2
Date: Wed, 12 Sep 2012 22:30:57 +0200
From: "Henk-Jan van Tuyl" <hjgt...@chello.nl>
Subject: Re: [Haskell-beginners] Haskell for Android
To: Beginners@haskell.org, "Miroslav Karpis"
<miroslav.kar...@gmail.com>
Message-ID: <op.wkjhxvl5pz0...@zen5.arnhem.chello.nl>
Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes
On Wed, 12 Sep 2012 19:21:28 +0200, Miroslav Karpis
<miroslav.kar...@gmail.com> wrote:
> Hi haskellers, please can you help me with this? I read several posts
> about it, but unfortunately it is still not clear. What is (if there is)
> the most straight way to port haskell code to android?
There is a HaskellWiki page for Android[0] with some interesting links.
This article is a stub; anyone who is an expert in this area, please add
more info.
Regards,
Henk-Jan van Tuyl
[0] http://www.haskell.org/haskellwiki/Android
--
http://Van.Tuyl.eu/
http://members.chello.nl/hjgtuyl/tourdemonad.html
Haskell programming
--
------------------------------
Message: 3
Date: Wed, 12 Sep 2012 15:32:13 -0700
From: Fletcher Stump Smith <fletcher...@gmail.com>
Subject: Re: [Haskell-beginners] Question about time consume when
calculate prime numbers
To: Yi Cheng <chengyi...@gmail.com>
Cc: beginners@haskell.org
Message-ID:
<CAPEBXRzXt+LNGHDSgWBgpniS34wZxt+HZobA=anox9krwht...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
You might also be interested in this paper:
www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf . I thought it was a good
analysis/
On Wed, Sep 12, 2012 at 8:53 AM, Yi Cheng <chengyi...@gmail.com> wrote:
> Thank you, very much. It's exactly the thing I want to know.
>
> Yi. Cheng
>
>
> On Wed, Sep 12, 2012 at 8:41 PM, Lorenzo Bolla <lbo...@gmail.com> wrote:
>>
>>
>>
>> On Wed, Sep 12, 2012 at 1:17 PM, Yi Cheng <chengyi...@gmail.com> wrote:
>>>
>>>
>>> Thanks for answering my question, but I'm still confused by some details.
>>> I don't quite agree with you that Eratosthenes algorithm must be
>>> implemented with a complexity of O(n^2) in space. When the n is used to
>>> calculate the primes below it, it can be implemented in space complexity
>>> O(n). For example, in languages, like C/C++, we can allocate a array. So I
>>> think the the complexity of O(n^2) in space you mentioned, is the complexity
>>> of "the beautiful code". So here's the question, can Eratosthenes algorithm
>>> be implemented in a more gentle way?
>>
>>
>> Correct: I referred to your implementation. See here
>> (http://www.haskell.org/haskellwiki/Prime_numbers#Sieve_of_Eratosthenes) for
>> many different (and more efficient) implementations of Eratosthenes.
>>
>>
>>> Then I think maybe there is a more beautiful and practical way to
>>> implement it.
>>> One method of mine is trying to judge whether a number is a prime just by
>>> the primes less than it, such as if the greatest common divisor of the
>>> number and the product of the primes less than it equals to 1. But the
>>> product of the primes is too large.
>>>
>>> So I wander if there is a concise method to solve the problem with a
>>> faster method. In my C++ version, the Eratosthenes is implemented in linear
>>> space complexity, and optimize in filtering the numbers which can be divided
>>> by a prime. This code is faster than the original algorithm implemented by
>>> me(It was also implemented it in C++, and slower than the following code).
>>> I know, when writing Haskell code, it would be better to forget some
>>> experience in command-line language, but I want to know whether there is a
>>> faster method to solve the problem.
>>>
>>>
>>> Thank you.
>>> Yi. Cheng
>>>
>>> The code in my c++ version.
>>> #include <iostream>
>>> using namespace std;
>>> int main(){
>>> int p[2000000] = {0};
>>> long sum = 0;
>>> int f = 1;
>>> for(long i=2; i <= 2000000; ++i){
>>> if(p[i] == 0){
>>> sum += i;
>>> for(long j = i * i; j < 2000000; j += i)
>>> p[j] = 1;
>>> }
>>> }
>>> cout<<sum<<endl;
>>> return 0;
>>>
>>> }
>>>
>>
>> This implementation looks like the one here:
>> http://www.haskell.org/haskellwiki/Prime_numbers#From_Squares, with the
>> difference that in C++ you are modifying your array in-place instead of
>> generating it lazily. It's not equivalent to your "beautiful" version in
>> Haskell.
>>
>> hth,
>> L.
>>
>>
>>
>>
>>
>>>
>>> On Wed, Sep 12, 2012 at 5:26 PM, Lorenzo Bolla <lbo...@gmail.com> wrote:
>>>>
>>>>
>>>>
>>>> On Wed, Sep 12, 2012 at 9:06 AM, Yi Cheng <chengyi...@gmail.com> wrote:
>>>>>
>>>>> Recently, I'm trying to solve some problems in project euler using
>>>>> haskell. When it came to problem 10, calculating the sum of all primes
>>>>> below
>>>>> 20000000, I try to write a program which can generate primes.
>>>>> In my memory Eratosthenes is faster than just whether a number can be
>>>>> divided by the number less then the square root of it.
>>>>> Firstly, I wrote the following programs:
>>>>>
>>>>> module Main where
>>>>> isPrime x = isPrime' 3 x (round . sqrt. fromIntegral $ x)
>>>>> isPrime' d target maxd
>>>>> | d > maxd = True
>>>>> | mod target d == 0 = False
>>>>> | otherwise = isPrime' (d + 2) target maxd
>>>>>
>>>>> main = print $ (sum (filter isPrime [3,5..2000000]) + 2)
>>>>>
>>>>> And it consume about 11s in my computer.
>>>>> Then, I tried to figure out how to solve the problem by Eratosthenes,
>>>>> but failed. Later, I find a program implemented by others, meeting my
>>>>> purpose and I've used it to solve the problem:
>>>>>
>>>>> primes :: [Int]
>>>>> primes = primes' [2..]
>>>>>
>>>>> primes' :: [Int] -> [Int]
>>>>> primes' [] = []
>>>>> primes' (n:ns) = n : primes' (filter (\v -> v `mod` n /= 0) ns)
>>>>>
>>>>> solve x = sum $ primes' [2..x]
>>>>>
>>>>> main = print $ solve 2000000
>>>>>
>>>>> Well, although the code is beautiful, it is slow. Even waiting for a
>>>>> minute, no answer was printed.
>>>>>
>>>>> In C version, Eratosthenes is faster than the method implemented in my
>>>>> earlier code, which only consume 0.3s(the earlier method consume 1.6s).
>>>>>
>>>>> So I want to know, why Eratosthenes implemented in Haskell is slow than
>>>>> the ugly code implemented by me.
>>>>> Could anyone tell me?
>>>>>
>>>>
>>>> Eratosthenes's complexity is O(n^2) (both space and time), whereas the
>>>> "ugly" one has a sub-quadratic running complexity and linear in space.
>>>>
>>>> Try to profile them:
>>>> $> ghc -O2 --make -prof -auto-all <filename>
>>>> $> ./primes +RTS -p -hc
>>>> $> hp2ps primes.hp
>>>>
>>>> You'll see that most of the time is spent allocating space which is
>>>> never released.
>>>> You could play a bit with strictness, but the main problem is the awful
>>>> complexity of the algorithm.
>>>>
>>>> hth,
>>>> L.
>>>>
>>>>
>>>>
>>>>>
>>>>> Thank you
>>>>> Yi Cheng
>>>>>
>>>>> _______________________________________________
>>>>> Beginners mailing list
>>>>> Beginners@haskell.org
>>>>> http://www.haskell.org/mailman/listinfo/beginners
>>>>>
>>>>
>>>
>>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
------------------------------
Message: 4
Date: Wed, 12 Sep 2012 15:22:16 -0800
From: Christopher Howard <christopher.how...@frigidcode.com>
Subject: [Haskell-beginners] cyclic imports
To: Haskell Beginners <beginners@haskell.org>
Message-ID: <50511928.8090...@frigidcode.com>
Content-Type: text/plain; charset="iso-8859-1"
In my app, I have a class definition and a data type definition that
depend on each other:
code:
--------
class (InternallyUpdating a) => Transient a where
{- Whether or not the object should be removed from existence -}
expired' :: a -> Maybe [AfterEffect]
data AfterEffect =
forall a. ( Animation a
, Transient a
) => VisualEffect a
-- to be extended algebraically...
--------
It's written in this somewhat recursive manner so that one effect can
give rise to another effect when it is completed. This code compiles
just fine when the two definitions are in the same file. However, if I
separate them out to different modules, each module most import the
other, resulting in this error:
code:
--------
Module imports form a cycle:
module `AfterEffect' (AfterEffect.hs)
imports `Updating' (./Updating.hs)
which imports `AfterEffect' (AfterEffect.hs)
--------
As a point of curiosity, at least, I'm wondering why GHC does not allow
mutally-dependent imports, as recursive dependencies doesn't seem to be
a problem in any other area of Haskell. And I'm wondering if there is
some kind of trick to get around this and allow the cyclic dependency.
--
frigidcode.com
indicium.us
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 551 bytes
Desc: OpenPGP digital signature
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120912/8444a298/attachment-0001.pgp>
------------------------------
Message: 5
Date: Thu, 13 Sep 2012 01:24:55 +0200
From: Chadda? Fouch? <chaddai.fou...@gmail.com>
Subject: Re: [Haskell-beginners] cyclic imports
To: Christopher Howard <christopher.how...@frigidcode.com>
Cc: Haskell Beginners <beginners@haskell.org>
Message-ID:
<CANfjZRaTg3cA4+s7mO5A=7r0a3s52kmsi7rhvrh4zzutt3r...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Thu, Sep 13, 2012 at 1:22 AM, Christopher Howard <
christopher.how...@frigidcode.com> wrote:
> As a point of curiosity, at least, I'm wondering why GHC does not allow
> mutally-dependent imports, as recursive dependencies doesn't seem to be
> a problem in any other area of Haskell. And I'm wondering if there is
> some kind of trick to get around this and allow the cyclic dependency.
>
Allowing mutually-dependent imports in all generality would complicate the
task of GHC name resolution and type inference but if you're ready to do a
bit more work, you can have cyclic dependency with an hs-boot file, see GHC
doc :
http://www.haskell.org/ghc/docs/latest/html/users_guide/separate-compilation.html#mutual-recursion
--
Jeda?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120913/48b6afd8/attachment-0001.htm>
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 51, Issue 20
*****************************************
