From: Lie Ryan on
On 12/5/2009 12:38 PM, geremy condra wrote:
>
> Where a list will do, use a list- duh. But when you need a graph, you
> shouldn't have to homebrew an implementation any more than you
> should have to homebrew an odict or named tuple, both of which
> are substantially easier to get right than a graph is.

That's what I was trying to say, though I can't find a good way to. The
comparison with the Zen was to meant that if List is sufficient (if
Simple is sufficient) don't use Tree (don't design a Complex). I wasn't
implying to reduce all problem into a list at whatever costs, sorry if
my wording appears to imply so...
From: geremy condra on
On Fri, Dec 4, 2009 at 8:38 PM, Carl Banks <pavlovevidence(a)gmail.com> wrote:
> On Dec 4, 4:42 pm, Lie Ryan <lie.1...(a)gmail.com> wrote:
>> On 12/5/2009 9:41 AM, Carl Banks wrote:
>>
>>
>>
>>
>>
>> > On Dec 4, 12:46 pm, geremy condra<debat...(a)gmail.com>  wrote:
>> > more common than full-blown graph package).
>> >> Sure, its a tree, which is also a graph. In this case it looks to
>> >> me more like a directed acyclic graph than anything, but its
>> >> pretty much just semantics since the interface is functionally
>> >> equivalent.
>>
>> > I'd have to agree with Lie, yes a tree is a graph, but it's simply not
>> > an argument that Python community is grasping for graph structures.
>> > It's like arguing that the Python community could benefit from a
>> > quaternion type, because quaternions are actually heavily used in
>> > Python, because a scalar number is a quarternion.
>>
>> > Carl Banks
>>
>> > (Would be +1 on a good graph implementation... just not because of
>> > ElementTree.)
>>
>> I think this could be an interpretation of the Zen:
>>
>> Simple is better than complex.
>> Complex is better than complicated.
>>
>> can be read as:
>> List is better than Tree
>> Tree is better than Graph
>>
>> not having Tree and Graph package in the standard library force most
>> people to find List-based solution. And people that know they need
>> graphs will find them in 3rd party modules. I have needed Trees a few
>> times in python, but very rarely a Graph (except for playing around).
>> YMDWV (your mileage definitely will vary).
>
> If you want a better example, consider various database schemas that
> have one-to-one, one-to-many, many-to-one, and many-to-many
> relationships.  I daresay these are very common.  All of these can be
> represented by a non-directed graph.
>
> Another common use of directed graphs is for dependency
> relationships.  In practice, a lot of times running things in order of
> dependency is done by assigning everything a scalar priotity, and
> executing in order of priority.  This can work ok, but it's fragile.
> If there's a graph type in Python maybe people will be encouraged to
> handle dependencies explicitly.

I actually considered using dependencies as an example on the
"graphine for pythonistas"[1] article, but decided to do the maze
run instead. In any event, the uses of graphs in general computing
are well enough established that I don't really think that's where
the majority of the difficulty in coming up with something for the
standard library will be- deciding how it should look and behave,
especially in terms of scope and target audience, that's going to
be the difficult part.

Geremy Condra

[1]: http://gitorious.org/graphine/pages/GraphineForPythonistas
From: Steven D'Aprano on
On Sat, 05 Dec 2009 11:42:15 +1100, Lie Ryan wrote:

> I think this could be an interpretation of the Zen:
>
> Simple is better than complex.
> Complex is better than complicated.
>
> can be read as:
> List is better than Tree

Because O(N) searches are better than O(log N) searches. Not.

How about "The right tool for the right job"?


> Tree is better than Graph
>
> not having Tree and Graph package in the standard library force most
> people to find List-based solution.

If you have to be *forced* to use a list-based solution, that's a good
sign that a list is *not* the right tool for the job.




--
Steven
From: Raymond Hettinger on
[Me]
> > * we've already got one (actually two).
> >   The two dictionary approach...

[Francis Carr]
> Solutions such as bidict just automate the two-dict approach.

