Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Nick Coghlan]

On 23 November 2017 at 17:13, Grant Jenks  wrote:

> And it will work! The heap algorithm is exposed through a high-level
> functional interface so that you can take advantage of duck-typing. This is
> an important Python feature.
>

Nobody is proposing taking the functional interface away (just as nobody is
proposing to take the bisect module away).

Instead, the argument is:

- the heapq functions need to be combined with concrete storage to be useful
- a simple wrapper class that combines them with a given list (or other
mutable sequence) is short and easy to maintain
- such a wrapper class is also useful in its own right for basic heap use
cases
- so let's provide one in the collections module

The potential arguments against that are:

- this means yet-another-data-type in the collections module, so it will
make the collections module harder to learn
- people will be confused as to whether they should use collections.Heap or
the heapq functions

The risks of both of those outcomes seem low, since the main current source
of confusion appears to be folks looking for a concrete "Heap" container
type, and being surprised when they get told they either need to be build a
DIY one from a list + the heapq functions, or else install a 3rd party
dependency to get a preassembled one.

Cheers,
Nick.

-- 
Nick Coghlan   |   ncogh...@gmail.com   |   Brisbane, Australia
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Greg Ewing]

Grant Jenks wrote:
The heap algorithm is exposed through a high-level 
functional interface so that you can take advantage of duck-typing.


This would also be true of a HeapWrapper class that wrapped
an existing sequence.

There's a difference between the heap functions and sorted().
The latter is just a single function that does its job and
returns a result. But the heap interface is a collection of
functions that have to be used together in the right way
to maintain the heap invariants. That suggests some
encapsulation is in order.

--
Greg
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Grant Jenks]

On Wed, Nov 22, 2017 at 9:22 PM, bunslow  wrote:

> Something *should* be object oriented with the functions in question all
> operate on the same data type, and in particular, those functions/verbs
> *are only well defined for that type*.
>

But here you are missing something that I think is important. These
functions are valid on *any* data type that has the methods of a mutable
sequence and has had heapq.heapify called on it. This is part of the
brilliance of heapq.

Suppose we wanted to create a list-like data-type backed by a filesystem or
database. I have done exactly such a thing like:

from collections import MutableSequence

class MyFileSystemList(MutableSequence): ...

data = MyFileSystemList('dir-path')

heapq.heapify(data)

heapq.heappush(data, 'text')

And it will work! The heap algorithm is exposed through a high-level
functional interface so that you can take advantage of duck-typing. This is
an important Python feature.

heapq.heappush(list-not-heap, item) is perfectly valid code in the current
> interface, but doesn't make any sense at all. And list.sort is *not*
> function based, it's an object oriented method. sorted() provides the same
> functionality for other types, given that it's a well defined function for
> a wide variety of sequences (unlike heappush). (list.sort is a method
> because unlike sorted(), it operates inplace, and is thus only meaningful
> for mutable, "complete" (all in memory, not "lazy") sequences -- i.e., a
> list.)
>

Personally, I find it irritating that list.sort will not similarly work
until I inherit from list. I would prefer if it worked on mutable
sequences. But regardless, if you inherit from "list", define all your own
methods to store data in a file system, database, whatever then "list.sort"
will work just fine as if it were a function:

class MyFileSystemList(list): ...  # Define methods to read/write from file
system.

data = MyFileSystemList()

list.sort(data)

So it's not the case that list.sort is a method and must only be used as
such. Rather, list.sort captures the algorithm known as sorting and works
on any mutable sequence (with the unfortunate additional requirement that
it inherits from list).

I've never used bisect, so I'll refrain from commenting on it.
>
> At the end of the day, the patch proposed is merely a wrapper around the
> functional approach; you are welcome to continue using it as you like, it's
> not going anywhere. I would propose that the docs put the OOP version first
> though.
>

>
On Wed, Nov 22, 2017 at 11:11 PM, Grant Jenks  wrote:
>
>> Honestly, I don't see the value in a thin object-oriented wrapper around
>> heapq functions. I'm a big -1 on the idea.
>>
>> I'm the author of sortedcontainers (https://pypi.python.org/pypi/
>> sortedcontainers/) so I interact with a lot of people using sorted
>> collections types. My observations show folk's needs tend to fit a bimodal
>> distribution. At one end are those who get by with list.sort, bisect, or
>> heapq and they seem to appreciate the simple function-based approach those
>> modules provide. At the other end are those who want a SortedList data type
>> and we have some good options on PyPI and some good building-blocks in the
>> standard library.
>>
>> Personally, I think "sorted", "bisect" and "heapq" in the standard
>> library are brilliant examples of the Python-way or "zen." I've learned a
>> lot by studying their code and I encourage others to do the same. Just
>> because something can be object-oriented doesn't mean it should be. There's
>> a lot to be said for simplicity. I also think Nick's arguments are valid
>> but I don't find them convincing.
>>
>> What I think would be sufficient is a "See also:" blurb like that under
>> https://docs.python.org/3/library/bisect.html#bisect.insort which also
>> references SortedContainers at http://www.grantjenks.com/d
>> ocs/sortedcontainers/ and the same blurb on heapq. I think that would be
>> a reasonable next-step before we include any new data type in the standard
>> library.
>>
>> Grant
>>
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Nick Coghlan]

