python STL?

[Maxim Khesin]

Hi,
being recently introduced to the joys of programming in a powerful
dynamic language (go snake!) I periodically rethink which parts of C++ I
still miss. One thing I really enjoy is the generics of C++ - i think
they are the single strong benefit of a strongly typed system. I was
wondering about the possibility of implementing STL-like algorithms in
Python and the one thing that I cannot think of doing without a kludge
is the object comparsion that so much of STL relies on, which in turn
relies on types and function(<) overloading. Is there a way to implement
something similar in python (short of multimethods?). How does the
python dictionary object allow arbitrary key types? Is in internally
using the references' addresses to impose the tree ordering?
thanks,
max.

 

[Dave Brueck]

being recently introduced to the joys of programming in a powerful

dynamic language (go snake!) I periodically rethink which parts of C++ I
still miss. One thing I really enjoy is the generics of C++ - i think
they are the single strong benefit of a strongly typed system. I was
wondering about the possibility of implementing STL-like algorithms in
Python and the one thing that I cannot think of doing without a kludge
is the object comparsion that so much of STL relies on, which in turn
relies on types and function(<) overloading. Is there a way to implement
something similar in python (short of multimethods?). How does the
python dictionary object allow arbitrary key types? Is in internally
using the references' addresses to impose the tree ordering?
thanks,
max.

Hi Max,

Could you give a more specific example of what you miss?

-Dave

 

[xam]

std::sort - works on any well-ordered object collection (you just define
your own operator< if you need to sort based on some weird criteria)

 

[Dave Brueck]

std::sort - works on any well-ordered object collection (you just define
your own operator< if you need to sort based on some weird criteria)

Right - this is what I suspected: most of the C++ STL _functionality_ is
available in Python already. Not all of it, but at least what I find to be the
most useful stuff (and in general if it's not built-in it's "almost" built-in
in that it's trivial to implement, so much so that having a Python STL wouldn't
make sense).

For example, Python's standard sort() already works on object collections, and
you could define your own comparison method if you want.

-Dave

 

[Ron Levine]

std::sort - works on any well-ordered object collection (you just define
your own operator< if you need to sort based on some weird criteria)

That particular one ALREADy exists in the standard sort(lt) funciton,
whose optional argument lt is any "less than" operator you care to
define.

 

[Dietrich Epp]

std::sort - works on any well-ordered object collection (you just
define
your own operator< if you need to sort based on some weird criteria)

class Foo:
def __init__(self, bar):
self.bar = bar
def __cmp__(self, other):
return cmp(self.bar, other.bar)
def __repr__(self):
return 'Foo(%i)' % self.bar

myList = [Foo(1), Foo(7), Foo(3), Foo(8), Foo(-1755)]
myList.sort()
print myList

Yeilds:
[Foo(-1755), Foo(1), Foo(3), Foo(7), Foo(8)]

STL stands for Standard Template Library. With a dynamic type system
it's completely unnecessary -- you don't need a new type of list to
sort a new type of object.

Personally, I hate the STL because it adds code without adding
functionality and I avoid it at all costs when programming in C++.
It's also not as portable as it should be. I hope this doesn't spark a
big thread. Everyone programs in C++ for different reasons for
different requirements.

 

[val]

google with stl.py and enjoy it...
val

 

[Andrew Dalke]

Ron Levine:

[std::sort] ALREADy exists in the standard sort(lt) funciton,
whose optional argument lt is any "less than" operator you care to
define.

Not quite. STL splits algorithms and containers. Python's sort
is a method on native lists. Suppose I make my own list-like data
structure which implements __getitem__ and __setitem__
etc. as needed for the container aspect of a list. If I want to
sort those values I need to implement my own sort code,
with no ability to leverage the standard Python sort code.

Eg, suppose I had a fixed-width file where I can read/write
fields from the file and can replace entries, but cannot add
or delete fields.

