I leave you with a Python question – Zhihu column

The first two days of Python thinking questions, give you a reference answer – Zhihu column

hubo1016/pychecktype

Some time ago out of a type checking function of the question, and reference answers. Sometimes when you write something that’s a little bit generic, you start thinking about how to make it more extensible and easy to use.

Before our algorithm has solved the recursive structure (from a reference of all sorts of problems, we are in the previous stage will be the problem as a mathematical problem, this can be regarded as “technology”, but not enough “engineering”, if someone wants to take advantage of this algorithm, we must have more in-depth knowledge of the whole algorithm, according to the principle of the need to implement its function. Engineering, on the other hand, requires users to have minimal knowledge of the algorithm in order to take full advantage of it. To do this, we need a deeper abstraction of both the problem and the algorithm.

———————————————————————————————–

Our previous algorithm implemented support for recursive structures of list and dict types, and now we want to generalize it to generic recursive data structures. Let’s begin by abstracting the problem further:

We have data V and data type T, and the result of the transformation is represented as f(V, T). Unfortunately, the process of calculating f(V, T) directly may come back to depend on f(V, T). Fortunately, f(V, T) is a pure function that always returns the same result for the same data and type.

————————————————————————————————

We have two main strategies for solving this problem:

  1. Generate a recursive structure, as in [] and {} : first create an empty structure and store it, then recurse, and if f(V, T) is encountered during recursion, create the recursive structure by returning the presaved reference directly.
  2. Disallow self-referencing, as is the case when converting a scalar to a list of only one element: if f(V, T) is directly recalled without any other recursive structure, it fails

Both cases boil down to the following process:

  1. Preparation – For recursive structures, create empty structures and coexist them; For forbidden recursion, save the forbidden recursion flag
  2. Recursion – Begins a recursive calculation, and if a token is encountered in the recursion it is processed accordingly (straight return or failure)

———————————————————————————————–

With that done, we then extract an engineering-oriented extension interface for the algorithm that requires minimal knowledge of the algorithm. Looking back at the conclusion above, the handling of tags is fixed and only needs to be extended:

  1. How to create an empty structure (or not, i.e. no self-reference)
  2. How do I recurse

Our interface is designed to do just that, which is the abstraction of the type-checking process in Answer 2.0:

class CustomizedChecker(object):
    """
    Inherit from this class to create a customized type checker
    """
    def __init__(self, *args, **kwargs):
        """
        Call bind()
        """
        if args or kwargs:
            self.bind(*args, **kwargs)
    def bind(self):
        """
        Allow delayed init
        """
        pass
    def pre_check_type(self, value):
        """
        First-step check for value. This step should not do any recursive check.
        
        :param value: value to be checked
        
        :return: An object if recursive creation if needed, or None if not needed.
                 TypeMismatchException should be raised if there is something wrong.
        """
        return None
        
    def final_check_type(self, value, current_result, recursive_check_type):
        """
        Second-step check for value. This step can use recursive check.
        
        :param value: value to be checked
        
        :param current_result: value returned by pre_check_type. If this value is not None, the return value must be the same object.
        
        :param recursive_check_type: a function recursive_check_type(value, type) to be called to do recursive type check
        """
        raise NotImplementedErrorCopy the code

There are two important processes here: pre_check_type and final_check_type. The parameter of pre_check_type is straightforward, which is the value to be checked. Recursive checks are not allowed during this process.

  1. If the type supports recursion, an empty structure is created and the newly created object is returned.
  2. Otherwise, None is returned, indicating that direct recursion is not supported

Current_result is the return value of pre_check_type. If pre_check_type returns an object other than None, The procedure should modify the object and return the same reference; Otherwise a new object should be returned. Recursive_check_type is a recursive_check_type function that performs recursive type checks and conversions. In this function, self-referential or self-referential logic is automatically handled. The implementation details are enclosed in a closure called RECURsive_check_type. This makes it very easy to extend a type.

After this step, we can subclass the CustomizedChecker from dict and list, and the logic in the main function is much cleaner:

def _customized_check(checker):
        if check_id in list_loop:
            raise TypeMismatchException(value, type_)
        current_result = checker.pre_check_type(value)
        if current_result is None:
            # Prevent an infinite loop
            list_loop.add(check_id)
            try:
                current_result = checker.final_check_type(value, None, lambda value, type: _check_type_inner(value, type, _recursive_check))
            finally:
                list_loop.discard(check_id)
        else:
            current_check[check_id] = current_result
            # backup succedded check: it may depends on current result. If the type match fails, revert all succeeded check
            _new_recursive_check = (current_check, dict(succeded_check), failed_check, set())
            checker.final_check_type(value, current_result, lambda value, type: _check_type_inner(value, type, _new_recursive_check))
            # copy succeeded checks
            succeded_check.clear()
            succeded_check.update(_new_recursive_check[1])                
return current_resultCopy the code

With the new engineering oriented interface, you don’t have to worry about doing things wrong when doing custom extensions.

To what extent does the new version extend its functionality? There is an example in the code that can examine a single linked list and convert it to a two-way list… This is not the limit, in fact it can also convert multi-fork trees to binary trees (children to left subtrees, brothers to right subtrees), edge lists to adjacency lists, recursive structures to non-recursive structures with ids, and so on…

It’s basically a new programming language.