Clojure

range's behavior is inconsistent

Details

• Type: Defect
• Status: Closed
• Priority: Minor
• Resolution: Completed
• Affects Version/s: Release 1.1, Release 1.2, Release 1.3, Release 1.4, Release 1.5
• Fix Version/s:
• Component/s: None
• Labels:
• Patch:
Code and Test
• Approval:
Ok

Description

Problem statement: The current behavior of range is inconsistent. (range 0 9 0) has always produced (). (range 0 9 -1) has always produced (). (range 9 0 1) has always produced (). However, (range 9 0 0) produces (9 9 9 9 ...), and (range 0 0 0) produces '(0 0 0 0 ...)

Proposal: Make the behavior of range consistent when using a step of 0 to make it produce an empty list.

Please see attached code and patch.

Attachments

1. inconsistent_range_fix.diff
20/Jul/12 5:10 PM
2 kB
Devin Walters

Activity

Hide
Mike Anderson added a comment -

Agree it is good to fix the inconsistency, but I think an infinite sequence of zeros is the correct result, as implied by the current docstring definition.

It's also mathematically cleanest: range should produce an arithmetic progression until the end value is equalled or exceeded.

Empty lists only seem to make sense as a return value when start >= end.

Show
Mike Anderson added a comment - Agree it is good to fix the inconsistency, but I think an infinite sequence of zeros is the correct result, as implied by the current docstring definition. It's also mathematically cleanest: range should produce an arithmetic progression until the end value is equalled or exceeded. Empty lists only seem to make sense as a return value when start >= end.
Hide
Devin Walters added a comment - - edited

Hi Mike,

Could you explain how you think the docstring definition implies this behavior? Maybe I'm missing something, but I was surprised. For instance, in the case of (range 3 9 0), if start were truly inclusive as the docstring says, the result would be (3), not ().

You mentioned that you think the infinite sequence of 0's is consistent and in keeping with the definition of range. I'm not sure I agree. (0,0] is an empty set of length zero, and [0,0) is an empty set of length zero.

You state that empty list only makes sense for start >= end, except this is not the current behavior. Could you help me understand what you believe the appropriate behavior would be in each of the following three cases? (range 0 10 0), (range 10 0 0), and (range 0 0 0)?

A few options to consider:
1) Fix the docstring to reflect the actual behavior of range.
2) Handle the case of (range 9 3 0) => (9 9 9 ...) to make it consistent with the behavior of (range 3 9 0) => ()
3) Stop allowing a step of zero altogether.

Editing to Add (Note: I don't think the way someone else did something is always the right way, just wanted to do some digging on how other people have handled this in the past):
http://docs.python.org/library/functions.html#range (0 step returns ValueError)
http://www2.tcl.tk/10797 (range returns empty list for a zero step)
http://www.scala-lang.org/api/2.7.7/scala/Range.html (zero step is not allowed)

Show
Devin Walters added a comment - - edited Hi Mike, Could you explain how you think the docstring definition implies this behavior? Maybe I'm missing something, but I was surprised. For instance, in the case of (range 3 9 0), if start were truly inclusive as the docstring says, the result would be (3), not (). You mentioned that you think the infinite sequence of 0's is consistent and in keeping with the definition of range. I'm not sure I agree. (0,0] is an empty set of length zero, and [0,0) is an empty set of length zero. You state that empty list only makes sense for start >= end, except this is not the current behavior. Could you help me understand what you believe the appropriate behavior would be in each of the following three cases? (range 0 10 0), (range 10 0 0), and (range 0 0 0)? A few options to consider: 1) Fix the docstring to reflect the actual behavior of range. 2) Handle the case of (range 9 3 0) => (9 9 9 ...) to make it consistent with the behavior of (range 3 9 0) => () 3) Stop allowing a step of zero altogether. Editing to Add (Note: I don't think the way someone else did something is always the right way, just wanted to do some digging on how other people have handled this in the past): http://docs.python.org/library/functions.html#range (0 step returns ValueError) http://www2.tcl.tk/10797 (range returns empty list for a zero step) http://www.scala-lang.org/api/2.7.7/scala/Range.html (zero step is not allowed)
Hide
Dimitrios Piliouras added a comment -

