How to typecheck a general function

Question

I created a class that implements a generalized version of a BFS search:

from collections import deque


class NodeSolver:
    '''Class for modeling problems that can be modeled as a directed graph with goal nodes'''
    def __init__(self, namer, detector, expander, follower):
        '''
        Whatever decides to use this gets to define what structure info is.
        namer: takes info representing a node and returns a hashable object (the name);
               names must be equal if and only if the nodes are equal
        detector: takes info and returns True if the node represented by the info is the goal node,
                  ...False otherwise.
        expander: takes info and returns an iterable of moves that can be made from the node
                  ...that the info represents. (a.k.a. paths leading out of that node)
        follower: takes info and a move that can be made from the node that the info represents,
                  ...and returns the info that represents the node that the move leads to
        '''
        self.get_name = namer
        self.is_goal = detector
        self.get_moves = expander
        self.follow_move = follower


class BFSSolver(NodeSolver):
    '''Class for solving node problems with breadth-first-search to reach the goal node'''
    def solve(self, start_info):
        '''
        Returns the list of moves needed to reach the goal node
        ...from the node represented by the parameter.
        Uses Breadth-first Search to go through the node tree
        '''
        if self.is_goal(start_info):
            return []

        start_name = self.get_name(start_info)

        # data is in the form (info, path)
        name_to_data = {start_name: (start_info, [])}
        queue = deque()

        queue.appendleft(start_name)

        while queue:
            current_name = queue.pop()
            current_info, current_path = name_to_data[current_name]

            expanded_moves = self.get_moves(current_info)
            # print("possible moves from {} is {}".format(current_info, expanded_moves))
            for move in expanded_moves:
                child_info = self.follow_move(current_info, move)
                child_path = current_path[:]
                child_path.append(move)

                if self.is_goal(child_info):
                    return child_path

                child_name = self.get_name(child_info)
                if child_name not in name_to_data:
                    # new, needs to be expanded
                    name_to_data[child_name] = (child_info, child_path)
                    queue.appendleft(child_name)
        return None

The implementation of what counts as being info, a move, or a name, is all up to the person who uses the class.

However, once definitions have been decided on for those, then they should stay consistent. For example, info may be an Info object type the user creates. A move might just be an integer. A name might just be a string.

After these definitions are chosen, I want the type checker to be able to ensure that the user is sticking to those definitions.

How do I use type checking to accomplish something like this?

For now, I've done:

from collections import deque
from typing import Callable, Any, Iterable, List, Deque, Tuple, Dict, Optional, Hashable

# pylint: disable=invalid-name
# Type definitions

# Can be literally anything
Info = Any
Name = Hashable
# Can be literally anything
Move = Any
# pylint: enable=invalid-name

class NodeSolver:
    '''Class for modeling problems that can be modeled as a directed graph with goal nodes'''
    def __init__(self, namer: Callable[[Info], Name],
                 detector: Callable[[Info], bool],
                 expander: Callable[[Info], Iterable[Move]],
                 follower: Callable[[Info, Move], Info]):
        '''
        Whatever decides to use this gets to define what structure info is.
        namer: takes info representing a node and returns a hashable object (the name);
               names must be equal if and only if the nodes are equal
        detector: takes info and returns True if the node represented by the info is the goal node,
                  ...False otherwise.
        expander: takes info and returns an iterable of moves that can be made from the node
                  ...that the info represents. (a.k.a. paths leading out of that node)
        follower: takes info and a move that can be made from the node that the info represents,
                  ...and returns the info that represents the node that the move leads to
        '''
        self.get_name = namer
        self.is_goal = detector
        self.get_moves = expander
        self.follow_move = follower


