Niklas Hambüchen | 26 Jul 21:39 2014

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

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?
Henk-Jan van Tuyl | 26 Jul 22:55 2014
Picon

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

On Sat, 26 Jul 2014 21:39:01 +0200, Niklas Hambüchen <mail <at> nh2.me> 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,
(Continue reading)

Niklas Hambüchen | 27 Jul 00:03 2014

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

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?
Daniil Frumin | 28 Jul 16:10 2014
Picon

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

Hi!

On Sun, Jul 27, 2014 at 12:55 AM, Henk-Jan van Tuyl <hjgtuyl <at> chello.nl> wrote:
> On Sat, 26 Jul 2014 21:39:01 +0200, Niklas Hambüchen <mail <at> nh2.me> 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

(Continue reading)

Henk-Jan van Tuyl | 28 Jul 18:31 2014
Picon

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

On Mon, 28 Jul 2014 16:10:38 +0200, Daniil Frumin <difrumin <at> gmail.com>  
wrote:

> Hi!
>
> On Sun, Jul 27, 2014 at 12:55 AM, Henk-Jan van Tuyl <hjgtuyl <at> chello.nl>  
> 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 <at> home
What if you could share your unused computer power to help find a cure? In  
(Continue reading)


Gmane