It does make sense NOT to allow a step of zero (at least to me)... I wasn't going to say anything about this but if other popular languages do not allow 0, then I guess it makes more sense than I originally gave myself credit for... However, if we want to be mathematically correct then the answer would be to return an infinte seq with the start value like below. After all, what is a step of 0? does it make any difference how many steps you take if with every step you cover 0 distance? obviously not...you start from x and you stay at x forever...we do have repeat for this sort of thing though...

(take 5 (range 3 9 0)) => (3 3 3 3 3)

+1 for not allowing 0 step

Show
Dimitrios Piliouras added a comment - It does make sense NOT to allow a step of zero (at least to me)... I wasn't going to say anything about this but if other popular languages do not allow 0, then I guess it makes more sense than I originally gave myself credit for... However, if we want to be mathematically correct then the answer would be to return an infinte seq with the start value like below. After all, what is a step of 0? does it make any difference how many steps you take if with every step you cover 0 distance? obviously not...you start from x and you stay at x forever...we do have repeat for this sort of thing though... (take 5 (range 3 9 0)) => (3 3 3 3 3) +1 for not allowing 0 step
Hide
Mike Anderson added a comment -

@Devin quite simple: a lazy sequence of nums starting from x with step 0.0 until it reaches an end value of y (where y > x) is an infinite sequence of x.

Consider the case where start is 0 and end is infinity (the default), you would expect sequences to go as follows:

step +2 : 0 2 4 6 8....
step +1 : 0 1 2 3 4....
step +0 : 0 0 0 0 0....

It would be inconsistent to make 0 a special case, all of these are valid arithmetic progressions. And all of these are consistent with the current docstring.

If you make 0 a special case, then people will need to write special case code to handle it. Consider the code to create a multiplication table for example:

(for [x (range 10)]
(take 10 (range 0 Long/MAX_VALUE x)))

This works fine if you produce an infinite sequence of zeros for step 0, but fails if you create an empty list as a special case for step 0.

As a related issue, I'd personally also favour negative step sizes also producing an infinite sequence. If we don't want to allow this though, then at least the docstring should be changed to say "a lazy seq of non-decreasing nums" and a negative step should throw an error.

Show
Mike Anderson added a comment - @Devin quite simple: a lazy sequence of nums starting from x with step 0.0 until it reaches an end value of y (where y > x) is an infinite sequence of x. Consider the case where start is 0 and end is infinity (the default), you would expect sequences to go as follows: step +2 : 0 2 4 6 8.... step +1 : 0 1 2 3 4.... step +0 : 0 0 0 0 0.... It would be inconsistent to make 0 a special case, all of these are valid arithmetic progressions. And all of these are consistent with the current docstring. If you make 0 a special case, then people will need to write special case code to handle it. Consider the code to create a multiplication table for example: (for [x (range 10)] (take 10 (range 0 Long/MAX_VALUE x))) This works fine if you produce an infinite sequence of zeros for step 0, but fails if you create an empty list as a special case for step 0. As a related issue, I'd personally also favour negative step sizes also producing an infinite sequence. If we don't want to allow this though, then at least the docstring should be changed to say "a lazy seq of non-decreasing nums" and a negative step should throw an error.
Hide
Devin Walters added a comment -

Carrying over a message from the clojure-dev list by Stuart Sierra:

• I called the ticket a defect. Does that seem reasonable?

yes

• Does anyone actually use the 0 step behavior in their programs?

not if they have any sense

• Has anyone been bitten by this in the past?

not me

• Is this behavior intentional for some historical reason I don't know about or understand?

I doubt it.

• Has this been brought up before? I couldn't find any reference to it via Google.

Not that I know of.

• Are there performance implications to my patch?

I doubt it. Lazy seqs are not ideal for high-performance code anyway.

• Am I addressing a symptom rather than the problem?

