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