Can you explain the following function?

Question

def a(n): return max([len(n)] + [a(i) for i in n]) if isinstance(n, list) else 0 

this was in my recent check and I just can't figure out what the list looks like. So basically this function was supposed to return the length of the largest list (which I accept based on the correct answers), I would understand that if it were not for this part of the function:

 + [a(i) for i in n]) 

when I see this part, it looks like it adds something to the length of the list that iterated. Can someone shed light on the purpose of this part? more specifically, the reason for the addition.

edit: so by looking at it more carefully .. it looks like a function puts the length of the first list into a list, then puts the length of the next list and returns max? ... how does it work?

Answer 1

This function calculates the length of the largest node in the tree (implemented as lists inside lists). Perhaps with a little renaming and a line, it will be clearer:

 def longest_list_in_tree(tree): if not isinstance(tree, list): return 0 # This is a leaf-value of the tree, it has "length 0" own_length = len(tree) longest_descendant_of_each_subtree = [ longest_list_in_tree(subtree) for subtree in tree ] return max([own_length] + longest_descendant_of_each_subtree) 

Answer 2

The purpose of the program is to find the length of the longest list in the list of lists. Suppose you pass a list of lists as input.

 b = [[1], [1, 2], [3], [[1, 2, 3], [1]]] 

Now, to find the length of the internal lists, you first need to iterate over the current list. But what if the original input itself is not a list? We return the length of the element as 0. This check is performed by this part.

 ... if isinstance(n, list) else 0 

if n not an instance of the list, we return 0. Now that we are sure that the current element is a list, we get the length of this list len(n) . Then we iterate over the list, like this

 [a(i) for i in n] 

we get each element n and recursively call a . Now, if the item is a list, it is expected that a(i) will return the length of the longest list. Thus, we collect all the lengths of the longest lists in each of the elements, create them as a list and combine them with a length of n . This concatenation is done using

 [len(n)] + [a(i) for i in n] 

we make a len(n) list, surrounding it with square brackets, and the + operator will add the lengths we get from all elements of n . So, with every call to the recursed function, we get something like this

 [length of current list, max length of sub elements in element 1 of n, max length of sub elements in element 2 of n, max length of sub elements in element 3 of n, ... ] 

then we will find the maximum of all these elements and return it to the caller.

To better understand this program, I created a decorator for registering inputs and corresponding outputs. This can help you better understand recursion.

 def logger(f): def wrapper(args, level): print "\t\t" * level + "Entered with input ", args temp = f(args, level) print "\t\t" * level + "Leaving with length", temp return temp return wrapper @logger def a(n, lev): return max([len(n)] + [a(i, lev+1) for i in n]) if isinstance(n, list) else 0 b = [[1], [1, 2], [3], [[1, 2, 3], [1]]] print a(b, 0) 

and the way out is

 Entered with input [[1], [1, 2], [3], [[1, 2, 3], [1]]] Entered with input [1] Entered with input 1 Leaving with length 0 Leaving with length 1 Entered with input [1, 2] Entered with input 1 Leaving with length 0 Entered with input 2 Leaving with length 0 Leaving with length 2 Entered with input [3] Entered with input 3 Leaving with length 0 Leaving with length 1 Entered with input [[1, 2, 3], [1]] Entered with input [1, 2, 3] Entered with input 1 Leaving with length 0 Entered with input 2 Leaving with length 0 Entered with input 3 Leaving with length 0 Leaving with length 3 Entered with input [1] Entered with input 1 Leaving with length 0 Leaving with length 1 Leaving with length 3 Leaving with length 4 4 

Answer 3

List values are a rather esoteric property of python and some other languages. This can confuse many people. However, the structure that they follow is incredibly simple and based on establishing a notation :

• A variable representing the elements of the input list in this case calls a recursive function call.
• List to work in this case n
• Optional predicate expression.
• An output expression that creates entries in the output list based on entries in the input list that satisfy the predicate.

The function will return the largest list / subscription size when n entered. Understanding the list contained in the max function call creates a list of all sizes of values ​​in the list (0 if it is not a list), using the recursive call on its own to traverse the sub-lists in the same way.

To help explain the code, you are writing another function to return the input array passed to the max function call to improve your understanding:

 def b(n): return [len(n)]+[b(i) for i in n] if isinstance(n,list) else 0 

Example:

 >>> x = [1,2,3,4,5,[1,2,3,4,5,6,7,8,9],7,[1,2,[1,2,3,4,5,6,7,8,9,10,11,12,13,14],4,5,6,[1,2]]] >>> a(x) 14 >>> b(x) [8, 0, 0, 0, 0, 0, [9, 0, 0, 0, 0, 0, 0, 0, 0, 0], 0, [7, 0, 0, [14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 0, 0, 0, [2, 0, 0]]] 

NB In response to your change, the + operator allows you to combine the two lists together. eg:.

 x = [a,b,c] y = [d,e,f] z = x + y; 

Answer 4

Let me break this for you:

 def a(n): '''return the largest length of a list or sublists in that list''' if isinstance(n, list): # if n is a list, return the max of the len of the list # for all subitems in the list, perform a(subitem) recursively. # so if a sublist is longer than the list, return the largest len. return max([len(n)] + [a(i) for i in n]) else: # that subitem isn't a list, so return 0, which won't factor into the max calc. return 0 

I would call a function like this:

 def max_len_list_of_lists(a_list): '''return the largest length of a list or sublists in that list''' ... 

Answer 5

Suppose n is a list with members, which can also be lists containing other lists, etc., this returns the length of the longest list. For example:

 a([2,3,4,5]) = 4 # [2,3,4,5] a([1, [2,3,4,5], 3]) = 4 # [2,3,4,5] a([1, [2,3,4,5], [3, [7,8,9,0,1]]]) = 5 # [7,8,9,0,1] 

Basically this is tail recursion, saying that the maximum length of all lists is the maximum among the length of the list passed as input and all its members, which are lists.

Run it with a few small examples to see why this is true.