[] \\ [1..] diverges - intended? - Haskell-Cafe - Haskell.org

newer
Munich Haskell Meeting

[] \\ [1..] diverges - intended?

older
New Functional Programming Job...

Niklas Hambüchen

26 Jul 2014 26 Jul '14

7:39 p.m.

Hi, I just noticed that import Data.List [] \\ [1..] diverges, although technically it doesn't have to (the docs suggest to me that it could just be [], and a non-diverging implementation is possible). Same for [1,2] \\ [1..] of course. Was this intended?

Reply

Sign in to reply online Use email software

Show replies by date

Henk-Jan van Tuyl

26 Jul 26 Jul

8:55 p.m.

On Sat, 26 Jul 2014 21:39:01 +0200, Niklas Hambüchen wrote:

Hi,

I just noticed that

import Data.List [] \\ [1..]

diverges, although technically it doesn't have to (the docs suggest to me that it could just be [], and a non-diverging implementation is possible).

Same for [1,2] \\ [1..] of course.

You can define (\\) as follows, terminating in case of the samples you gave: (\\) :: (Eq a) => [a] -> [a] -> [a] (\\) [] _ = [] (\\) _ [] = [] (\\) xs (y : ys) = delete y xs \\ ys but this will not terminate in cases like: [0] \\ [1..] I don't think there is a way to get this terminating for all cases. Regards, Henk-Jan van Tuyl -- Folding@home What if you could share your unused computer power to help find a cure? In just 5 minutes you can join the world's biggest networked computer and get us closer sooner. Watch the video. http://folding.stanford.edu/ http://Van.Tuyl.eu/ http://members.chello.nl/hjgtuyl/tourdemonad.html Haskell programming --

Reply

Sign in to reply online Use email software

Niklas Hambüchen

10:03 p.m.

On 26/07/14 22:55, Henk-Jan van Tuyl wrote:

You can define (\\) as follows, terminating in case of the samples you gave:

Yes, that's what I mean. Why is it not defined like that?

but this will not terminate in cases like: [0] \\ [1..]

Yes, this of course not terminate because it has to search for a 0 in the second list, which takes forever. But my question was about the first case: Was it intended (or is it specified) that (\\) cannot work on infinite lists? Otherwise maybe your implementation should replace the current one?

Reply

Sign in to reply online Use email software

Daniil Frumin

28 Jul 28 Jul

2:10 p.m.

Hi! On Sun, Jul 27, 2014 at 12:55 AM, Henk-Jan van Tuyl wrote:

On Sat, 26 Jul 2014 21:39:01 +0200, Niklas Hambüchen wrote:

...
Hi,

I just noticed that

import Data.List [] \\ [1..]

diverges, although technically it doesn't have to (the docs suggest to me that it could just be [], and a non-diverging implementation is possible).

Same for [1,2] \\ [1..] of course.

You can define (\\) as follows, terminating in case of the samples you gave:

(\\) :: (Eq a) => [a] -> [a] -> [a] (\\) [] _ = [] (\\) _ [] = [] (\\) xs (y : ys) = delete y xs \\ ys

Is this actually correct? Shouldn't the second line be (\\) x [] = x ?

but this will not terminate in cases like: [0] \\ [1..]

I don't think there is a way to get this terminating for all cases.

Regards, Henk-Jan van Tuyl

-- Folding@home What if you could share your unused computer power to help find a cure? In just 5 minutes you can join the world's biggest networked computer and get us closer sooner. Watch the video. http://folding.stanford.edu/

http://Van.Tuyl.eu/ http://members.chello.nl/hjgtuyl/tourdemonad.html Haskell programming --

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Sincerely yours, -- Daniil

Reply

Sign in to reply online Use email software

Henk-Jan van Tuyl

4:31 p.m.

On Mon, 28 Jul 2014 16:10:38 +0200, Daniil Frumin wrote:

Hi!

On Sun, Jul 27, 2014 at 12:55 AM, Henk-Jan van Tuyl wrote:

...
(\\) :: (Eq a) => [a] -> [a] -> [a] (\\) [] _ = [] (\\) _ [] = [] (\\) xs (y : ys) = delete y xs \\ ys

Is this actually correct? Shouldn't the second line be

(\\) x [] = x

?

You are right; as it was just to prove a point I didn't spend enough time reviewing/testing it. My life would have been much easier if I had chosen an area of expertise where showing my diploma was enough to prove that I am right. Regards, Henk-Jan van Tuyl -- Folding@home What if you could share your unused computer power to help find a cure? In just 5 minutes you can join the world's biggest networked computer and get us closer sooner. Watch the video. http://folding.stanford.edu/ http://Van.Tuyl.eu/ http://members.chello.nl/hjgtuyl/tourdemonad.html Haskell programming --

Reply

Sign in to reply online Use email software

4010

Age (days ago)

4012

Last active (days ago)

Download

4 comments

3 participants

tags

participants (3)

Daniil Frumin
Henk-Jan van Tuyl
Niklas Hambüchen