class BFSSolver(NodeSolver):
    '''Class for solving node problems with breadth-first-search to reach the goal node'''
    def solve(self, start_info: Info) -> Optional[List[Move]]:
        '''
        Returns the list of moves needed to reach the goal node
        ...from the node represented by the parameter.
        Uses Breadth-first Search to go through the node tree
        '''
        if self.is_goal(start_info):
            return []

        start_name = self.get_name(start_info)

        # data is in the form (info, path)
        name_to_data: Dict[Name, Tuple[Info, List[Move]]] = {start_name: (start_info, [])}
        queue: Deque[Name] = deque()

        queue.appendleft(start_name)

        while queue:
            current_name = queue.pop()
            current_info, current_path = name_to_data[current_name]

            expanded_moves = self.get_moves(current_info)
            # print("possible moves from {} is {}".format(current_info, expanded_moves))
            for move in expanded_moves:
                child_info = self.follow_move(current_info, move)
                child_path = current_path[:]
                child_path.append(move)

                if self.is_goal(child_info):
                    return child_path

                child_name = self.get_name(child_info)
                if child_name not in name_to_data:
                    # new, needs to be expanded
                    name_to_data[child_name] = (child_info, child_path)
                    queue.appendleft(child_name)
        return None

However, I'm not sure how a class that uses this would be able to set those variables for type checking, and I'm also not sure what would happen if multiple classes used this class with differing definitions for Info, Move and Name.

Also, I'm getting errors about having Any all over the place.

What tool are you using to check types in your program? – Noctis Skytower Jun 06 '19 at 17:50 — Noctis Skytower, Jun 06 '19 at 17:50

score 3 · Accepted Answer · answered Jun 06 '19 at 18:04

Use TypeVars and generics:

from collections import deque
from typing import Callable, Any, Iterable, List, Deque, Tuple, Dict, Optional, Hashable, TypeVar, Generic


TInfo = TypeVar('TInfo')
TName = TypeVar('TName', bound=Hashable)
TMove = TypeVar('TMove')

class NodeSolver(Generic[TInfo, TName, TMove]):
    '''Class for modeling problems that can be modeled as a directed graph with goal nodes'''
    def __init__(self,
                 namer: Callable[[TInfo], TName],
                 detector: Callable[[TInfo], bool],
                 expander: Callable[[TInfo], Iterable[TMove]],
                 follower: Callable[[TInfo, TMove], TInfo]):
        self.get_name = namer
        self.is_goal = detector
        self.get_moves = expander
        self.follow_move = follower

def namer1(info: int) -> str: ...
def detector1(info: int) -> bool: ...
def expander1(info: int) -> Iterable[bool]: ...
def follower1(info: int, move: bool) -> int: ...

def namer2(info: str) -> int: ...
def detector2(info: str) -> bool: ...
def expander2(info: str) -> Iterable[float]: ...
def follower2(info: str, move: float) -> str: ...

solver1 = NodeSolver(namer1, detector1, expander1, follower1)
solver2 = NodeSolver(namer2, detector2, expander2, follower2)

reveal_type(solver1)  # Revealed type is 'test.NodeSolver[builtins.int*, builtins.str*, builtins.bool*]'
reveal_type(solver2)  # Revealed type is 'test.NodeSolver[builtins.str*, builtins.int*, builtins.float*]'

gibberish = NodeSolver(namer1, detector2, expander1, follower2)  # Cannot infer type argument 1 of "NodeSolver"
reveal_type(gibberish)                                           # Revealed type is 'test.NodeSolver[Any, Any, Any]'

The TypeVars essentially act as placeholders for inferred types and will parameterize your NodeSolver type.

How do I use these TypeVars in the `BFSSolver`? I'm getting errors like `Missing type parameters for generic type` — Pro Q, Jun 06 '19 at 21:56
Nevermind, I figured out that it's `BFSSolver(NodeSolver[GenericInfo, GenericName, GenericMove])` from [this](https://stackoverflow.com/questions/32650416/is-it-possible-to-inherit-from-class-with-generic-in-python) — Pro Q, Jun 06 '19 at 22:14

How to typecheck a general function

1 Answers1