class FileList:
def __init__(self, filename):
self.filename = filename
self.infile = open(filename, "rwb")
self._n = os.path.getsize(filename) / 40
def __len__(self): return self._n
def __getitem__(self, i):
if not (0 <= i < self._n):
raise IndexError(i)
return self.infile.seek(i*40).read(40)
def __setitem__(self, i, s):
if not (0 <= i < self._n):
raise IndexError(i)
assert len(s) == 40
self.infile.seek(i*40).write(s)

The idea is that a 'std::sort' *algorithm* should be
able to use this list-like container even though there's
no implementation similarity between it and native lists.

Andrew
(e-mail address removed)

 

[Cy Edmunds]

Hi,
being recently introduced to the joys of programming in a powerful
dynamic language (go snake!) I periodically rethink which parts of C++ I
still miss. One thing I really enjoy is the generics of C++ - i think
they are the single strong benefit of a strongly typed system. I was
wondering about the possibility of implementing STL-like algorithms in
Python and the one thing that I cannot think of doing without a kludge
is the object comparsion that so much of STL relies on, which in turn
relies on types and function(<) overloading. Is there a way to implement
something similar in python (short of multimethods?). How does the
python dictionary object allow arbitrary key types? Is in internally
using the references' addresses to impose the tree ordering?
thanks,
max.

The STL (now part of the standard library) does with considerable
complexity* that which Python does very simply. That's because C++ templates
attempt to do generic programming without breaking the type system. Python
has no type system to break so generic program comes naturally.

--
Cy
http://home.rochester.rr.com/cyhome/

*if you don't agree with that, I will whack you one with my copy of Josuttis

 

[Terry Reedy]

being recently introduced to the joys of programming in a powerful
dynamic language (go snake!) I periodically rethink which parts of C++ I
still miss. One thing I really enjoy is the generics of C++

Then since Python programming generally *is* generic programming, it
is not surprising that you enjoy Python ;-).

- i think they are the single strong benefit of a strongly typed

system.

And Python is more strongly typed than C/C++ (no type casts except
possibly for some user classes).

I was wondering about the possibility of implementing
STL-like algorithms in Python

From what I understand of STL, Python functions are STL or template
like unless one specificly adds type checks to inhibit the generality.
Python code works with any object with the needed interface and
behavior. Perhaps you have not grokked this because it is automatic
in Python.

and the one thing that I cannot think of doing without a kludge
is the object comparsion that so much of STL relies on, which in turn
relies on types and function(<) overloading.

I do not understand this. Most builtin types come with working
comparison operations. User-defined classes can easily include them
also. I believe the builtin functions max and min are more
general/generic that what you can very easily write in C++.

Is there a way to implement something similar in python

Probably, but we need an example 'something'.

How does the python dictionary object allow arbitrary key types?

It accepts any hashable object by using the hash value.

Is in internally using the references' addresses

CPython uses object addresses, but that is an implementation detail
rather than part of the language definition. The C source is open and
pretty readable.

to impose the tree ordering?

There is no tree ordering as I understand the term.

Terry J. Reedy

 

[Terry Reedy]

std::sort - works on any well-ordered object collection (you just define
your own operator< if you need to sort based on some weird criteria)

List.sort works whenever the contents are inter-comparable, which is
possibly more often with Python than with C. It takes an optional
compare function and in 2.4 will probably take an optional key
function arg. This will be will be called O(n) instead of O(nlogn)
times (as with compare functions). Its n outputs will then be
compared as usual. List is the only linear non-lazy mutable builtin,
so a sort function rather than method would make no sense. Classes
derived from list inherit .sort().

When possible, Python functions (and for loops) work generically with
iterables rather than specifically with lists.

Terry J. Reedy

 

[rm]

The STL (now part of the standard library) does with considerable
complexity* that which Python does very simply. That's because C++ templates
attempt to do generic programming without breaking the type system. Python
has no type system to break so generic program comes naturally.

C++ is statically typed, so to keep the strong typing and at the same
type allowing code to be generic, templates were added.

Python is dynamically typed, so one doesn't need extra language
constructs to make things generic.

bye,
rm