On 23 November 2017 at 15:22, bunslow  wrote:

> Something *should* be object oriented with the functions in question all
> operate on the same data type, and in particular, those functions/verbs
> *are only well defined for that type*. heapq.heappush(list-not-heap, item)
> is perfectly valid code in the current interface, but doesn't make any
> sense at all. And list.sort is *not* function based, it's an object
> oriented method. sorted() provides the same functionality for other types,
> given that it's a well defined function for a wide variety of sequences
> (unlike heappush). (list.sort is a method because unlike sorted(), it
> operates inplace, and is thus only meaningful for mutable, "complete" (all
> in memory, not "lazy") sequences -- i.e., a list.)
>
> I've never used bisect, so I'll refrain from commenting on it.
>
> At the end of the day, the patch proposed is merely a wrapper around the
> functional approach; you are welcome to continue using it as you like, it's
> not going anywhere. I would propose that the docs put the OOP version first
> though.
>

Ensuring the docs are clearly separated is part of why I think
"collections.Heap" would make more sense as a proposal than "heapq.Heap" -
collections already imports heapq for use in the Counter implementation,
and adding another primitive container type to collections is a smaller
conceptual change than updating heapq to being more than just a heap
algorithm library.

I'd also note that a collections.Heap class that accepts the underlying
list to use as its sole parameter would compose nicely with the list
builtin to allow creation of a heap from an arbitrary iterable:

heap = collections.Heap(list(iterable))

rather than the current:

heap = list(iterable)
heapq.heapify(heap)

That's akin to the difference between:

data = sorted(iterable)

and:

data = list(iterable)
data.sort()

I don't think it would be a disaster if we continued to leave this out, but
I don't think it would be a major maintenance burden or future barrier to
learning to add it, either.

Cheers,
Nick.

-- 
Nick Coghlan   |   ncogh...@gmail.com   |   Brisbane, Australia
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[bunslow]

Something *should* be object oriented with the functions in question all
operate on the same data type, and in particular, those functions/verbs
*are only well defined for that type*. heapq.heappush(list-not-heap, item)
is perfectly valid code in the current interface, but doesn't make any
sense at all. And list.sort is *not* function based, it's an object
oriented method. sorted() provides the same functionality for other types,
given that it's a well defined function for a wide variety of sequences
(unlike heappush). (list.sort is a method because unlike sorted(), it
operates inplace, and is thus only meaningful for mutable, "complete" (all
in memory, not "lazy") sequences -- i.e., a list.)

I've never used bisect, so I'll refrain from commenting on it.

At the end of the day, the patch proposed is merely a wrapper around the
functional approach; you are welcome to continue using it as you like, it's
not going anywhere. I would propose that the docs put the OOP version first
though.

On Wed, Nov 22, 2017 at 11:11 PM, Grant Jenks  wrote:

