[Haskell-beginners] Sieve of Aritosthenes

[Peter McIlroy]

Apologies for the empty post.
You might turn your attention to the following web page, which approaches the problem using recursive co-routines. Amidst a discussion of UNIX pipes, both in history and as a primitive co-routine implementation, there is a two-line Haskell program.

http://www.cs.dartmouth.edu/~doug/sieve/



-----Original Message-----
From: "beginners-request at haskell.org" <beginners-request at haskell.org>
Sent: ‎5/‎5/‎2016 11:10 AM
To: "beginners at haskell.org" <beginners at haskell.org>
Subject: Beginners Digest, Vol 95, Issue 8

Send Beginners mailing list submissions to
	beginners at haskell.org

To subscribe or unsubscribe via the World Wide Web, visit
	http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
	beginners-request at haskell.org

You can reach the person managing the list at
	beginners-owner at haskell.org

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."


Today's Topics:

   1. Re:  Timed Profiling (Vale Cofer-Shabica)
   2. Re:  Infinite recursion in list comprehension (Silent Leaf)
   3. Re:  Infinite recursion in list comprehension (Silent Leaf)


----------------------------------------------------------------------

Message: 1
Date: Thu, 5 May 2016 10:38:50 -0400
From: Vale Cofer-Shabica <vale.cofershabica at gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
	beginner-level topics related to Haskell <beginners at haskell.org>
Subject: Re: [Haskell-beginners] Timed Profiling
Message-ID:
	<CAAzfV4Rse76Yw8Vq_Mqny_cFRw_9_FFcXBAAm4W+54zXWTuveQ at mail.gmail.com>
Content-Type: text/plain; charset="utf-8"

timeout(1) allows you to specify the signal(7) sent with the --signal
option. It may be worth experimenting with different values. One of them
might terminate the program while allowing it to clean up and generate
profiling information. I don't know enough about the haskell runtime to
know.

-vale

--
vale cofer-shabica
401.267.8253

On Wed, May 4, 2016 at 7:06 PM, Tim Perry <tim.v2.0 at gmail.com> wrote:

> I believe that timeout sends a kill signal to the process in question. I
> imagine that the process is killed before the profiling information is
> written and so you get an empty file. When you close the program with
> alt-F4, the program gets a chance to shut down cleanly and writes on the
> profiling information (.prof)
>
>
> On Wed, May 4, 2016 at 9:11 AM, Ben Rogalski <bwrogalski at gmail.com> wrote:
>
>> I would like to generate a time and allocation profiling report after
>> running my program for exactly 60 seconds (on Ubuntu Linux).
>>
>> I compiled with the following flags:
>>
>> -rtsopts -auto-all -caf-all -fforce-recomp
>>
>> I then ran the program:
>>
>> The program stops after 60 seconds, but the .prof file is empty.
>>
>> When I run the program without using timeout, and close it manually (Alt
>> F4, it is a graphical program), the .prof file contains the information I
>> would expect.
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160505/b8bbb307/attachment-0001.html>

------------------------------

Message: 2
Date: Thu, 5 May 2016 19:57:52 +0200
From: Silent Leaf <silent.leaf0 at gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
	beginner-level topics related to Haskell <beginners at haskell.org>
Subject: Re: [Haskell-beginners] Infinite recursion in list
	comprehension
Message-ID:
	<CAGFccjMN86K9ibBPi_q+Jx07tU4Jc0zbF9Kggy12zY1CA2=pfg at mail.gmail.com>
Content-Type: text/plain; charset="utf-8"

I succeeded to get it working with n = 2,000,000 at least, through this
means:

primesBelow :: Int -> [Int]
primesBelow max = list
  where list = 2:3:rest
        rest = [ v | k <- [1..(max-1)`div`6], i <- [-1, 1]
                       , let v = 6*k+i, checker v]
        ...
        ...

the function "checker" (in the list comprehension, as conditional) is using
itself in its definition the variable "list" to generate the test for each
"v" of the list comprehension "rest". I dunno if this kind of recursion
suits you.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160505/314e2cca/attachment-0001.html>

------------------------------

Message: 3
Date: Thu, 5 May 2016 20:10:29 +0200
From: Silent Leaf <silent.leaf0 at gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
	beginner-level topics related to Haskell <beginners at haskell.org>
Subject: Re: [Haskell-beginners] Infinite recursion in list
	comprehension
Message-ID:
	<CAGFccjPCcn0q+ZvrE+BNN7iaCw-b4HJURfPDceVELcJKT3KdoQ at mail.gmail.com>
Content-Type: text/plain; charset="utf-8"