I think the problem is that the result of `range` with a step of 0 was never specified. Don't assume that the tests are specifications. Many of the tests in Clojure were written by over-eager volunteers who defined the tests based on whatever the behavior happened to be. The only specification from the language designer is the docstring. By my reading, that means that `range` with a step of 0 should return an infinite seq of the start value, unless the start and end values are equal.

-S

Show
Devin Walters added a comment - Carrying over a message from the clojure-dev list by Stuart Sierra:
• I called the ticket a defect. Does that seem reasonable?
yes
• Does anyone actually use the 0 step behavior in their programs?
not if they have any sense
• Has anyone been bitten by this in the past?
not me
• Is this behavior intentional for some historical reason I don't know about or understand?
I doubt it.
• Has this been brought up before? I couldn't find any reference to it via Google.
Not that I know of.
• Are there performance implications to my patch?
I doubt it. Lazy seqs are not ideal for high-performance code anyway.
• Am I addressing a symptom rather than the problem?
I think the problem is that the result of `range` with a step of 0 was never specified. Don't assume that the tests are specifications. Many of the tests in Clojure were written by over-eager volunteers who defined the tests based on whatever the behavior happened to be. The only specification from the language designer is the docstring. By my reading, that means that `range` with a step of 0 should return an infinite seq of the start value, unless the start and end values are equal. -S
Hide
Devin Walters added a comment -

Carrying over a message by Michal Marczyk:

With a negative step, the comparison is reversed, so that e.g.

(range 3 0 -1)

evaluates to

(3 2 1)

I think this is the useful behaviour; the docstring should perhaps be

Agreed on zero step.

Cheers,
Michał

Show
Devin Walters added a comment - Carrying over a message by Michal Marczyk: With a negative step, the comparison is reversed, so that e.g. (range 3 0 -1) evaluates to (3 2 1) I think this is the useful behaviour; the docstring should perhaps be adjusted to match it. Agreed on zero step. Cheers, Michał
Hide
Devin Walters added a comment - - edited

Adding a new patch after hearing comments. This patch makes (range 9 3 0) => (9 9 9 9 ...), (range 3 9 0) => (3 3 3 3 ...), and () will be returned when (= start end). Also updated the docstring.

Show
Devin Walters added a comment - - edited Adding a new patch after hearing comments. This patch makes (range 9 3 0) => (9 9 9 9 ...), (range 3 9 0) => (3 3 3 3 ...), and () will be returned when (= start end). Also updated the docstring.
Hide
Timothy Baldridge added a comment -

Marking as vetted

Show
Timothy Baldridge added a comment - Marking as vetted
Hide
Timothy Baldridge added a comment -

Patch applies cleanly. We've discussed this issue to death (for as simple as it is). I think it's time to mark it as screened.

Show
Timothy Baldridge added a comment - Patch applies cleanly. We've discussed this issue to death (for as simple as it is). I think it's time to mark it as screened.
Hide
Timothy Baldridge added a comment -

For some reason I'm not allowed to edit the attachments list. When you apply the patch, please apply inconsistent_range_fix.diff as that is the most recent version of the fix.

Show
Timothy Baldridge added a comment - For some reason I'm not allowed to edit the attachments list. When you apply the patch, please apply inconsistent_range_fix.diff as that is the most recent version of the fix.
Hide
Rich Hickey added a comment -

As someone who has to read these tickets, I'd really appreciate it if you could keep the description up to date and accurate, with examples of the current and intended behavior and the strategy to be used in fixing. I can't follow every thread to see what the latest thinking is, especially on a patch like this where the original mission was changed.

Thanks

Show
Rich Hickey added a comment - As someone who has to read these tickets, I'd really appreciate it if you could keep the description up to date and accurate, with examples of the current and intended behavior and the strategy to be used in fixing. I can't follow every thread to see what the latest thinking is, especially on a patch like this where the original mission was changed. Thanks
Hide
Devin Walters added a comment -

@Tim: I've removed the other attachments.

@Rich: Understood. I will update the description this evening.

Show
Devin Walters added a comment - @Tim: I've removed the other attachments. @Rich: Understood. I will update the description this evening.

Vote (0)
Watch (2)

• Created:
Updated:
Resolved: