[Python-Dev] Re: PEP 276 Simple Iterator for ints

[Tim Peters]

[Skip Montanaro]
> The Haskell syntax has been bandied about on c.l.py for the past
> several days ...
>
> Haskell has a list constructor that maps pretty nicely onto
> Python's range() and xrange() functions:
>
>     [ exp1 [, exp2] .. [exp3] ]

The mapping isn't so nice -- range/xrange are great when the argument is
len(sequence), but stuff like range(len(n)-1, -1, -1) is error-prone.  Write
an array merge sort in Python and count the off-by-2**i errors <wink>.

> Since Haskell is lazy in its evaluation, infinite sequences can be
> constructed easily:
>
>     [ 0 .. ]                    # all natural numbers

In practice I think that's more often written:

    [0, 1 ..]

but I've seen both.  The [exp ..] form is more common when "exp" is an
expression instead of a literal (presumably because writing [exp, exp+1 ..]
then is more of a PITA).

> More common usage in Python would be something like
>
>     [ 0 .. 5 ]                  # [0, 1, 2, 3, 4, 5]
>
> or
>
>     [ 0, 3 .. 27 ]              # xrange(0, 28, 3)
>
> I believe (Tim can correct me if I'm wrong), but when you use these
> constructors to build finite sequences, they are closed at both ends,
> just as Python lists, and unlike [x]range(),

Yes, finite flavors are closed at both ends; note that can include empty
cases, like:

    [10 .. 0]
and
    [10, 11 .. 0]

> hence the different endpoints in the last example.  This seems to be a
> sticking point for people on c.l.py who see the lack of complete
> equivalence with [x]range as a problem.

If they were trivially equivalent to range/xrange, why bother <0.5 wink>?
Note that David Eppstein kicked off this round via searching for a cleaner
notation for integer sequence to use in his classroom lectures and handouts
(in which Python is used as a pseudo-language, not a real one -- and that
his students grasp [i, j ..] at once is the important point for him).

> I see them as (effectively) list constructors, and expect them to be
> closed at both ends.

Ya, and I think it's impossible not to see them that way.  IIRC, someone
once had the hideous suggestion of doing something like .. to mean semi-open
and ... to mean closed.

> ...
> I see a few advantages to this list constructor over [x]range():
>
>     * I think it would be a bit easier to explain to new users than
>       range.
>
>       I think most people have seen sequences in math like
>
>           [ x , x , ... , x  ]
>              1   2         n
>
>       and would thus find the notation familiar.  Admittedly, [x]range()
>       isn't that difficult, however.

If what you're *thinking* is i, j .. k, the transformation to an equivalent
range() isn't trivial; e.g., if j > i is known,

    range(i, k+1, j-i)

does the trick except when k == sys.maxint and/or j-i overflows; but in any
case it's simply not what you're *thinking*.


>     * It would expose potentially significant optimizations that
>       can't be made today by eliminating the attribute lookup and
>       function call to range, and thus getting rid of that little bit
>       of dynamism nobody ever uses anyway.

As I said last time this went around, I doubt the optimizations are
significant:  loop overhead is generally at worst a handful-of-percent thing
in real programs, and the cost of one global lookup+call per entire loop
(not per loop *trip*) isn't even measurable outside contrived examples.

>     * I think we could easily extend the notation to build sequences of
>       other basic types: floats and single-character strings being the
>       most obvious:
>
>           [ "a", "c" .. "z"]
>
>           [ 0.0, 0.1 .. 2*math.pi ]

-1 on floats:  unless floats are rationals, it's ill-defined, and like it or
not users are better off coding float steps themselves so they explicitly
control the rounding errors in ways best for their apps.  (BTW, repeated
addition is almost exactly the worst thing to do for fp sequences; doing
starting_value + iteration_ordinal * step_value on each trip is usually much
better behaved for floats.)

Note that any Enum type in Haskell can use this notation.  The four
syntactic forms map to Enum methods like so:

   [e1 ..]        <-> enumFrom       e1
   [e1, e2 ..]    <-> enumFromThen   e1 e2
   [e1 .. e3]     <-> enumFromTo     e1 e3
   [e1, e2 .. e3] <-> enumFromThenTo e1 e2 e3

> Python already has a "..." operator, so I would propose that be
> used instead of Haskell's "..".

Certainly a better idea than using "()" <wink>.