So, when I look at this code with the visualizer, it looks like the code is essentially re-creating the call stack every time through. Looking at the code structure, this sort of makes sense to me, since I think recursion with a generator means you are essentially creating a new generator every time through, so you are yielding to more and more generators each time through. But, it seems crazy. I thought the whole point of generators is that they remember where they were, so why is the whole stack being re-created every time? Or have I just totally mis-understood what is going on with the visualizer and/or the generator? Is there a better way to traverse the Trie? I did end up with this code by a strange route, so maybe the code is sub-optimal.
thanks for being patient with me, Maria On Sat, Aug 31, 2013 at 12:35 AM, Maria McKinley <mar...@mariakathryn.net>wrote: > Wow, okay, so that is a lot of recursion and generation for me to wrap my > brain around. > > I was trying to understand what was going on, and I put the code in a > visualizer, which you can see here: > > *http://tinyurl.com/orzrlh2* > > So, now I can almost wrap my brain around it. > > > On Fri, Aug 30, 2013 at 11:18 PM, Maria McKinley > <mar...@mariakathryn.net>wrote: > >> Yay! Thanks. Still working out exactly how to make it work how I want, >> but I feel like I'm getting the idea of how this is working now... I will >> post code when I have it working properly. >> >> ~maria >> >> >> On Fri, Aug 30, 2013 at 10:42 PM, Mark Harviston < >> mark.harvis...@gmail.com> wrote: >> >>> on line 94 you have >>> >>> >>> yield node.items() >>> >>> >>> this will yield node.items() which is itself a generator.... this is not >>> what you want to do. >>> >>> If it was Python 3, you could do: >>> >>> yield from node.items() >>> >>> >>> and that would be correct. >>> >>> Since it's Python 2, you have to do >>> >>> for i in node.items(): >>> yield i >>> >>> This will make the recursion work and iterate over the whole list. >>> >>> --Mark >>> >>> >>> On Fri, Aug 30, 2013 at 10:04 PM, Maria McKinley < >>> mar...@mariakathryn.net> wrote: >>> >>>> I'll assume as long as people are answering me, there is enough >>>> interest to keep going... >>>> >>>> I was having a problem seeing the representation of my object, but I >>>> did figure that out. I was able to print from the items method, and see >>>> that the code wasn't yielding the correct variable in order see the letter >>>> itself. >>>> >>>> Each time you add a word to the trie, it adds each letter of that word >>>> to a node. I have two words (that start with different letters) in my trie, >>>> so when I do the loop, I see the two letters at the top node. >>>> >>>> Weirdly, if I stick in letter.next() in the loop: >>>> >>>> for letters in mytrie.items(): >>>> print 'letters', letters >>>> letters.next() >>>> >>>> I do get the 2nd layer, but no more. If I try to do more, I get >>>> StopIteration. My biggest problem is I can't decide if the problem is my >>>> lack of understanding of generators or if this code is just not written >>>> correctly. Surely, it is suppose to be iterating through the entire tree, >>>> and not just the root level? How do I drill down to lower levels? I see how >>>> it is done for adding new words, but can't make something similar work for >>>> looking at unknown words. >>>> >>>> I have my code up here: >>>> >>>> https://github.com/codedragon/trie >>>> >>>> but it isn't a whole lot different from what is in the wikipedia >>>> article. Just has a script for playing around with it and some print >>>> statements stuck in. >>>> >>>> thanks again, >>>> Maria >>>> >>>> >>>> >>>> >>>> >>>> >>>> On Thu, Aug 29, 2013 at 9:49 PM, Joseph Wright <jos...@mammalia.net>wrote: >>>> >>>>> No, it wouldn't help with the iteration, but I thought you were having >>>>> a problem seeing the representation of your object. Now I'm trying to >>>>> figure this thing out…. >>>>> >>>>> It looks like the reason the 'char' only showing the first letter is >>>>> because in the add() method, the first letter of the string is what it >>>>> assigns to head: >>>>> >>>>> head, tail = s[0], s[1:] >>>>> >>>>> So it uses just one letter at a time per node. >>>>> >>>>> Joseph >>>>> >>>>> >>>>> On Aug 29, 2013, at 8:55 PM, Maria McKinley <mar...@mariakathryn.net> >>>>> wrote: >>>>> >>>>> Not yet, would that solve the problem that it is not iterating? Using >>>>> some good old-fashioned print statements, I found out a little bit more. >>>>> >>>>> I added the following print statements: >>>>> >>>>> for char, node in self.root.iteritems(): >>>>> # node.value is none when not at end of word >>>>> >>>>> if node.value is None: >>>>> print 'none' >>>>> print 'char',char >>>>> print 'node',node >>>>> yield node.items() >>>>> else: >>>>> print 'stuff' >>>>> yield node >>>>> >>>>> And this was the output. There are 2 words in the trie, but it only >>>>> reports the first letter of each word, and stops: >>>>> >>>>> none >>>>> char p >>>>> node <trie.Trie instance at 0x10e8d0560> >>>>> <generator object items at 0x10e8bc690> >>>>> none >>>>> char t >>>>> node <trie.Trie instance at 0x10e8bab48> >>>>> <generator object items at 0x10e8bc5a0> >>>>> >>>>> ~maria >>>>> >>>>> >>>>> On Thu, Aug 29, 2013 at 7:59 PM, Joseph Wright <jos...@mammalia.net>wrote: >>>>> >>>>>> Have you tried defining __repr__? >>>>>> >>>>>> Joseph >>>>>> >>>>>> On Aug 29, 2013, at 7:56 PM, Maria McKinley <mar...@mariakathryn.net> >>>>>> wrote: >>>>>> >>>>>> Thanks Morris. That does answer one question, I can't assume code on >>>>>> wikipedia is bug-free. Changing it doesn't solve the problem, >>>>>> unfortunately, but you are right, time to hit the debugger. Thanks >>>>>> everyone. >>>>>> >>>>>> cheers, >>>>>> Maria >>>>>> >>>>>> >>>>>> On Thu, Aug 29, 2013 at 5:46 PM, Morris Bernstein < >>>>>> mor...@systems-deployment.com> wrote: >>>>>> >>>>>>> I hate to suggest this because I almost never use it, but have you >>>>>>> considered using the pdb debugger and setting a breakpoint? >>>>>>> >>>>>>> Meanwhile, your problem is here: >>>>>>> def items(self): >>>>>>> """Return an iterator over the items of the `Trie`.""" >>>>>>> for char, node in self.root.iteritems(): >>>>>>> if node.value is None: >>>>>>> yield node.items >>>>>>> >>>>>>> node.items is the the Trie.items() method bound to the node object. >>>>>>> >>>>>>> I think, taking a quick look at the code, you want to yield >>>>>>> node.items(), function call again. Looks like the same problem. >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> On Thu, Aug 29, 2013 at 5:17 PM, Maria McKinley < >>>>>>> mar...@mariakathryn.net> wrote: >>>>>>> >>>>>>>> Doh. Thanks. This does the trick, but it gives me the instance >>>>>>>> location. I assumed this is because there is no __str__ method >>>>>>>> defined, but >>>>>>>> when I added a __str__ method it didn't change anything. Probably >>>>>>>> didn't >>>>>>>> implement the __str__ method correctly, but since I didn't even get an >>>>>>>> error, not sure this was even the problem. (Pretty sure, for example, >>>>>>>> that >>>>>>>> I shouldn't always be referencing the head node.) >>>>>>>> >>>>>>>> def __str__(self): >>>>>>>> return "Node letter is %s" % (self.root[0]) >>>>>>>> >>>>>>>> for c in mytrie.items(): >>>>>>>> print c >>>>>>>> ...: >>>>>>>> <bound method Trie.items of <trie.Trie instance at 0x1010dc710>> >>>>>>>> <bound method Trie.items of <trie.Trie instance at 0x1010dca70>> >>>>>>>> >>>>>>>> thanks again, >>>>>>>> Maria >>>>>>>> >>>>>>>> >>>>>>>> On Thu, Aug 29, 2013 at 4:40 PM, Cris Ewing <c...@crisewing.com>wrote: >>>>>>>> >>>>>>>>> I expect that the problem here is that you are attempting to >>>>>>>>> iterate over the method itself, rather than its result. You'd need >>>>>>>>> to call >>>>>>>>> the method to do that: >>>>>>>>> >>>>>>>>> for c in mytrie.items(): >>>>>>>>> print c >>>>>>>>> >>>>>>>>> hth >>>>>>>>> >>>>>>>>> c >>>>>>>>> >>>>>>>>> On Aug 29, 2013, at 4:38 PM, Maria McKinley wrote: >>>>>>>>> >>>>>>>>> Hello, >>>>>>>>> >>>>>>>>> I hope someone on this list doesn't mind answering what I think is >>>>>>>>> a quick question. I have been playing around with the python code >>>>>>>>> found >>>>>>>>> here: >>>>>>>>> >>>>>>>>> http://en.wikipedia.org/wiki/Trie#A_Python_version >>>>>>>>> >>>>>>>>> I can't get the iterator to work, and I wonder if I'm not calling >>>>>>>>> it correctly. I thought once I made my object, and added stuff to it, >>>>>>>>> I >>>>>>>>> could just do this: >>>>>>>>> >>>>>>>>> for c in mytrie.items: >>>>>>>>> print c >>>>>>>>> >>>>>>>>> but I get this error: >>>>>>>>> >>>>>>>>> TypeError: 'instancemethod' object is not iterable >>>>>>>>> >>>>>>>>> What am I doing wrong? >>>>>>>>> >>>>>>>>> thanks, >>>>>>>>> Maria >>>>>>>>> >>>>>>>>> >>>>>>>>> Cris Ewing >>>>>>>>> -------------------------------------------------- >>>>>>>>> Principal, Cris Ewing, Developer LLC >>>>>>>>> http://www.crisewing.com >>>>>>>>> c...@crisewing.com >>>>>>>>> 1.206.724.2112 >>>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> -- >>>>>>>> Maria Mckinley >>>>>>>> Software Developer with Bonus SysAdmin Experience >>>>>>>> www.mariakathryn.net >>>>>>>> www.linkedin.com/in/mariamckinley >>>>>>>> >>>>>>> >>>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> Maria Mckinley >>>>>> Software Developer with Bonus SysAdmin Experience >>>>>> www.mariakathryn.net >>>>>> www.linkedin.com/in/mariamckinley >>>>>> >>>>>> >>>>>> >>>>> >>>>> >>>>> -- >>>>> Maria Mckinley >>>>> Software Developer with Bonus SysAdmin Experience >>>>> www.mariakathryn.net >>>>> www.linkedin.com/in/mariamckinley >>>>> >>>>> >>>>> >>>> >>>> >>>> -- >>>> Maria Mckinley >>>> Software Developer with Bonus SysAdmin Experience >>>> www.mariakathryn.net >>>> www.linkedin.com/in/mariamckinley >>>> >>> >>> >> >> >> -- >> Maria Mckinley >> Software Developer with Bonus SysAdmin Experience >> www.mariakathryn.net >> www.linkedin.com/in/mariamckinley >> > > > > -- > Maria Mckinley > Software Developer with Bonus SysAdmin Experience > www.mariakathryn.net > www.linkedin.com/in/mariamckinley > -- Maria Mckinley Software Developer with Bonus SysAdmin Experience www.mariakathryn.net www.linkedin.com/in/mariamckinley
