Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Python - How do I write a more efficient, Pythonic reduce?

I'm trying to build a very lightweight Node class to serve as a Python-based hierarchy search tool. See the definition below.

from functools import reduce
from operator import or_


class Node:

    def __init__(self, name):
        self.name = name
        self.children = []

    def add_child(self, child_node):
        self.children.append(child_node)

    def contains(self, other_node):
        if self == other_node:
            return True
        elif other_node in self.children:
            return True
        else:
            return reduce(or_, [child.contains(other_node)
                                for child in self.children], False)

    def is_contained_by(self, other_node):
        return other_node.contains(self)

    def __eq__(self, other_node):
        return self.name == other_node.name

    def __de__(self, other_node):
        return self.name != other_node.name

contains seems to be a textbook case of functional programming (pulled directly from Why Functional Programming Matters).

Question: is there a more efficient or Pythonic way of writing contains? I know that map is usually replaced by list comprehension, but I hadn't seen a better way of doing reduce-based recursion.

Thanks,

Mike

===EDITED ... HERE'S THE REDONE CLASS TAKING INTO ACCOUNT THE ANSWER AND COMMENTS===

class Node:

    def __init__(self, name):
        self.name = name
        self.children = []

    def add_child(self, child_node):
        # Hattip to lazyr for catching this.
        if self.contains(child_node) or child_node.contains(self):
            raise TreeError('A relationship is already defined.')    
        else:
            self.children.append(child_node)                

    def contains(self, other_node):
        # Hattip to lazyr for pointing out any() and to Jochen Ritzel for
        # eliminating the silly child check.
        return (self == other_node or
                any(child.contains(other_node) for child in self.children))

    def is_contained_by(self, other_node):
        return other_node.contains(self)

    def __eq__(self, other_node):
        return self.name == other_node.name

    def __de__(self, other_node):
        return self.name != other_node.name

    def __repr__(self):
        return self.name
like image 645
MikeRand Avatar asked Mar 18 '11 14:03

MikeRand


People also ask

What can I use instead of reduce in Python?

So, if you're using Python 3.8 and product reduction is a common operation in your code, then you'll be better served by using math. prod() rather than Python's reduce() .

How do you make a function reduce in Python?

Reduce function is an inbuilt function in python whose major task is to give aggregate value as an output. Syntactically it is written as; reduce(func,iter_obj) here reduce operation will be done on “func” function and “iter_obj” is implying the iterable data values used to return result of output.

Why reduce is not totally recommended in Python 3?

The arguments against reduce are that it tends to be misapplied, harms readability and doesn't fit in with the non-functional orientation of Python. These are the sort of possible answers to OP's question as to why it was relegated to functools .

What does reduce () do in Python?

Reduce function in python allows us to perform reduction operations on iterables using python callables and lambda functions. reduce() applies a function to the items in an iterable and reduces them to a single cumulative value.


1 Answers

I think (not tested) that you instead of reduce should use any like this, which will stop on the first hit:

return any(child.contains(other_node) for child in self.children)

By the way, did you mean for a.contains(b) to return False when a == b and len(a.children) > 0?

Edit: If your tree contains a loop, like this:

a = Node("a")
b = Node("b")
a.add_child(a)
a.add_child(b)

then

a.contains(b)

will crash the program. You may want to check for this either in contains or in add_child, depending on which you use the most.

like image 51
Lauritz V. Thaulow Avatar answered Sep 25 '22 02:09

Lauritz V. Thaulow