[Haskell-beginners] foldr on infinite list to decide prime number

[Chul-Woong Yang]

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 <driemer.riemer at gmail.com>:
> 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 at 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 at colorado.edu
> Phone: (303) 906-2194
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>