> Honestly, I don't see the value in a thin object-oriented wrapper around
> heapq functions. I'm a big -1 on the idea.
>
> I'm the author of sortedcontainers (https://pypi.python.org/pypi/
> sortedcontainers/) so I interact with a lot of people using sorted
> collections types. My observations show folk's needs tend to fit a bimodal
> distribution. At one end are those who get by with list.sort, bisect, or
> heapq and they seem to appreciate the simple function-based approach those
> modules provide. At the other end are those who want a SortedList data type
> and we have some good options on PyPI and some good building-blocks in the
> standard library.
>
> Personally, I think "sorted", "bisect" and "heapq" in the standard library
> are brilliant examples of the Python-way or "zen." I've learned a lot by
> studying their code and I encourage others to do the same. Just because
> something can be object-oriented doesn't mean it should be. There's a lot
> to be said for simplicity. I also think Nick's arguments are valid but I
> don't find them convincing.
>
> What I think would be sufficient is a "See also:" blurb like that under
> https://docs.python.org/3/library/bisect.html#bisect.insort which also
> references SortedContainers at http://www.grantjenks.com/
> docs/sortedcontainers/ and the same blurb on heapq. I think that would be
> a reasonable next-step before we include any new data type in the standard
> library.
>
> Grant
>
>
> On Wed, Nov 22, 2017 at 8:05 PM, Nick Coghlan  wrote:
>
>> On 22 November 2017 at 11:00, Chris Angelico  wrote:
>>
>>> So the question is more: why, with Python being the way it is, do the
>>> heap functions operate on a list? I think heapq.heapify is the answer:
>>> in linear time, it heapifies a list *in place*.
>>>
>>> I don't think there's any reason to have *both* interfaces to the heap
>>> functionality, but it certainly isn't illogical to try to treat a heap
>>> as a thing, and therefore have a Heap type.
>>>
>>
>> Right, the parallel here is that we have a "heapq" module for the same
>> reason that we have list.sort(), sorted(), and the bisect module, rather
>> than a single "SortedList" type. https://code.activestate.com/r
>> ecipes/577197-sortedcollection/ then provides an example of how to
>> combine those into a "SortedCollection" type.
>>
>> That said, I'm still in favour of adding an object-oriented wrapper to
>> either `collections` or the `heapq` module for all the classic OO reasons:
>>
>> - it makes it easier to reliably maintain the heap invariant (just drop
>> your list reference after passing it to the heap wrapper)
>> - it gives both human readers and static code analysers more information
>> to work with ("this is a heap" rather than "this is a list")
>> - it provides a hook for improved interactive help on heap instances
>>
>> I don't have any great concerns about potential confusion - the OO
>> wrapper will be easy enough to use that anyone that's unsure will likely
>> gravitate towards that, while the lower level `heapq` functions will remain
>> available for folks writing their own heap implementations.
>>
>> This effect would likely be even more pronounced if the OO wrapper were
>> made available as `collections.Heap` (`collections` already imports the
>> `heapq` module for use in the Counter implementation).
>>
>> Cheers,
>> Nick.
>>
>> --
>> Nick Coghlan   |   ncogh...@gmail.com   |   Brisbane, Australia
>>
>> ___
>> Python-ideas mailing list
>> Python-ideas@python.org
>> https://mail.python.org/mailman/listinfo/python-ideas
>> Code of Conduct: http://python.org/psf/codeofconduct/
>>
>>
>
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
>
___
Python-ideas m

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[bunslow]

On Wed, Nov 22, 2017 at 10:52 PM, bunslow  wrote:

> I'll just note the original proposal I made was specifically designed to
> be the minimum possible improvement, to avoid controversy (and e.g. a PEP).
>
> I agree that there are significant flaws and room for improvement in the
> current heapq module (which is why things like xheap exist), but even so
> it's still very useful as is, and the minimal OOP wrapper would go a long
> way towards usability of the current functionality (and of course "just use
> pip" is often not a viable course of action for certain developers). It
> seems that such a wrapper is widely (though not unanimously) approved.
>
> Next step I suppose is creating a bpo issue?
>
> On Wed, Nov 22, 2017 at 10:05 PM, Nick Coghlan  wrote:
>
>> On 22 November 2017 at 11:00, Chris Angelico  wrote:
>>
>>> So the question is more: why, with Python being the way it is, do the
>>> heap functions operate on a list? I think heapq.heapify is the answer:
>>> in linear time, it heapifies a list *in place*.
>>>
>>> I don't think there's any reason to have *both* interfaces to the heap
>>> functionality, but it certainly isn't illogical to try to treat a heap
>>> as a thing, and therefore have a Heap type.
>>>
>>
>> Right, the parallel here is that we have a "heapq" module for the same
>> reason that we have list.sort(), sorted(), and the bisect module, rather
>> than a single "SortedList" type. https://code.activestate.com/r
>> ecipes/577197-sortedcollection/ then provides an example of how to
>> combine those into a "SortedCollection" type.
>>
>> That said, I'm still in favour of adding an object-oriented wrapper to
>> either `collections` or the `heapq` module for all the classic OO reasons:
>>
>> - it makes it easier to reliably maintain the heap invariant (just drop
>> your list reference after passing it to the heap wrapper)
>> - it gives both human readers and static code analysers more information
>> to work with ("this is a heap" rather than "this is a list")
>> - it provides a hook for improved interactive help on heap instances
>>
>> I don't have any great concerns about potential confusion - the OO
>> wrapper will be easy enough to use that anyone that's unsure will likely
>> gravitate towards that, while the lower level `heapq` functions will remain
>> available for folks writing their own heap implementations.
>>
>> This effect would likely be even more pronounced if the OO wrapper were
>> made available as `collections.Heap` (`collections` already imports the
>> `heapq` module for use in the Counter implementation).
>>
>> Cheers,
>> Nick.
>>
>> --
>> Nick Coghlan   |   ncogh...@gmail.com   |   Brisbane, Australia
>>
>> ___
>> Python-ideas mailing list
>> Python-ideas@python.org
>> https://mail.python.org/mailman/listinfo/python-ideas
>> Code of Conduct: http://python.org/psf/codeofconduct/
>>
>>
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Grant Jenks]

Honestly, I don't see the value in a thin object-oriented wrapper around
heapq functions. I'm a big -1 on the idea.

