# foldr on infinite list to decide prime number

10 messages
Open this post in threaded view
|

## foldr on infinite list to decide prime number

 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 [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

## Re: 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 primesprimes = 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 [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

## Re: foldr on infinite list to decide prime number

 In reply to this post by Chul-Woong Yang 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 [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

## Re: 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 <[hidden email]>: > 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 > [hidden email] > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

## Re: foldr on infinite list to decide prime number

 In reply to this post by Chul-Woong Yang On February 2, 2016 3:36:03 AM GMT+02:00, Chul-Woong Yang <[hidden email]> 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 <[hidden email]>: > >> 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 >[hidden email] >http://mail.haskell.org/cgi-bin/mailman/listinfo/beginnersNote 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 [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

## Re: 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 <[hidden email]>: > On February 2, 2016 3:36:03 AM GMT+02:00, Chul-Woong Yang <[hidden email]> 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 <[hidden email]>: >> >>> 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 >>[hidden email] >>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 > [hidden email] > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

## Re: foldr on infinite list to decide prime number

In reply to this post by Francesco Ariis
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).

complex cases section)
_______________________________________________
Beginners mailing list
[hidden email]
```

--

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

[hidden email]
Phone: (303) 906-2194

_______________________________________________
Beginners mailing list
[hidden email]
Open this post in threaded view
|

## Re: 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. _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners