[Tutor] Fwd: treeTraversal, nested return?

[Matthew Wood]

Gah, hit the reply button instead of reply-all.  :-(

--

I enjoy haiku
but sometimes they don't make sense;
refrigerator?


---------- Forwarded message ----------
From: Matthew Wood <woodm1979 at gmail.com>
Date: Wed, Jun 9, 2010 at 2:30 PM
Subject: Re: [Tutor] treeTraversal, nested return?
To: jjcrump at uw.edu


Well, I've taken a look at your code.  In your last example, the appending
last line here:

>     else:
>        for x in getWorks(id):
>           result.extend(makeNestedLists(x[1]))

uses, a list.extend call.  If you switch that to append, you SHOULD see the
result you're looking for.  ...at least as best I can guess without
replicating the code and having some good test cases.


Here's some of your other questions:

>To my surprise, I say, because it looks like it shouldn't work at all
>with the result being set to the empty list with each recursion;

Each time you call the function 'makeNestedLists' a new copy of all the
local variables is created.  Thus, you aren't blanking the 'result' list
each time; instead you're creating a new list each time.  Then, when you
return the list, you then shove it into the parent-function-instance list.

Just take care to understand the difference between:

[1, 2, 3].append([4, 5, 6])  -> [1, 2, 3, [4, 5, 6]]
[1, 2, 3].extend([4, 5, 6]) -> [1, 2, 3, 4, 5, 6]

Your list comprehension example above adds an extra list wrapper around
things, which is why the extend worked.



--

I enjoy haiku
but sometimes they don't make sense;
refrigerator?


On Wed, Jun 9, 2010 at 12:40 PM, <jjcrump at uw.edu> wrote:

> Thanks to Matthew and Denis for trying to enlighten me. Thanks to your
> clues I've made some progress; however, I can't seem to get the hang of the
> usual recursion trick of keeping track of the level one is on. It doesn't
> work, I suppose, because the data structure I'm traversing isn't actually
> nested, its a flat series of lists of tuples.
>
> I did finally get a function to traverse the "tree-like" data coming from
> the db
>
> getRecord() returns a tuple of record-type, record-id, parent-id, and
> title, thus:
> ('work', 47302, 47301, 'record title')
>
> getImages(id) returns a list of 'image' tuples whose parent-id is id
> getWorks(id) returns a list of 'work' tuples whose parent-id is id
>
> works can be nodes, images can't
>
> so:
>
>   def makeDecendentList(id, result):
>      result.append(getRecord(id))
>      if getImages(id):
>         for x in getImages(id):
>            result.append(x)
>      if not getWorks(id):
>         return
>      else:
>         for y in getWorks(id):
>            makeDecendentList(y[1],result)
>      return result
>
> called with the empty list as the second argument.
>
> Well and good. This walks the 'tree' (following the parent-ids) and returns
> me a list of all the decendents of id. But what I wanted was a nested data
> structure.
>
> In the fashion of an ape given a typewriter and sufficient time, I trial
> and errored my way to this:
>
>   def makeNestedLists(id):
>      result = []
>      result.append(getRecord(id))
>      result.extend(getImages(id))
>      if not getWorks(id):
>         return result
>      else:
>         result.extend([makeNestedLists(x[1]) for x in getWorks(id)])
>      return result
>
> To my surprise, this gets me exactly what I wanted, eg:
>
>   [  ('work', 47301, 47254, 'a title'),
>      ('image', 36871, 47301, 'a title'),
>      ('image', 36872, 47301, 'a title'),
>      [  ('work', 47302, 47301, 'a title'),
>         ('image', 10706, 47302, 'a title'),
>         ('image', 10725, 47302, 'a title')
>      ]
>   ]
>
> To my surprise, I say, because it looks like it shouldn't work at all with
> the result being set to the empty list with each recursion; moreover, if I
> spell out the loop in the list comp like this:
>
>   def makeNestedLists(id):
>      result = []
>      result.append(getRecord(id))
>      result.extend(getImages(id))
>      if not getWorks(id):
>         return result
>      else:
>         for x in getWorks(id):
>            result.extend(makeNestedLists(x[1]))
>      return result
>
> I once again get a flat list of all the decendents of id.
>
> I know it's sad, but can any wise tutor explain to me what's going on in
> the code that I myself wrote?
>
> Thanks,
> Jon
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20100609/bd3de101/attachment.html>