I'm the author of sortedcontainers (
https://pypi.python.org/pypi/sortedcontainers/) so I interact with a lot of
people using sorted collections types. My observations show folk's needs
tend to fit a bimodal distribution. At one end are those who get by with
list.sort, bisect, or heapq and they seem to appreciate the simple
function-based approach those modules provide. At the other end are those
who want a SortedList data type and we have some good options on PyPI and
some good building-blocks in the standard library.

Personally, I think "sorted", "bisect" and "heapq" in the standard library
are brilliant examples of the Python-way or "zen." I've learned a lot by
studying their code and I encourage others to do the same. Just because
something can be object-oriented doesn't mean it should be. There's a lot
to be said for simplicity. I also think Nick's arguments are valid but I
don't find them convincing.

What I think would be sufficient is a "See also:" blurb like that under
https://docs.python.org/3/library/bisect.html#bisect.insort which also
references SortedContainers at
http://www.grantjenks.com/docs/sortedcontainers/ and the same blurb on
heapq. I think that would be a reasonable next-step before we include any
new data type in the standard library.

Grant


On Wed, Nov 22, 2017 at 8:05 PM, Nick Coghlan  wrote:

> On 22 November 2017 at 11:00, Chris Angelico  wrote:
>
>> So the question is more: why, with Python being the way it is, do the
>> heap functions operate on a list? I think heapq.heapify is the answer:
>> in linear time, it heapifies a list *in place*.
>>
>> I don't think there's any reason to have *both* interfaces to the heap
>> functionality, but it certainly isn't illogical to try to treat a heap
>> as a thing, and therefore have a Heap type.
>>
>
> Right, the parallel here is that we have a "heapq" module for the same
> reason that we have list.sort(), sorted(), and the bisect module, rather
> than a single "SortedList" type. https://code.activestate.com/
> recipes/577197-sortedcollection/ then provides an example of how to
> combine those into a "SortedCollection" type.
>
> That said, I'm still in favour of adding an object-oriented wrapper to
> either `collections` or the `heapq` module for all the classic OO reasons:
>
> - it makes it easier to reliably maintain the heap invariant (just drop
> your list reference after passing it to the heap wrapper)
> - it gives both human readers and static code analysers more information
> to work with ("this is a heap" rather than "this is a list")
> - it provides a hook for improved interactive help on heap instances
>
> I don't have any great concerns about potential confusion - the OO wrapper
> will be easy enough to use that anyone that's unsure will likely gravitate
> towards that, while the lower level `heapq` functions will remain available
> for folks writing their own heap implementations.
>
> This effect would likely be even more pronounced if the OO wrapper were
> made available as `collections.Heap` (`collections` already imports the
> `heapq` module for use in the Counter implementation).
>
> Cheers,
> Nick.
>
> --
> Nick Coghlan   |   ncogh...@gmail.com   |   Brisbane, Australia
>
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Nick Coghlan]

On 22 November 2017 at 11:00, Chris Angelico  wrote:

> So the question is more: why, with Python being the way it is, do the
> heap functions operate on a list? I think heapq.heapify is the answer:
> in linear time, it heapifies a list *in place*.
>
> I don't think there's any reason to have *both* interfaces to the heap
> functionality, but it certainly isn't illogical to try to treat a heap
> as a thing, and therefore have a Heap type.
>

Right, the parallel here is that we have a "heapq" module for the same
reason that we have list.sort(), sorted(), and the bisect module, rather
than a single "SortedList" type.
https://code.activestate.com/recipes/577197-sortedcollection/ then provides
an example of how to combine those into a "SortedCollection" type.

That said, I'm still in favour of adding an object-oriented wrapper to
either `collections` or the `heapq` module for all the classic OO reasons:

- it makes it easier to reliably maintain the heap invariant (just drop
your list reference after passing it to the heap wrapper)
- it gives both human readers and static code analysers more information to
work with ("this is a heap" rather than "this is a list")
- it provides a hook for improved interactive help on heap instances

I don't have any great concerns about potential confusion - the OO wrapper
will be easy enough to use that anyone that's unsure will likely gravitate
towards that, while the lower level `heapq` functions will remain available
for folks writing their own heap implementations.

This effect would likely be even more pronounced if the OO wrapper were
made available as `collections.Heap` (`collections` already imports the
`heapq` module for use in the Counter implementation).

Cheers,
Nick.

-- 
Nick Coghlan   |   ncogh...@gmail.com   |   Brisbane, Australia
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Greg Ewing]

Chris Angelico wrote:

Yeah but if it's wrapping an existing list, it's not really
constructing a new object.


That depends on what you consider the object to be. There
are existing examples of objects that wrap other objects
and mutate them, e.g. TextIOWrapper.

If it would make anyone happier, there could be two classes,
Heap and HeapWrapper (with one probably being implemented
as a subclass of the other).

--
Greg
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Stephan Houben]

I thought the purpose of heapq was to have a ready-made example
for instructors on how an API can be improved by applying object-oriented
techniques. ;-)

