Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: foldr on infinite list to decide prime number (Gesh)
2. Re: foldr on infinite list to decide prime number
(Chul-Woong Yang)
3. Re: foldr on infinite list to decide prime number (derek riemer)
4. Re: foldr with short circuit and accumulator (Chul-Woong Yang)
5. Re: foldr with short circuit and accumulator (Chul-Woong Yang)
6. Re: foldr on infinite list to decide prime number
(Chul-Woong Yang)
----------------------------------------------------------------------
Message: 1
Date: Tue, 02 Feb 2016 15:33:14 +0200
From: Gesh <g...@gesh.uni.cx>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] foldr on infinite list to decide
prime number
Message-ID: <e1c434b6-9f74-465a-8b4d-1f63a4c68...@gesh.uni.cx>
Content-Type: text/plain; charset=UTF-8
On February 2, 2016 3:36:03 AM GMT+02:00, Chul-Woong Yang
<cwy...@aranetworks.com> 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 <cwy...@aranetworks.com>:
>
>> 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
>Beginners@haskell.org
>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
------------------------------
Message: 2
Date: Wed, 3 Feb 2016 09:36:00 +0900
From: Chul-Woong Yang <cwy...@aranetworks.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] foldr on infinite list to decide
prime number
Message-ID:
<CALmycjqAdh9gNVQGZfP3Rj=Be1KTv46UtmGLMjHgnpf0+UQ=k...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Thank you for kind response.
See you in another thread. :-)
2016-02-02 22:33 GMT+09:00 Gesh <g...@gesh.uni.cx>:
> On February 2, 2016 3:36:03 AM GMT+02:00, Chul-Woong Yang
> <cwy...@aranetworks.com> 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 <cwy...@aranetworks.com>:
>>
>>> 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
>>Beginners@haskell.org
>>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
> Beginners@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
Message: 3
Date: Tue, 2 Feb 2016 17:52:08 -0700
From: derek riemer <driemer.rie...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] foldr on infinite list to decide
prime number
Message-ID: <56b14f38.6070...@gmail.com>
Content-Type: text/plain; charset="windows-1252"; Format="flowed"
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.rie...@colorado.edu <mailto:derek.rie...@colorado.edu>
Phone: (303) 906-2194
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160202/2d2d759f/attachment-0001.html>
------------------------------
Message: 4
Date: Wed, 3 Feb 2016 09:53:13 +0900
From: Chul-Woong Yang <cwy...@aranetworks.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] foldr with short circuit and
accumulator
Message-ID:
<calmycjoqtpvhg53om4phwbhm+zsgxrqsmwrfpbzpbjzb6et...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Thank you for introducing mind-blowing ssfold, which has step function
with three argument:
> ssfold p f a0 xs = foldr (\x xs a -> if p a then a else xs (f a x)) id xs a0
Having spent last night, I've yet to got it. What a slow person!
Regards,
2016-02-02 18:03 GMT+09:00 KwangYul Seo <kwangyul....@gmail.com>:
> Hi,
>
> Implementing a short-circuiting fold was already discussed in the
> haskell-cafe mailing list.
>
> https://mail.haskell.org/pipermail/haskell-cafe/2007-April/024171.html
>
>
> On Tue, Feb 2, 2016 at 4:15 PM, Chul-Woong Yang <cwy...@aranetworks.com>
> wrote:
>>
>> Hi, all.
>>
>> Can it be possible to do fold with short circuit and accumulator both?
>> For example, can we find an element which is same value to adjacent one?
>>
>> findAdjacent [1,2..n, n, n+1, n+2.......] => n
>> \__very long__/
>>
>> Though there can be many ways to do it, Can we do it with fold[r|l]?
>>
>> I'll be happy to receive any comments.
>>
>> Chul-Woong
>> _______________________________________________
>> Beginners mailing list
>> Beginners@haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
------------------------------
Message: 5
Date: Wed, 3 Feb 2016 10:23:46 +0900
From: Chul-Woong Yang <cwy...@aranetworks.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] foldr with short circuit and
accumulator
Message-ID:
<CALmycjpj9v9oFQV8ti7RcCFw7WCC=wdm2xrqdxs1ixsma0j...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Hi,
Thanks for your reply. I've done zip'ing in those kinds of problem, also.
I think it'd be better if we can do it without zip'ing, with folding only.
With help of KwangYul Seo, I know now that short-circuiting with fold
is possible,
and I made ssfold version of findAdjacent:
-- Spencer Janssen's ssfold, from haskell-cafe
ssfold p f a0 xs = foldr (\x xs a -> if p a then a else xs (f a x)) id xs a0
findAdjacent :: [Int] -> Maybe Int
findAdjacent = snd . ssfold (uncurry const) step (False, Nothing)
where step acc@(True, _) _ = acc
step (False, last) x = (if Just x == last then True else False, Just x)
findAdjacent $ [1..10000] ++ [10000..]
==> 10000
It might be overkill for finding adjacent entry. It's better to use zip'ing.
But I think ssfold can be useful in other cases.
Any comments will be welcomed.
Regards,
Chul-Woong
2016-02-02 17:47 GMT+09:00 Theodore Lief Gannon <tan...@gmail.com>:
> If you mean is there any f and z for which this can be done with only "foldr
> f z xs", I believe the answer is no. If you don't mind extra parts, though:
>
> findAdjacent :: (Eq a) => [a] -> Maybe a
> findAdjacent xs = foldr f Nothing $ zip xs ps
> where
> ps = zipWith (==) (tail xs) xs
> f (x,p) next = if p then Just x else next
>
>
> On Mon, Feb 1, 2016 at 11:15 PM, Chul-Woong Yang <cwy...@aranetworks.com>
> wrote:
>>
>> Hi, all.
>>
>> Can it be possible to do fold with short circuit and accumulator both?
>> For example, can we find an element which is same value to adjacent one?
>>
>> findAdjacent [1,2..n, n, n+1, n+2.......] => n
>> \__very long__/
>>
>> Though there can be many ways to do it, Can we do it with fold[r|l]?
>>
>> I'll be happy to receive any comments.
>>
>> Chul-Woong
>> _______________________________________________
>> Beginners mailing list
>> Beginners@haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
------------------------------
Message: 6
Date: Wed, 3 Feb 2016 10:56:29 +0900
From: Chul-Woong Yang <cwy...@aranetworks.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] foldr on infinite list to decide
prime number
Message-ID:
<CALmycjrJfwpAXtsHfVS8=WAk_qmQutdBiVu=kxqqsswtnmc...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
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.rie...@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@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.rie...@colorado.edu
> Phone: (303) 906-2194
>
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 92, Issue 4
****************************************
