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 |
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]>:
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
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 |
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 |
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/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 |
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 |
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). [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 --
Derek Riemer
Websites:
[hidden email]
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
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 |
In reply to this post by derek riemer
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 <[hidden email]>: > 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 > [hidden email] > 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 [hidden email] > Phone: (303) 906-2194 > > > _______________________________________________ > 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 |
In reply to this post by derek riemer
On 3 February 2016 at 11:52, derek riemer <[hidden email]> 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 _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
Free forum by Nabble | Edit this page |