I think adding a HeapQueue class would be a great idea. Obviously the
existing functions
would need to continue existing for backward compatibility.

Stephan

2017-11-22 12:09 GMT+01:00 Antoine Pitrou :

> On Wed, 22 Nov 2017 00:22:00 -0600
> Nick Timkovich 
> wrote:
> >
> > Functions are great. I'm a big fan of functions. However,
> >
> > 1. Once there are several that all have the same thing as an argument:
> > thing_operation1(thing, arg), thing_operation2(thing, arg)...it's about
> > time to bind them together.
> > 2. And especially for the heap "soft-datatype": once it's heapified,
> > naively modifying it with other methods will ruin the heap invariant.
> **The
> > actual list you pass around can't be treated as a list.**
>
> A third reason: documentation and discoverability.  If I type
> help(some_heapified_list) at the prompt, I get the usual documentation
> for list methods, not the documentation of heapq functions...
>
> Regards
>
> Antoine.
>
>
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Antoine Pitrou]

On Wed, 22 Nov 2017 00:22:00 -0600
Nick Timkovich 
wrote:
> 
> Functions are great. I'm a big fan of functions. However,
> 
> 1. Once there are several that all have the same thing as an argument:
> thing_operation1(thing, arg), thing_operation2(thing, arg)...it's about
> time to bind them together.
> 2. And especially for the heap "soft-datatype": once it's heapified,
> naively modifying it with other methods will ruin the heap invariant. **The
> actual list you pass around can't be treated as a list.**

A third reason: documentation and discoverability.  If I type
help(some_heapified_list) at the prompt, I get the usual documentation
for list methods, not the documentation of heapq functions...

Regards

Antoine.


___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Antoine Pitrou]

On Wed, 22 Nov 2017 17:11:53 +1100
Chris Angelico  wrote:
> On Wed, Nov 22, 2017 at 3:55 PM, Greg Ewing  
> wrote:
> > Chris Angelico wrote:  
> >>
> >> So the question is more: why, with Python being the way it is, do the
> >> heap functions operate on a list? I think heapq.heapify is the answer:
> >> in linear time, it heapifies a list *in place*.  
> >
> >
> > There's no reason a Heap object couldn't accomodate that
> > case. E.g. the constructor could optionally accept an
> > existing list to heapify and wrap.
> >  
> 
> Yeah but if it's wrapping an existing list, it's not really
> constructing a new object. Every other constructor in Python will make
> something independent of its origin (if you call list() on a list, you
> get back a brand new copy, for instance), but to take advantage of
> in-place heapification, it would have to mutate the input. I think
> that would be even more surprising.

In any case, copying a list a pretty cheap, so in-place heapification
isn't a very important optimization.

Regards

Antoine.


___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Sven R. Kunze]

On 22.11.2017 07:22, Nick Timkovich wrote:

Functions are great. I'm a big fan of functions. However,

1. Once there are several that all have the same thing as an argument: 
thing_operation1(thing, arg), thing_operation2(thing, arg)...it's 
about time to bind them together.
2. And especially for the heap "soft-datatype": once it's heapified, 
naively modifying it with other methods will ruin the heap invariant. 
**The actual list you pass around can't be treated as a list.**


Two important aspects to which I want to add some thoughts.

The reason why I created xheap was because I actually needed a more 
complex datastructure which required more bookkeeping:


1) custom orders on the same data (list)
2) fast removal from within the heap

The plain "Heap" implementation (object wrapper of heapq) was just for 
the sake of completion.


Cheers,
Sven

PS: I tend to think that implementing xheap was easier BECAUSE the 
stdlib provided a function-only heap implementation. Nonetheless, both 
ways do have their merits.
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Nick Timkovich]

On Tue, Nov 21, 2017 at 6:45 PM, Steven D'Aprano 
wrote:

> On Tue, Nov 21, 2017 at 04:56:27PM -0600, Nick Timkovich wrote:
> > On Tue, Nov 21, 2017 at 4:16 PM, Sven R. Kunze  wrote:
> >
> > > Maybe, that suffices: https://pypi.python.org/pypi/xheap
> > >
> > I still think the heapq.heap* functions are atrocious and they should
> > immediately be packaged with *no additional features* into a stdlib
> object
> > for reasons along the line of
> > https://mail.python.org/pipermail/python-ideas/2017-October/047514.html
>
> I think you pasted the wrong URL. That link is about pip, and the
> discoverability of third-party libraries.
>

Probably straining the reference, but akin to "don't teach JSON with
Python, teach XML-RPC because it supports that better in the stdlib", why
not "don't teach heaps, just use lists with pop and insert+sort".


> But generally, Python's APIs are not "pure object oriented" in the Java
> sense, and we don't needlessly create objects just for the sake of
> ensuring everything is an object. Functions are fine too...


Functions are great. I'm a big fan of functions. However,

