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