Negative nth index

Negative nth index

[Anand Tamariya]

[-- Attachment #1: Type: text/plain, Size: 71 bytes --]

Should negative index for nth be valid? e.g.
(nth -1 '(1 2)) returns 1

[-- Attachment #2: Type: text/html, Size: 137 bytes --]

Re: Negative nth index

[Eli Zaretskii]

> From: Anand Tamariya <atamariya@gmail.com>
> Date: Sun, 22 Dec 2024 11:13:18 +0530
> 
> Should negative index for nth be valid? e.g. 
> (nth -1 '(1 2)) returns 1

What does this do in other Lisps?

Re: Negative nth index

[Tassilo Horn]

Eli Zaretskii <eliz@gnu.org> writes:

>> Should negative index for nth be valid? e.g. 
>> (nth -1 '(1 2)) returns 1
>
> What does this do in other Lisps?

In CL, it errors (ditto for nthcdr with negative index).  Same for (nth
'(1 2 3) -1) in Clojure or (list-ref '(1 2 3) -1) in Scheme.

Bye,
Tassilo

Re: Negative nth index

[Andreas Schwab]

On Dez 22 2024, Anand Tamariya wrote:

> (nth -1 '(1 2)) returns 1

What would (nth -1 '#1=(1 2 . #1#)) return?

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: Negative nth index

[Stefan Kangas]

Tassilo Horn <tsdh@gnu.org> writes:

> Eli Zaretskii <eliz@gnu.org> writes:
>
>>> Should negative index for nth be valid? e.g.
>>> (nth -1 '(1 2)) returns 1
>>
>> What does this do in other Lisps?
>
> In CL, it errors (ditto for nthcdr with negative index).  Same for (nth
> '(1 2 3) -1) in Clojure or (list-ref '(1 2 3) -1) in Scheme.

Stefan Monnier, any comments here?

Re: Negative nth index

[Stefan Monnier]

>>>> Should negative index for nth be valid? e.g.
>>>> (nth -1 '(1 2)) returns 1

[ I'd make it return 2 otherwise you can't use it to return the
  last element.  ]

>>> What does this do in other Lisps?
>> In CL, it errors (ditto for nthcdr with negative index).  Same for (nth
>> '(1 2 3) -1) in Clojure or (list-ref '(1 2 3) -1) in Scheme.
> Stefan Monnier, any comments here?

I don't see a strong argument in favor of making it index from the end
rather than signal an error.  What would the implementation look like?
Would it be significantly more efficient than doing it "by hand" e.g.:

    (let ((l (length X)))
      (nth (if (< i 0) (- l i) i) X))


- Stefan

Re: Negative nth index

[Teemu Likonen]

[-- Attachment #1: Type: text/plain, Size: 547 bytes --]

* 2024-12-24 00:11:26-0500, Stefan Monnier wrote:

> I don't see a strong argument in favor of making it index from the end
> rather than signal an error.  What would the implementation look like?
> Would it be significantly more efficient than doing it "by hand" e.g.:
>
>     (let ((l (length X)))
>       (nth (if (< i 0) (- l i) i) X))

First test if index (i) is negative and only then run the needed
"length" etc.

-- 
/// Teemu Likonen - .-.. https://www.iki.fi/tlikonen/
// OpenPGP: 6965F03973F0D4CA22B9410F0F2CAE0E07608462

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 251 bytes --]

Re: Negative nth index

[Thierry Volpiatto]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>>>> Should negative index for nth be valid? e.g.
>>>>> (nth -1 '(1 2)) returns 1
>
> [ I'd make it return 2 otherwise you can't use it to return the
>   last element.  ]
>
>>>> What does this do in other Lisps?
>>> In CL, it errors (ditto for nthcdr with negative index).  Same for (nth
>>> '(1 2 3) -1) in Clojure or (list-ref '(1 2 3) -1) in Scheme.
>> Stefan Monnier, any comments here?
>
> I don't see a strong argument in favor of making it index from the end
> rather than signal an error.  What would the implementation look like?
> Would it be significantly more efficient than doing it "by hand" e.g.:
>
>     (let ((l (length X)))
>       (nth (if (< i 0) (- l i) i) X))

I guess you meant (+ l i) no?

>
> - Stefan
>
>
>

-- 
Thierry

Re: Negative nth index

[Philip Kaludercic]

Thierry Volpiatto <thievol@posteo.net> writes:

> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>
>>>>>> Should negative index for nth be valid? e.g.
>>>>>> (nth -1 '(1 2)) returns 1
>>
>> [ I'd make it return 2 otherwise you can't use it to return the
>>   last element.  ]
>>
>>>>> What does this do in other Lisps?
>>>> In CL, it errors (ditto for nthcdr with negative index).  Same for (nth
>>>> '(1 2 3) -1) in Clojure or (list-ref '(1 2 3) -1) in Scheme.
>>> Stefan Monnier, any comments here?
>>
>> I don't see a strong argument in favor of making it index from the end
>> rather than signal an error.  What would the implementation look like?
>> Would it be significantly more efficient than doing it "by hand" e.g.:
>>
>>     (let ((l (length X)))
>>       (nth (if (< i 0) (- l i) i) X))
>
> I guess you meant (+ l i) no?

And do we need a check to see if (< (- i) (length l)),  otherwise

  (nth -10 '(1 2 3))

could still return a non-nil value, while

  (nth 10 '(1 2 3))

just returns nil.

Using (mod i l) would also be too DWIM-y, right?

>>
>> - Stefan
>>
>>
>>

Re: Negative nth index

[Stefan Monnier]

> I don't see a strong argument in favor of making it index from the end
> rather than signal an error.  What would the implementation look like?
> Would it be significantly more efficient than doing it "by hand" e.g.:
>
>     (let ((l (length X)))
>       (nth (if (< i 0) (- l i) i) X))

AFAICT so far people were only able to fix my code but not answer my
question, which suggests the answer is no, which would be a good
argument in favor of staying with the current behavior: the change
wouldn't save us from going down the list twice.


        Stefan

Re: Negative nth index

[Sebastián Monía]

Hello,

Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>>>> Should negative index for nth be valid? e.g.
>>>>> (nth -1 '(1 2)) returns 1
>
> [ I'd make it return 2 otherwise you can't use it to return the
>   last element.  ]
>
>>>> What does this do in other Lisps?
>>> In CL, it errors (ditto for nthcdr with negative index).  Same for (nth
>>> '(1 2 3) -1) in Clojure or (list-ref '(1 2 3) -1) in Scheme.

And for this reason I _would not_ expect it to work with negative
numbers in Elisp.

> I don't see a strong argument in favor of making it index from the end
> rather than signal an error.  What would the implementation look like?

This is "modern"? behaviour that I would expect from seq-elt, because it
is the newest, bell and whistles library.

I have a feeling that keeping `nth' more limited for reasons of
tradition is silly, but...it feels right.

Regards,
Seb

-- 
Sebastián Monía
https://site.sebasmonia.com/

Re: Negative nth index

[Pip Cet via Emacs development discussions.]

"Stefan Monnier" <monnier@iro.umontreal.ca> writes:

>>>>> Should negative index for nth be valid? e.g.
>>>>> (nth -1 '(1 2)) returns 1
>
> [ I'd make it return 2 otherwise you can't use it to return the
>   last element.  ]

I think the OP meant that (nth -1 '(1 2)) is 1 on current Emacs, which
is definitely unexpected.

> I don't see a strong argument in favor of making it index from the end
> rather than signal an error.  What would the implementation look like?

I agree, but the current implementation does not signal an error.  It
should, and I think that's what the suggestion was.

To me, (nth -1 list) means "I set list to be the cdr of x, now tell me
what x was", so the right answer is "I can't do that, so here's an error
and go fix your code".  It's perfectly analogous to (/ 0 0), which means
"I multiplied a number x by 0 and got 0.  Tell me what x was."

For circular lists, we could give a possible answer for x (just as we
could give a possible answer for x in the 0/0 example), by moving back
in the cycle, but it's not the only possible answer, so we shouldn't.

(For lists both proper and circular, we could also create a new cons
cell and return it, I guess).

Indexing from the end is even worse than defining 0/0 to be 17.

Pip

Re: Negative nth index

[Mattias Engdegård]

24 dec. 2024 kl. 22.33 skrev Pip Cet via Emacs development discussions. <emacs-devel@gnu.org>:

> I think the OP meant that (nth -1 '(1 2)) is 1 on current Emacs, which
> is definitely unexpected.

It's a straight consequence of (nth N L) = (car (nthcdr N L)).

>> I don't see a strong argument in favor of making it index from the end
>> rather than signal an error.  What would the implementation look like?
> 
> I agree, but the current implementation does not signal an error.  It
> should, and I think that's what the suggestion was.

It is true that signalling an error for negative arguments might catch some bugs but doing so would also risk breaking working code that relies on the current (well-defined) behaviour.

And there's not much performance to gain from it: while a good compiler might use it for value range propagation, as in

  (use (nth n lis))
  (if (< n 0) ...)  ; dead if nth signals on negative n

it doesn't really justify a change.

Re: Negative nth index

[Pip Cet via Emacs development discussions.]

Mattias Engdegård <mattias.engdegard@gmail.com> writes:

> 24 dec. 2024 kl. 22.33 skrev Pip Cet via Emacs development discussions. <emacs-devel@gnu.org>:
>
>> I think the OP meant that (nth -1 '(1 2)) is 1 on current Emacs, which
>> is definitely unexpected.
>
> It's a straight consequence of (nth N L) = (car (nthcdr N L)).

s/nth/nthcdr/g in my email, then.  Of course the two should behave
analogously, the question is whether they should both throw an error (my
opinion) or shouldn't.

(My apologies for actually writing about nthcdr but calling it nth in
the last mail).

>>> I don't see a strong argument in favor of making it index from the end
>>> rather than signal an error.  What would the implementation look like?
>>
>> I agree, but the current implementation does not signal an error.  It
>> should, and I think that's what the suggestion was.
>
> It is true that signalling an error for negative arguments might catch
> some bugs but doing so would also risk breaking working code that
> relies on the current (well-defined) behaviour.

If it were merely undocumented, I might agree, but the current behavior
doesn't match the documentation, because taking cdr -1 times is
obviously an impossible thing to do.

> And there's not much performance to gain from it

This isn't about performance.

Pip

Re: Negative nth index

[Mattias Engdegård]

25 dec. 2024 kl. 11.56 skrev Pip Cet <pipcet@protonmail.com>:

> s/nth/nthcdr/g in my email, then.  Of course the two should behave
> analogously, the question is whether they should both throw an error (my
> opinion) or shouldn't.

The behaviour of nthcdr for negative N is well-established and turns out to be somewhat useful in practice.

If compatibility with existing code were completely unimportant, I'd recommend that negative arguments cause nth to signal but not nthcdr. But it isn't, so I don't.

> If it were merely undocumented, I might agree, but the current behavior
> doesn't match the documentation,

Yes, the manual and doc strings could certainly be improved.

> because taking cdr -1 times is
> obviously an impossible thing to do.

Well now, we could define

 (nthcdr N L) = (cons nil (nthcdr (1+ N) L)

for N<0. (No, we shouldn't.)

> This isn't about performance.

Of course it's about performance. In some respect it always is!

Re: Negative nth index

[Pip Cet via Emacs development discussions.]

Mattias Engdegård <mattias.engdegard@gmail.com> writes:

> 25 dec. 2024 kl. 11.56 skrev Pip Cet <pipcet@protonmail.com>:
>
>> s/nth/nthcdr/g in my email, then.  Of course the two should behave
>> analogously, the question is whether they should both throw an error (my
>> opinion) or shouldn't.
>
> The behaviour of nthcdr for negative N is well-established and turns out to be somewhat useful in practice.

I didn't know that.  We specifically undocumented it in 2013, as it
turns out (3e6b67c9b7230bf10219082d9215d9617a33715e):

2013-08-13  Glenn Morris  <rgm@gnu.org>

	* lists.texi (List Elements):
	Undocument behavior of nth and nthcdr with n < 0.  (Bug#15059)

I agree with the statement in that bug thread: All hope is lost.  We
can't fix it and it is broken, and now we're stuck with permanent harm.
The only thing it's good for now is to serve as a cautionary tale.

>> If it were merely undocumented, I might agree, but the current behavior
>> doesn't match the documentation,
>
> Yes, the manual and doc strings could certainly be improved.

By reverting that commit?

>> because taking cdr -1 times is
>> obviously an impossible thing to do.
>
> Well now, we could define
>
>  (nthcdr N L) = (cons nil (nthcdr (1+ N) L)
>
> for N<0. (No, we shouldn't.)

As I said, that's defining 0/0 to be 17 because it's A solution to 0 * x
= 0.  We don't, because we want the unique solution.

>> This isn't about performance.
>
> Of course it's about performance. In some respect it always is!

In the spirit of contradicting in the strongest possible way, how about
we make it infloop?  It'd never return an unexpected value or throw an
unexpected error, then, and it matches the while (count--) x = Fcdr (x)
idea.

Pip

Re: Negative nth index

[Stefan Kangas]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>> In CL, it errors (ditto for nthcdr with negative index).  Same for (nth
>>> '(1 2 3) -1) in Clojure or (list-ref '(1 2 3) -1) in Scheme.
>> Stefan Monnier, any comments here?
>
> I don't see a strong argument in favor of making it index from the end
> rather than signal an error.

I'd make it signal an error like in CL, Clojure, and Scheme, but it
doesn't do that today, so the change would not be backwards-compatible.
So I'm not sure what to do here or how.

For reference, the current behavior is this:

    (nth -1 '(1 2 3))                     => 1
    (nth -2 '(1 2 3))                     => 1
    (nth -3 '(1 2 3))                     => 1
    (nth most-negative-fixnum '(1 2 3))   => 1

Re: Negative nth index

[Stefan Kangas]

Pip Cet <pipcet@protonmail.com> writes:

> I didn't know that.  We specifically undocumented it in 2013, as it
> turns out (3e6b67c9b7230bf10219082d9215d9617a33715e):
>
> 2013-08-13  Glenn Morris  <rgm@gnu.org>
>
> 	* lists.texi (List Elements):
> 	Undocument behavior of nth and nthcdr with n < 0.  (Bug#15059)
>
> I agree with the statement in that bug thread: All hope is lost.  We
> can't fix it and it is broken, and now we're stuck with permanent harm.
> The only thing it's good for now is to serve as a cautionary tale.

We could warn in the byte-compiler, at least for constant arguments (as
futile as that would be), or we could introduce a new runtime warning.

But I'm not exactly sure that it would be worth the trouble.

>>> If it were merely undocumented, I might agree, but the current behavior
>>> doesn't match the documentation,
>>
>> Yes, the manual and doc strings could certainly be improved.
>
> By reverting that commit?

Perhaps the least intrusive thing we could do is to document the current
behavior, and say that this is an unfortunate historical accident that
no Lisp program should ever rely on.