foldr on infinite list to decide prime number

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

foldr on infinite list to decide prime number

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
Reply | Threaded
Open this post in threaded view
|

Re: foldr on infinite list to decide prime number

Chul-Woong Yang
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
Reply | Threaded
Open this post in threaded view
|

Re: foldr on infinite list to decide prime number

Francesco Ariis
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
Reply | Threaded
Open this post in threaded view
|

Re: foldr on infinite list to decide prime number

Chul-Woong Yang
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
Reply | Threaded
Open this post in threaded view
|

Re: foldr on infinite list to decide prime number

Gesh
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
Reply | Threaded
Open this post in threaded view
|

Re: foldr on infinite list to decide prime number

Chul-Woong Yang
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
Reply | Threaded
Open this post in threaded view
|

Re: foldr on infinite list to decide prime number

derek riemer
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

  • 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!

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


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: foldr on infinite list to decide prime number

Francesco Ariis
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
Reply | Threaded
Open this post in threaded view
|

Re: foldr on infinite list to decide prime number

Chul-Woong Yang
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
Reply | Threaded
Open this post in threaded view
|

Re: foldr on infinite list to decide prime number

Thomas Koster
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