foldr on infinite list to decide prime number

newer
Why does sequence (map print [1,...

Chul-Woong Yang

2 Feb 2016 2 Feb '16

1:32 a.m.

Hi, all. While I know that foldr can be used on infinite list to generate infinite list, I'm having difficulty in understaind following code: isPrime n = n > 1 && -- from haskell wiki foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes primes = 2 : filter isPrime [3,5..] primes is a infinite list of prime numbers, and isPrime does foldr to get a boolean value. What causes foldr to terminate folding? Any helps will be deeply appreciated. Thank you. Chul-Woong

Attachments:

attachment.html (text/html — 1.9 KB)

Show replies by date

Chul-Woong Yang

2 Feb 2 Feb

1:36 a.m.

New subject: foldr on infinite list to decide prime number

I feel sorry for posting mis-formatted code. I re-post the question. -- Hi, all. While I know that foldr can be used on infinite list to generate infinite list, I'm having difficulty in understaind following code: isPrime n = n > 1 && -- from haskell wiki foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes primes = 2 : filter isPrime [3,5..] primes is a infinite list of prime numbers, and isPrime does foldr to get a boolean value. What causes foldr to terminate folding? Any helps will be deeply appreciated. Thank you. 2016-02-02 10:32 GMT+09:00 Chul-Woong Yang :

...

Hi, all.

While I know that foldr can be used on infinite list to generate infinite list, I'm having difficulty in understaind following code:

isPrime n = n > 1 && -- from haskell wiki foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes primes = 2 : filter isPrime [3,5..]

primes is a infinite list of prime numbers, and isPrime does foldr to get a boolean value. What causes foldr to terminate folding?

Any helps will be deeply appreciated.

Thank you.

Chul-Woong

Gesh

1:33 p.m.

New subject: foldr on infinite list to decide prime number

On February 2, 2016 3:36:03 AM GMT+02:00, Chul-Woong Yang wrote:

...

I feel sorry for posting mis-formatted code. I re-post the question. --

Hi, all.

While I know that foldr can be used on infinite list to generate infinite list, I'm having difficulty in understaind following code:

isPrime n = n > 1 && -- from haskell wiki foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes primes = 2 : filter isPrime [3,5..]

primes is a infinite list of prime numbers, and isPrime does foldr to get a boolean value. What causes foldr to terminate folding?

Any helps will be deeply appreciated.

Thank you.

2016-02-02 10:32 GMT+09:00 Chul-Woong Yang :

...
Hi, all.

While I know that foldr can be used on infinite list to generate infinite list, I'm having difficulty in understaind following code:

isPrime n = n > 1 && -- from haskell wiki foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes primes = 2 : filter isPrime [3,5..]

primes is a infinite list of prime numbers, and isPrime does foldr to get a boolean value. What causes foldr to terminate folding?

Any helps will be deeply appreciated.

Thank you.

Chul-Woong

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

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

Note that || is lazy, specifically:

...

True || _ = True False || x = x Hence, once foldr reaches a prime larger than sqrt n, the first branch of || will be True, short-circuiting the entire infinite computation.

HTH, Gesh

Chul-Woong Yang

3 Feb 3 Feb

12:36 a.m.

New subject: foldr on infinite list to decide prime number

Thank you for kind response. See you in another thread. :-) 2016-02-02 22:33 GMT+09:00 Gesh :

...

On February 2, 2016 3:36:03 AM GMT+02:00, Chul-Woong Yang wrote:

...
I feel sorry for posting mis-formatted code. I re-post the question. --

Hi, all.

While I know that foldr can be used on infinite list to generate infinite list, I'm having difficulty in understaind following code:

isPrime n = n > 1 && -- from haskell wiki foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes primes = 2 : filter isPrime [3,5..]

primes is a infinite list of prime numbers, and isPrime does foldr to get a boolean value. What causes foldr to terminate folding?

Any helps will be deeply appreciated.

Thank you.

2016-02-02 10:32 GMT+09:00 Chul-Woong Yang :

...
Hi, all.

While I know that foldr can be used on infinite list to generate infinite list, I'm having difficulty in understaind following code:

isPrime n = n > 1 && -- from haskell wiki foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes primes = 2 : filter isPrime [3,5..]

primes is a infinite list of prime numbers, and isPrime does foldr to get a boolean value. What causes foldr to terminate folding?

Any helps will be deeply appreciated.

Thank you.

Chul-Woong

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

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

Note that || is lazy, specifically:

...
True || _ = True False || x = x Hence, once foldr reaches a prime larger than sqrt n, the first branch of || will be True, short-circuiting the entire infinite computation.

HTH, Gesh _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Francesco Ariis

2 Feb 2 Feb

2:01 a.m.

New subject: foldr on infinite list to decide prime number

On Tue, Feb 02, 2016 at 10:32:10AM +0900, Chul-Woong Yang wrote:

...

Hi, all.

While I know that foldr can be used on infinite list to generate infinite list, I'm having difficulty in understaind following code:

isPrime n = n > 1 && -- from haskell wiki foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes primes = 2 : filter isPrime [3,5..]

primes is a infinite list of prime numbers, and isPrime does foldr to get a boolean value. What causes foldr to terminate folding?

foldr _immediately_ calls the passed function, hence /it can short circuit/, that isn't the case for foldl. I wrote an article to explain it [1]. It was drafted in a time when foldr and friends were monomorphic (i.e. they only worked with lists), but it should illustrate the point nicely. Current polymorphic implementation of foldr is: foldr :: (a -> b -> b) -> b -> t a -> b foldr f z t = appEndo (foldMap (Endo #. f) t) z and I must admit I have problems explaining why it terminates early (as it does). [1] http://ariis.it/static/articles/haskell-laziness/page.html (more complex cases section)

Chul-Woong Yang

2:12 a.m.

New subject: foldr on infinite list to decide prime number

Aha! I see. Thank you for pointing the short-circuiting of (||), and for nice article. Regards, 2016-02-02 11:01 GMT+09:00 Francesco Ariis :

...

On Tue, Feb 02, 2016 at 10:32:10AM +0900, Chul-Woong Yang wrote:

...
Hi, all.

While I know that foldr can be used on infinite list to generate infinite list, I'm having difficulty in understaind following code:

isPrime n = n > 1 && -- from haskell wiki foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes primes = 2 : filter isPrime [3,5..]

primes is a infinite list of prime numbers, and isPrime does foldr to get a boolean value. What causes foldr to terminate folding?

foldr _immediately_ calls the passed function, hence /it can short circuit/, that isn't the case for foldl.

I wrote an article to explain it [1]. It was drafted in a time when foldr and friends were monomorphic (i.e. they only worked with lists), but it should illustrate the point nicely.

Current polymorphic implementation of foldr is:

foldr :: (a -> b -> b) -> b -> t a -> b foldr f z t = appEndo (foldMap (Endo #. f) t) z

and I must admit I have problems explaining why it terminates early (as it does).

[1] http://ariis.it/static/articles/haskell-laziness/page.html (more complex cases section) _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

derek riemer

3 Feb 3 Feb

12:52 a.m.

New subject: foldr on infinite list to decide prime number

Doesn't foldr have to "reach" to the far right of the list of infinite primes to get the last number since it consumes from the right? On 2/1/2016 7:01 PM, Francesco Ariis wrote:

...

On Tue, Feb 02, 2016 at 10:32:10AM +0900, Chul-Woong Yang wrote:

...
Hi, all.

While I know that foldr can be used on infinite list to generate infinite list, I'm having difficulty in understaind following code:

isPrime n = n > 1 && -- from haskell wiki foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes primes = 2 : filter isPrime [3,5..]

primes is a infinite list of prime numbers, and isPrime does foldr to get a boolean value. What causes foldr to terminate folding? foldr _immediately_ calls the passed function, hence /it can short circuit/, that isn't the case for foldl.

I wrote an article to explain it [1]. It was drafted in a time when foldr and friends were monomorphic (i.e. they only worked with lists), but it should illustrate the point nicely.

Current polymorphic implementation of foldr is:

foldr :: (a -> b -> b) -> b -> t a -> b foldr f z t = appEndo (foldMap (Endo #. f) t) z

and I must admit I have problems explaining why it terminates early (as it does).

[1] http://ariis.it/static/articles/haskell-laziness/page.html (more complex cases section) _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

-- ------------------------------------------------------------------------ Derek Riemer * Department of computer science, third year undergraduate student. * Proud user of the NVDA screen reader. * Open source enthusiast. * Member of Bridge Cu * Avid skiier. Websites: Honors portfolio http://derekriemer.com Awesome little hand built weather app! http://django.derekriemer.com/weather/ email me at derek.riemer@colorado.edu mailto:derek.riemer@colorado.edu Phone: (303) 906-2194

Francesco Ariis

1:55 a.m.

New subject: foldr on infinite list to decide prime number

On Tue, Feb 02, 2016 at 05:52:08PM -0700, derek riemer wrote:

...

Doesn't foldr have to "reach" to the far right of the list of infinite primes to get the last number since it consumes from the right?

foldl is /left/ associative, foldr /right/ associative. λ> foldl1 (-) [1..3] -4 -- which is: ((1-2)-3) λ> foldr1 (-) [1..3] 2 -- which is (1-(2-3)) Haskell being non strict (i.e. "proceeding from the outside"), it will immediately short circuit on foldr but have to build the whole list first on foldl.

Chul-Woong Yang

1:56 a.m.

New subject: foldr on infinite list to decide prime number

Simple foldr'ing over infinite list: foldr (\x acc -> x || acc) False $ repeat True Under lazy evaluation, the foldr stops expansion when x has True value since (||) short-circuits evaluation. In strict evaluation, foldr should reach to the far right of the infinite list as you said. 2016-02-03 9:52 GMT+09:00 derek riemer :

...

Doesn't foldr have to "reach" to the far right of the list of infinite primes to get the last number since it consumes from the right?

On 2/1/2016 7:01 PM, Francesco Ariis wrote:

On Tue, Feb 02, 2016 at 10:32:10AM +0900, Chul-Woong Yang wrote:

Hi, all.

While I know that foldr can be used on infinite list to generate infinite list, I'm having difficulty in understaind following code:

isPrime n = n > 1 && -- from haskell wiki foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes primes = 2 : filter isPrime [3,5..]

primes is a infinite list of prime numbers, and isPrime does foldr to get a boolean value. What causes foldr to terminate folding?

foldr _immediately_ calls the passed function, hence /it can short circuit/, that isn't the case for foldl.

I wrote an article to explain it [1]. It was drafted in a time when foldr and friends were monomorphic (i.e. they only worked with lists), but it should illustrate the point nicely.

Current polymorphic implementation of foldr is:

foldr :: (a -> b -> b) -> b -> t a -> b foldr f z t = appEndo (foldMap (Endo #. f) t) z

and I must admit I have problems explaining why it terminates early (as it does).

[1] http://ariis.it/static/articles/haskell-laziness/page.html (more complex cases section) _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

-- ________________________________

Derek Riemer

Department of computer science, third year undergraduate student. Proud user of the NVDA screen reader. Open source enthusiast. Member of Bridge Cu Avid skiier.

Websites: Honors portfolio Awesome little hand built weather app!

email me at derek.riemer@colorado.edu Phone: (303) 906-2194

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

Thomas Koster

1:59 a.m.

New subject: foldr on infinite list to decide prime number

On 3 February 2016 at 11:52, derek riemer wrote:

...

Doesn't foldr have to "reach" to the far right of the list of infinite primes to get the last number since it consumes from the right?

foldr does not consume from the right. It is right-associative. See these simulations: http://foldr.com http://foldl.com Notice that the essential difference between foldr and foldl is the placement of the parentheses in the result, which the simulations show very well. Whether that expression "short-circuits" or not depends on the operator you used with your fold. Operators that are lazy in their second argument (at least some of the time), like "||" and ":", can short-circuit when used with foldr. A common mistake is to think the parentheses force an evaluation order, like "inside-out" for example. This is not the case for lazy languages like Haskell. This unfortunate confusion probably arises because parentheses often do prescribe evaluation order in basic arithmetic and strict languages like Java. Hope this helps, Thomas Koster

3489

Age (days ago)

3490

Last active (days ago)

List overview

Download

9 comments

5 participants

participants (5)

Chul-Woong Yang
derek riemer
Francesco Ariis
Gesh
Thomas Koster