1. Once there are several that all have the same thing as an argument:
thing_operation1(thing, arg), thing_operation2(thing, arg)...it's about
time to bind them together.
2. And especially for the heap "soft-datatype": once it's heapified,
naively modifying it with other methods will ruin the heap invariant. **The
actual list you pass around can't be treated as a list.**
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Chris Angelico]

On Wed, Nov 22, 2017 at 3:55 PM, Greg Ewing  wrote:
> Chris Angelico wrote:
>>
>> So the question is more: why, with Python being the way it is, do the
>> heap functions operate on a list? I think heapq.heapify is the answer:
>> in linear time, it heapifies a list *in place*.
>
>
> There's no reason a Heap object couldn't accomodate that
> case. E.g. the constructor could optionally accept an
> existing list to heapify and wrap.
>

Yeah but if it's wrapping an existing list, it's not really
constructing a new object. Every other constructor in Python will make
something independent of its origin (if you call list() on a list, you
get back a brand new copy, for instance), but to take advantage of
in-place heapification, it would have to mutate the input. I think
that would be even more surprising.

ChrisA
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Greg Ewing]

Chris Angelico wrote:

So the question is more: why, with Python being the way it is, do the
heap functions operate on a list? I think heapq.heapify is the answer:
in linear time, it heapifies a list *in place*.


There's no reason a Heap object couldn't accomodate that
case. E.g. the constructor could optionally accept an
existing list to heapify and wrap.

--
Greg
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Chris Angelico]

On Wed, Nov 22, 2017 at 11:45 AM, Steven D'Aprano  wrote:
> On Tue, Nov 21, 2017 at 04:56:27PM -0600, Nick Timkovich wrote:
>> On Tue, Nov 21, 2017 at 4:16 PM, Sven R. Kunze  wrote:
>>
>> > Maybe, that suffices: https://pypi.python.org/pypi/xheap
>> >
>> I still think the heapq.heap* functions are atrocious and they should
>> immediately be packaged with *no additional features* into a stdlib object
>> for reasons along the line of
>> https://mail.python.org/pipermail/python-ideas/2017-October/047514.html
>
> I think you pasted the wrong URL. That link is about pip, and the
> discoverability of third-party libraries. It says nothing about why
> functions are "atrocious" and why wrapping them into an object is
> better.
>
> But generally, Python's APIs are not "pure object oriented" in the Java
> sense, and we don't needlessly create objects just for the sake of
> ensuring everything is an object. Functions are fine too, and if the
> only difference between a function and method is the syntax you use to
> call it:
>
> function(value, arguments)
>
> versus
>
> value.function(arguments)
>
>
> then that's a difference that makes no difference, and there is no
> advantage to using an object wrapper.
>
> See also:
>
> http://steve-yegge.blogspot.com.au/2006/03/execution-in-kingdom-of-nouns.html
>
> for a perspective on how the emphasis on objects is harmful.
>
> What advantage is there to making the heap functions into Heap methods?

A heap is an actual thing. We don't have dict methods implemented as
functions operating on a "blob of memory" object; we have dict as a
type. So the most simple and obvious way to work with a heap would be
something like:

from heaps import Heap

h = Heap()
h.push(blah)
h.pop()

So the question is more: why, with Python being the way it is, do the
heap functions operate on a list? I think heapq.heapify is the answer:
in linear time, it heapifies a list *in place*.

I don't think there's any reason to have *both* interfaces to the heap
functionality, but it certainly isn't illogical to try to treat a heap
as a thing, and therefore have a Heap type.

ChrisA
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Steven D'Aprano]

On Tue, Nov 21, 2017 at 04:56:27PM -0600, Nick Timkovich wrote:
> On Tue, Nov 21, 2017 at 4:16 PM, Sven R. Kunze  wrote:
> 
> > Maybe, that suffices: https://pypi.python.org/pypi/xheap
> >
> I still think the heapq.heap* functions are atrocious and they should
> immediately be packaged with *no additional features* into a stdlib object
> for reasons along the line of
> https://mail.python.org/pipermail/python-ideas/2017-October/047514.html

I think you pasted the wrong URL. That link is about pip, and the 
discoverability of third-party libraries. It says nothing about why 
functions are "atrocious" and why wrapping them into an object is 
better.

But generally, Python's APIs are not "pure object oriented" in the Java 
sense, and we don't needlessly create objects just for the sake of 
ensuring everything is an object. Functions are fine too, and if the 
only difference between a function and method is the syntax you use to 
call it:

function(value, arguments)

versus

value.function(arguments)


then that's a difference that makes no difference, and there is no 
advantage to using an object wrapper.

See also:

http://steve-yegge.blogspot.com.au/2006/03/execution-in-kingdom-of-nouns.html

for a perspective on how the emphasis on objects is harmful.

What advantage is there to making the heap functions into Heap methods?



