On Jul 3, 12:56 am, Paul Rubin <http://phr...@nospam.invalid> wrote: > Simon Forman <sajmik...@gmail.com> writes: > > > Yes, but the concept of null pointers is considered kludgy these days. > > Seriously? "kludgy"? (I really AM getting old.) > > http://math.andrej.com/2009/04/11/on-programming-language-design/ > > discusses the issue (scroll down to "Undefined values" section).
Hmm, I'm not convinced. I read that post with interest, but his argument against None et. al. was just this: "...stick to the principle: NULL is wrong because it causes horrible and tricky mistakes which appear even after the program was tested thoroughly. You cannot introduce NULL into the language and tell the programmer to be careful about it. The programmer is not capable of being careful!" To me that seems weak and too general, you could say /anything/ "...causes horrible and tricky mistakes which appear even after the program was tested thoroughly." He does go on to say, in a reply to a comment, "In my opinion, at the end of the day the quality of the code depends more on the quality of its author than on the quality of the language he uses. But this does not mean that the quality of the programming language does not matter." Which I agree with wholeheartedly. I just don't see that he made a strong case that the inclusion of NULLs directly implies poor quality of language. (I like Haskell's Maybe, but saying A is better than B doesn't imply that B is therefore terrible.) > > Well I wouldn't know, I've been fortunate enough to program mostly in > > python for over half a decade now and None and 0 are as close as I've > > gotten to NULL in a long time. > > Right, and how many times have you had to debug > > AttributeError: 'NoneType' object has no attribute 'foo' > > or the equivalent null pointer exceptions in Java, C, or whatever? > They are very common. And the basic idea is that if you avoid using > null pointers in the first place, you'll get fewer accidental null > pointer exceptions. I have encountered exceptions like that, but usually as a result of e.g. omitting a return statement (so the caller gets None instead of whatever should have been returned.) I don't usually write "pointer" style code in python. In fact, other than this BTree and the Dancing Links algorithm I mentioned earlier I can't recall ever having done it. Indeed, python's omission of pointers is one of the reasons I'm so fond of it. In my experience with python exceptions like that one are indicators of something bad wrong with my code, not of misuse of None (as NULL pointer.) > > That sounds very interesting, but I'm only writing a BTree to then use > > it to play with "persistent data structures" > > But you have implemented a mutable tree. If you want to write a > persistent one, then write a persistent one! You also use a wishful The paper I'm working from is about general techniques for making persistent data structures from mutable forms, thus I wanted a mutable BTree to then "overwrite" with a persistent form. > heuristic in the hope of keeping the tree balanced--if you want a > balanced tree, why not use one that's guaranteed to stay in balance? > AVL trees are pretty easy to implement; maybe you could try writing a > persistent one: > > http://en.wikipedia.org/wiki/AVL_tree The balance (or lack thereof) of the tree is not important (in this use.) I threw in that heuristic in the delete function because it was easy enough and it was mentioned in the wikipedia article on BTrees. AVL trees are easy too, but still more complicated than I need. > > In this particular case it's somewhat more elegant (IMO) to check "is > > None". > > Well, I can't understand why that might be, but it's surely > subjective, so ok. It's a matter of this: if a is None: return b if b is None: return a # handle both non-None here... vs. this: if a is not None: if b is not None: # handle both non-None here... else: return a return b Everything is subjective, but I think the first one is more elegant IMO. > > > I'm sorry but I find that class rather ugly. The code would be a lot > > > smaller and have fewer corner cases with a different data representation. > > > Um, thanks? Seriously though, care to put your money where your mouth > > is? I'd be interested to see a BTree implemented as you indicated above. > > Er, I'm not trying to argue with you. You asked for people's advice > and impressions, so I gave you some. I don't feel like rewriting that I know, I asked for it. :] But it still stings a little to hear someone call my code "rather ugly". No hard feelings. I'm not trying to argue with you either. :] > whole class, but I'll do a method or two, using [] to represent an > empty node. (Hmm, actually changing the empty node representation did > less to shorten the code than just getting rid of a bunch of > duplication. Really, I'd tend to look for a slightly different tree > structure which tried to avoid these issues). Hmm, I really don't see that using an empty list rather than None as a stand-in for NULL pointer bought you anything there. In fact, this code would work identically if you replaced [] with None. I was hoping to see some clever code-fu involving list manipulation or something. When would you ever store a value in the empty list "nodes" anyway? > Untested: > > class BinaryTree: > def __init__(self, key, value): > self.key = key > self.value = value > self.higher = self.lower = [] > > def get(self, key): > if key == self.key: > return self.value > branch = self.lower if key < self.key else self.higher > return branch.get(key) if branch else [] > > def insert(self, key, value): > def xinsert(xtree): # xtree is either a tree or [] > if not xtree: xtree = BinaryTree(key, value) > else: xtree.insert(key, value) > return xtree > > if key == self.key: > self.value = value > elif key < self.key: > self.lower = xinsert(self.lower) > else: > self.higher = xinsert(self.higher) > > and so forth. -- http://mail.python.org/mailman/listinfo/python-list