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 <jhm...@xenops.com> 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/>)
>> 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<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<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<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>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>> --
>>>>>>>> Maria Mckinley
>>>>>>>> Software Developer with Bonus SysAdmin Experience
>>>>>>>> www.mariakathryn.net
>>>>>>>> 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>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>> --
>>>>> Maria Mckinley
>>>>> Software Developer with Bonus SysAdmin Experience
>>>>> www.mariakathryn.net
>>>>> 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>
>>>>
>>>>
>>>
>>>
>>> --
>>> Maria Mckinley
>>> Software Developer with Bonus SysAdmin Experience
>>> www.mariakathryn.net
>>> 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