-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Nick Timkovich]

On Tue, Nov 21, 2017 at 4:16 PM, Sven R. Kunze  wrote:

> Maybe, that suffices: https://pypi.python.org/pypi/xheap
>
I still think the heapq.heap* functions are atrocious and they should
immediately be packaged with *no additional features* into a stdlib object
for reasons along the line of
https://mail.python.org/pipermail/python-ideas/2017-October/047514.html

If the improvements in xheap are converging on boringly-stable, maybe bring
them in at a later date.
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Sven R. Kunze]

Maybe, that suffices: https://pypi.python.org/pypi/xheap


On 21.11.2017 03:46, bunslow wrote:

Perhaps such repetition is a sign that *something* needs to be done...

Thanks for the link though. I'm new enough to the community that it 
didn't even occur to me to search for prior discussions.


On Mon, Nov 20, 2017 at 8:38 PM, Sebastian Kreft > wrote:


This has been brought up multiple times. Last time was on this
thread
https://mail.python.org/pipermail/python-ideas/2016-October/043024.html
.

On Tue, Nov 21, 2017 at 3:13 AM, bunslow mailto:buns...@gmail.com>> wrote:

Nothing so bombastic this time. The heapq functions are
basically all named "heapsomething", and basically all take a
"heap" for their first argument, with supplementary args
coming after. It's a textbook example of the (hypothetical)
Object Oriented Manifesto™ where defining a class increases
type safety and programmers' conceptual clarity. There're
practically no drawbacks, and the code to be added would be
very simple. Updating the tests and docs would probably be
harder.

In pure Python, such a class would look like this:

class Heap(list):

    def __init__(self, iterable=None):
        if iterable:
            super().__init__(iterable)
        else:
            super().__init__()

        self.heapify()

    push = heapq.heappush
    pop = heapq.heappop
    pushpop = heapq.heappushpop
    replace = heapq.heapreplace
    heapify = heapq.heapify

    # This could be a simple wrapper as well, but I had the
following thoughts anyways, so here they are
    def nsmallest(self, n, key=None):
        # heapq.nsmallest makes a *max* heap of the first n
elements,
        # while we know that self is already a min heap, so we can
        # make the max heap construction faster
        self[:n] = reversed(self[:n])
        return heapq.nsmallest(n, self, key)

    # do we define nlargest on a minheap??


Wrapping around the C builtin functions (which aren't
descriptors) would be a bit harder, but not much so:

from functools import partial

class Heap(list):
    def __init__(self, iterable=None):
        if iterable:
            super().__init__(iterable)
        else:
            super().__init__()

        self.heapify = partial(heapq.heapify, self)
        self.push = partial(heapq.heappush, self)
        ...

        self.heapify()


Thoughts?

___
Python-ideas mailing list
Python-ideas@python.org 
https://mail.python.org/mailman/listinfo/python-ideas

Code of Conduct: http://python.org/psf/codeofconduct/





-- 
Sebastian Kreft





___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/


___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Stephen J. Turnbull]

bunslow writes:

 > Perhaps such repetition is a sign that *something* needs to be
 > done...

It's not.  Most such repetition is due to new people who have not read
the last 20 years of archives. :-)  (In case the smiley isn't clear
enough, parse that as "all the new people who aren't cray-cray".)

That doesn't mean there's nothing to the idea, it just means that
*mere repetition* of certain proposals is only a sign that "great[sic]
minds think alike," while Python development is attracting new people
at a high rate.

Repetition of certain arguments *in the same thread*, on the other
hand, is often a sign that a meeting of minds has not be reached, and
that can be symptomatic of problems (though it's not necessarily an
indication of the necessity of a proposal).


Regards,

Steve

___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[bunslow]

Perhaps such repetition is a sign that *something* needs to be done...

Thanks for the link though. I'm new enough to the community that it didn't
even occur to me to search for prior discussions.

On Mon, Nov 20, 2017 at 8:38 PM, Sebastian Kreft  wrote:

