That is indeed what i was planning on doing next Jonathan, thanks. For anyone interested, I have written up what I have learned so far, plus a silly explanation about recursion, here:
http://www.mariakathryn.net/Blog/60 Please let me know if I got anything wrong! And thanks again for the help. cheers, Maria On Wed, Sep 4, 2013 at 3:05 PM, Jonathan Mark <[email protected]> wrote: > hi, I wasn't quite clear... > By "full name of the item" I meant the name like "plant" which was > inserted into the Trie in the first place. > So since you have this: > mytrie.add('plant',2) > Trie.items() should be yielding this: > ('plant', 2) > (rather than yielding a single char value). > > "prefix argument" was a general concept rather than being a specific thing. > If you think of the bottom level Trie that has the value 2 stored for > "plant": > That Trie does not know that the key is "plant", only that the last > character is "t". So it is going to be hard for its items() function to > yield "plant". > Therefore I was suggesting that the items() function could have an > additional argument, which is a prefix to be attached to all the strings > being yielded (where the "plan" part gets passed in). > > Hopefully that makes it clearer instead of more muddled, but let me know... > > Jonathan > > > On 09/04/2013 02:41 PM, Maria McKinley wrote: > >> Yes, that helps, thank you both. >> >> However, I don't understand what you mean by the full name of the item. >> So, >> in the visualizer, we can see that the instance is this: >> >> defaultdict(<class __main__.Trie at 0x1012a10>, {'p': <__main__.Trie >> instance at 0x1031290>}) >> >> Are you referring to something like this? If so, why is that preferable? I >> can see including the node.value, but that doesn't seem to be what you are >> talking about. >> Also, what is meant by a prefix argument? The only reference I can find to >> a prefix argument when I google is to do with emacs lisp, and that doesn't >> look applicable. >> >> thanks again, >> Maria >> >> >> On Wed, Sep 4, 2013 at 12:56 AM, Jonathan Mark <[email protected]> wrote: >> >> I think what is happening is: >>> >>> The visualizer makes it look like the stack is being re-created each time >>> an item is retrieved. >>> Indeed, a bunch of stack frames are being put on top of the stack, so in >>> that sense, the stack is being re-created. >>> However these frames are not new, they were previously removed from the >>> stack (when a "yield" was done) and saved away as part of the state of >>> the >>> generator objects. So the stack is just being efficiently put back to the >>> state it was in when the previous item was returned. (Well, fairly >>> efficiently.) >>> >>> Another way to explain the generator magic: "yield" causes the current >>> stack frame to be saved away so it can be resumed later. When the caller >>> requests another item, the stack frame returns to the top of the stack >>> and >>> continues running where it left off. If that stack frame was in the >>> process >>> of traversing a nested generator, then it will request another item in >>> turn, causing an additional saved frame to be added back onto the stack, >>> etc., until the whole stack is set up again. >>> >>> Your generator code looks really close to doing what you want... >>> I think Trie.items() should not do "yield char" though, it should yield >>> the full name of the item, or maybe a (name, value) pair. >>> This may mean adding a prefix argument to Trie.items() so the full name >>> will be available. >>> >>> Hope that helps, feel free to query more... >>> >>> Jonathan >>> >>> >>> On 09/04/2013 12:03 AM, Mark Harviston wrote: >>> >>> 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/<http://www.python.org/dev/**peps/pep-0380/> >>>> <http://www.**python.org/dev/peps/pep-0380/<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 < >>>> [email protected]> >>>> **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 < >>>>> [email protected]>****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 < >>>>>> [email protected] >>>>>> >>>>>> 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 < >>>>>>> [email protected]> 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 < >>>>>>>> [email protected]> 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<https://github.com/codedragon/**trie> >>>>>>>>> <https://github.com/**codedragon/trie<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 < >>>>>>>>> [email protected] >>>>>>>>> >>>>>>>>>> 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 < >>>>>>>>>> [email protected]> >>>>>>>>>> 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 < >>>>>>>>>> [email protected] >>>>>>>>>> >>>>>>>>>>> wrote: >>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> Have you tried defining __repr__? >>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> Joseph >>>>>>>>>>> >>>>>>>>>>> On Aug 29, 2013, at 7:56 PM, Maria McKinley < >>>>>>>>>>> [email protected]> >>>>>>>>>>> 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 < >>>>>>>>>>> [email protected]> 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 < >>>>>>>>>>>> [email protected]> 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 < >>>>>>>>>>>>> [email protected] >>>>>>>>>>>>> >>>>>>>>>>>>>> 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<http://en.wikipedia.org/wiki/**Trie#A_Python_version> >>>>>>>>>>>>>> <http://**en.wikipedia.org/wiki/Trie#A_**Python_version<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 >>>>>>>>>>>>>> [email protected] >>>>>>>>>>>>>> 1.206.724.2112 >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>> -- >>>>>>>>>>>>> Maria Mckinley >>>>>>>>>>>>> Software Developer with Bonus SysAdmin Experience >>>>>>>>>>>>> www.mariakathryn.net >>>>>>>>>>>>> www.linkedin.com/in/****mariamckinley<http://www.linkedin.com/in/**mariamckinley> >>>>>>>>>>>>> <http://www.**linkedin.com/in/mariamckinley<http://www.linkedin.com/in/mariamckinley> >>>>>>>>>>>>> > >>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>> -- >>>>>>>>>>> Maria Mckinley >>>>>>>>>>> Software Developer with Bonus SysAdmin Experience >>>>>>>>>>> www.mariakathryn.net >>>>>>>>>>> www.linkedin.com/in/****mariamckinley<http://www.linkedin.com/in/**mariamckinley> >>>>>>>>>>> <http://www.**linkedin.com/in/mariamckinley<http://www.linkedin.com/in/mariamckinley> >>>>>>>>>>> > >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>> -- >>>>>>>>>> Maria Mckinley >>>>>>>>>> Software Developer with Bonus SysAdmin Experience >>>>>>>>>> www.mariakathryn.net >>>>>>>>>> www.linkedin.com/in/****mariamckinley<http://www.linkedin.com/in/**mariamckinley> >>>>>>>>>> <http://www.**linkedin.com/in/mariamckinley<http://www.linkedin.com/in/mariamckinley> >>>>>>>>>> > >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>> -- >>>>>>>>> Maria Mckinley >>>>>>>>> Software Developer with Bonus SysAdmin Experience >>>>>>>>> www.mariakathryn.net >>>>>>>>> www.linkedin.com/in/****mariamckinley<http://www.linkedin.com/in/**mariamckinley> >>>>>>>>> <http://www.**linkedin.com/in/mariamckinley<http://www.linkedin.com/in/mariamckinley> >>>>>>>>> > >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>> -- >>>>>>> Maria Mckinley >>>>>>> Software Developer with Bonus SysAdmin Experience >>>>>>> www.mariakathryn.net >>>>>>> www.linkedin.com/in/****mariamckinley<http://www.linkedin.com/in/**mariamckinley> >>>>>>> <http://www.**linkedin.com/in/mariamckinley<http://www.linkedin.com/in/mariamckinley> >>>>>>> > >>>>>>> >>>>>>> >>>>>>> >>>>>> >>>>>> -- >>>>>> Maria Mckinley >>>>>> Software Developer with Bonus SysAdmin Experience >>>>>> www.mariakathryn.net >>>>>> www.linkedin.com/in/****mariamckinley<http://www.linkedin.com/in/**mariamckinley> >>>>>> <http://www.**linkedin.com/in/mariamckinley<http://www.linkedin.com/in/mariamckinley> >>>>>> > >>>>>> >>>>>> >>>>>> >>>>> >>>>> -- >>>>> Maria Mckinley >>>>> Software Developer with Bonus SysAdmin Experience >>>>> www.mariakathryn.net >>>>> www.linkedin.com/in/****mariamckinley<http://www.linkedin.com/in/**mariamckinley> >>>>> <http://www.**linkedin.com/in/mariamckinley<http://www.linkedin.com/in/mariamckinley> >>>>> > >>>>> >>>>> >>>>> >>>> >> >> -- Maria Mckinley Software Developer with Bonus SysAdmin Experience www.mariakathryn.net www.linkedin.com/in/mariamckinley