Implicitly, primesBelow shouldn't ever in fact call itself, not as it is
articulated here **at the very least**, not without wasting a lot of
calculus.

As it is, and maybe no matter what (i'm not sure, don't have the knowledge
to certify that), when primesBelow checks if a value "v" is prime or not,
well no matter what it'll already have calculated and stored all primes
below this value n (this, according to how primesBelow is articulated, aka
filtering of Naturals bottom-top).

Thus, if for each potential element "v" of the result (in my version,
"list") of primesBelow, you call once again primesBelow, asking it to
generate again all primes below sqrt(v), you'll do nothing more than doing
again what you already did, because all those previous primes have already
been generated, stored away, and especially very accessible, in the
list-result in-construction of the **current** call to primesBelow, so if
you don't use it but call again primesBelow to get a copy of what you
already have, you'll multiply immensely the work without any gain.
That's why I named the very result of primesBelow, to get a way to use
"list" (the previously generated items of the future result-list) in
"checker".

2016-05-05 15:44 GMT+02:00 Dushyant Juneja <juneja.dushyant at gmail.com>:

> Hi Akash,
>
> Thanks for the response. A very simple and lucid explanation. Looks
> interesting.
>
> So, here's the big picture now, for which I need this. I intend to
> implement a lookalike Sieve of Eratosthenes algorithm in haskell. For this,
> I intend to use the earlier function recursively, as follows:
>
> primesBelowN :: Integer -> [Integer]
> primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]]
>                      where f x = foldr g True xs
>                                  where g t ac = (x `rem` t /= 0) && ac
>                                        xs = [ m | m <- primesBelowN n, m
> <= (truncate (sqrt (fromInteger x)))]
>
> Of course, I could do something like this:
>
> primesBelowN :: Integer -> [Integer]
> primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]]
>                      where f x = foldr g True xs
>                                  where g t ac = (x `rem` t /= 0) && ac
>                                        xs = [ m | m <- primesBelowN (truncate
> (sqrt (fromInteger x)))]
>
> However, this calls primesBelowN function with a new argument everytime. I
> suppose that is not optimal (correct me if I am wrong).
>
> Point number 2: both fail. Grrh.
>
> Any ideas how I could go recursive with this function?
>
> Dushyant
>
>
> On Thu, May 5, 2016 at 6:31 PM akash g <akaberto at gmail.com> wrote:
>
>> Hi Dushyant,
>>
>> The problem most likely is
>> [m | m <- [5,7..], m <= (truncate (sqrt (fromInteger x)))]
>>
>>  This is because, the filter condition (the last part) does a very simple
>> thing:  It filters out any element that does not fulfil the criteria.  You
>> are operating on a list that is monotonically increasing.  However, the
>> filter isn't aware of this property.  Hence, this list comprehension never
>> ends because it doesn't know that once the condition fails, it will always
>> fail.
>>
>> Thus, the solution would be to generate a finite set (or take a part of
>> the infinite set using takeWhile or something like that), instead of using
>> an infinite one.
>>
>> Regards,
>> G Akash.
>>
>> On Thu, May 5, 2016 at 6:13 PM, Dushyant Juneja <
>> juneja.dushyant at gmail.com> wrote:
>>
>>> Hi,
>>>
>>> I seem to be landing into infinite recursion when using higher order
>>> functions with list comprehension. Take this for an example. The following
>>> works well, and gives answers for numbers like 2000000 as well:
>>>
>>> primesBelowN :: Integer -> [Integer]
>>> primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1,
>>> 1]]
>>>                      where f x = foldr g True xs
>>>                                  where g t ac = (x `rem` t /= 0) && ac
>>>                                        xs = [5, 7..(truncate (sqrt
>>> (fromInteger x)))]
>>>
>>>
>>> However, the following never returns anything for the same number,
>>> probably due to some kind of loop malfunction:
>>>
>>> primesBelowN :: Integer -> [Integer]
>>> primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1,
>>> 1]]
>>>                      where f x = foldr g True xs
>>>                                  where g t ac = (x `rem` t /= 0) && ac
>>>                                        xs = [ m | m <- [5, 7, ..], m <= (truncate
>>> (sqrt (fromInteger x)))]
>>>
>>> Any ideas what might be going wrong?
>>>
>>> Thanks in advance!
>>>
>>> DJ
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> Beginners at haskell.org
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>
>>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160505/d46458fe/attachment.html>

------------------------------

Subject: Digest Footer

_______________________________________________
Beginners mailing list
Beginners at haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


------------------------------

End of Beginners Digest, Vol 95, Issue 8
****************************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160505/5165798f/attachment-0001.html>