They do so at the expense of implementing a new API to support it and
at the expense with having non-obvious behaviors (i.e. how it handles
collapsing two records into one, which exceptions can be raised, how
the bijection invariants are maintained, which of the two symmetric
accessors is the primary, etc). This is not a cost-free choice of
simply "automating something".

IMO, "just automating" something that is already clear is not
necessarily a net win. Each new class has a learning curve and it is
sometimes simpler to use the basic dictionary API instead of inventing
a new one. I would *much* rather debug code written by someone using
two dictionaries than code using any of the APIs discussed so far --
all of those hide important design decisions behind a layer of
abstraction. The API must be easy to learn and remember (including
all of it quirks); otherwise, it is a net mental tax on the programmer
and code reviewers.

Also, I've presented examples of usability problems with APIs that do
not require the user to specify names for the two directions. It is
too easy to make mistakes that are hard to see. Which is correct,
phonelist['raymond'] or phonelist[raymonds_phonenumber]? There is no
way to tell without looking back at the bijection specification. The
API must be self-documenting. An API that is error-prone is worse
than having no bijection class at all.

Further, the API needs to be consistent with the rest of the language
(no abusing syntax with the likes of phonelist[:number]).

Unfortunately, Mark Lemburg has thrown gas on this fire, so the
conversation will likely continue for a while. If so, it would be
helpful if the conversation centered around real-world examples of
code that would be improved with a bijection class. In my experience,
there are examples where bijections arise in programs but it doesn't
happen often enough to warrant a new class for it. In cases where it
does arise, people should try-out the proposed APIs to see if in-fact
the code is made more clear or whether simple work is just being
hidden behind a layer of abstraction. For grins, insert an error into
the code (conflating the primary key with the secondary key) and see
if the error is self-evident or whether it is hidden by the new API.
Also, test the API for flexibility (how well can it adapt to
injections and surjections, can it handle use cases with default
values, is there a meaningful interpretation of dict.fromkeys() in a
bijection, can a user specify how to handle violations of the
bijection invariants by raising exceptions, supplying default values,
collapsing records, etc.)

Even if a proposed API passes those smell tests, demonstrates the
required flexibility, is easy to learn and use, is not error-prone,
and actually improves real-world use cases, it is my opinion that a
recipe for it will not garner a fan club and that it will have limited
uptake. ISTM that it is more fun to write classes like this than it
is to actually use them.

Raymond


P.S. It also makes sense to look at other mature languages to see
whether they ever find a need to include a bijection class in their
standard library or builtin collections. If Smalltalk, Java, Forth,
Go, Io, Haskell and C++ couldn't be sold on it, perhaps the buyer
should beware. If some language is found that did include a bijection
class, then do a Google code search to see how it fared in the real-
world. My bet is that it either wasn't used much or that it actually
make code worse by making errors harder to spot.


From: Raymond Hettinger on
> >   ...sqlite3 provides another way...
>
> In many many cases, using a dB (even a lightweight such as sqlite3) is
> swatting the fly with a sledgehammer :-)

I'm sure it seems that way, but look at the generic description of the
problem: "I have a list of n-ary tuples with named fields and would
like to be able to retrieve a tuple using any of m-fields as a lookup
key (where 2 <= m <= n). Also, I would like to enforce the constraint
that those m-fields are all unique keys."

That pretty much sounds like a typical database problem featuring a
single table with multiple indexes. One can wish-away the complexity
of a database but you will end-up re-inventing an in-memory, one-table
version of database.

===============
phonelist
===============
name idnumber
---- --------
ray 1234
josh 5423
carl 8674
tery 5409
greg 3402
mark 2108

tasks
-----
list names
list idnumbers
find idnumber=2108
find name=greg
del name=tery
update idnumber=4321 where name=ray
list sorted by name
list sorted by idnumber reversed
is name=john in phonelist
Now, extend the table to make it a trijection (three unique keys),
perhaps a social security number.
Now, extend the table to add a field that isn't unique (not a key
field), perhaps a person's favorite language.
Oh wait, you can't do that with a bijection API.
Now, forget the in-memory part and make it persistent on disk.
Now, relate the entries to another dictionary of tuples (i.e. another
table with foreign-key).
Too bad a DB wasn't used to solve a DB problem.


Raymond