> This has been brought up multiple times. Last time was on this thread
> https://mail.python.org/pipermail/python-ideas/2016-October/043024.html.
>
> On Tue, Nov 21, 2017 at 3:13 AM, bunslow  wrote:
>
>> Nothing so bombastic this time. The heapq functions are basically all
>> named "heapsomething", and basically all take a "heap" for their first
>> argument, with supplementary args coming after. It's a textbook example of
>> the (hypothetical) Object Oriented Manifesto™ where defining a class
>> increases type safety and programmers' conceptual clarity. There're
>> practically no drawbacks, and the code to be added would be very simple.
>> Updating the tests and docs would probably be harder.
>>
>> In pure Python, such a class would look like this:
>>
>> class Heap(list):
>>
>> def __init__(self, iterable=None):
>> if iterable:
>> super().__init__(iterable)
>> else:
>> super().__init__()
>>
>> self.heapify()
>>
>> push = heapq.heappush
>> pop = heapq.heappop
>> pushpop = heapq.heappushpop
>> replace = heapq.heapreplace
>> heapify = heapq.heapify
>>
>> # This could be a simple wrapper as well, but I had the following
>> thoughts anyways, so here they are
>> def nsmallest(self, n, key=None):
>> # heapq.nsmallest makes a *max* heap of the first n elements,
>> # while we know that self is already a min heap, so we can
>> # make the max heap construction faster
>> self[:n] = reversed(self[:n])
>> return heapq.nsmallest(n, self, key)
>>
>> # do we define nlargest on a minheap??
>>
>>
>> Wrapping around the C builtin functions (which aren't descriptors) would
>> be a bit harder, but not much so:
>>
>> from functools import partial
>>
>> class Heap(list):
>> def __init__(self, iterable=None):
>> if iterable:
>> super().__init__(iterable)
>> else:
>> super().__init__()
>>
>> self.heapify = partial(heapq.heapify, self)
>> self.push = partial(heapq.heappush, self)
>> ...
>>
>> self.heapify()
>>
>>
>> Thoughts?
>>
>> ___
>> Python-ideas mailing list
>> Python-ideas@python.org
>> https://mail.python.org/mailman/listinfo/python-ideas
>> Code of Conduct: http://python.org/psf/codeofconduct/
>>
>>
>
>
> --
> Sebastian Kreft
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[Sebastian Kreft]

This has been brought up multiple times. Last time was on this thread
https://mail.python.org/pipermail/python-ideas/2016-October/043024.html.

On Tue, Nov 21, 2017 at 3:13 AM, bunslow  wrote:

> Nothing so bombastic this time. The heapq functions are basically all
> named "heapsomething", and basically all take a "heap" for their first
> argument, with supplementary args coming after. It's a textbook example of
> the (hypothetical) Object Oriented Manifesto™ where defining a class
> increases type safety and programmers' conceptual clarity. There're
> practically no drawbacks, and the code to be added would be very simple.
> Updating the tests and docs would probably be harder.
>
> In pure Python, such a class would look like this:
>
> class Heap(list):
>
> def __init__(self, iterable=None):
> if iterable:
> super().__init__(iterable)
> else:
> super().__init__()
>
> self.heapify()
>
> push = heapq.heappush
> pop = heapq.heappop
> pushpop = heapq.heappushpop
> replace = heapq.heapreplace
> heapify = heapq.heapify
>
> # This could be a simple wrapper as well, but I had the following
> thoughts anyways, so here they are
> def nsmallest(self, n, key=None):
> # heapq.nsmallest makes a *max* heap of the first n elements,
> # while we know that self is already a min heap, so we can
> # make the max heap construction faster
> self[:n] = reversed(self[:n])
> return heapq.nsmallest(n, self, key)
>
> # do we define nlargest on a minheap??
>
>
> Wrapping around the C builtin functions (which aren't descriptors) would
> be a bit harder, but not much so:
>
> from functools import partial
>
> class Heap(list):
> def __init__(self, iterable=None):
> if iterable:
> super().__init__(iterable)
> else:
> super().__init__()
>
> self.heapify = partial(heapq.heapify, self)
> self.push = partial(heapq.heappush, self)
> ...
>
> self.heapify()
>
>
> Thoughts?
>
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
>


-- 
Sebastian Kreft
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

[Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

[bunslow]

Nothing so bombastic this time. The heapq functions are basically all named
"heapsomething", and basically all take a "heap" for their first argument,
with supplementary args coming after. It's a textbook example of the
(hypothetical) Object Oriented Manifesto™ where defining a class increases
type safety and programmers' conceptual clarity. There're practically no
drawbacks, and the code to be added would be very simple. Updating the
tests and docs would probably be harder.

In pure Python, such a class would look like this:

class Heap(list):

def __init__(self, iterable=None):
if iterable:
super().__init__(iterable)
else:
super().__init__()

self.heapify()

push = heapq.heappush
pop = heapq.heappop
pushpop = heapq.heappushpop
replace = heapq.heapreplace
heapify = heapq.heapify

# This could be a simple wrapper as well, but I had the following
thoughts anyways, so here they are
def nsmallest(self, n, key=None):
# heapq.nsmallest makes a *max* heap of the first n elements,
# while we know that self is already a min heap, so we can
# make the max heap construction faster
self[:n] = reversed(self[:n])
return heapq.nsmallest(n, self, key)

# do we define nlargest on a minheap??


Wrapping around the C builtin functions (which aren't descriptors) would be
a bit harder, but not much so:

from functools import partial

class Heap(list):
def __init__(self, iterable=None):
if iterable:
super().__init__(iterable)
else:
super().__init__()

self.heapify = partial(heapq.heapify, self)
self.push = partial(heapq.heappush, self)
...

self.heapify()


Thoughts?
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/