This may be an artifact of for .. in .. yield vs a yield from. I don't have too much experience with the visualizer (I usually use pdb to step through code if I need to).
yield from is the "correct" way to call a generator from another generator and yield the other generators results. (but it only works on Python 3), and it does a better job of traversing the call-stack. PEP 380 (http://www.python.org/dev/peps/pep-0380/) has decent information on yield from, though it's a bit technical. For a Trie or any Tree, traversing would have to be done this way or perhaps with visitor/walker pattern. as in trie.walk(lambda node: print(node)), but that isn't very Pythonic. Look up tree traversals (pre-order, post-order, in-order, etc.), they all use recursion somehow. On Tue, Sep 3, 2013 at 11:41 PM, Maria McKinley <mar...@mariakathryn.net>wrote: > 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 >
