Type in Python to implement algebraic extension (1) ~ Monoids, groups, rings, ring of integers ~

Introduction

Python 3.5 introduces the ** type hint ** feature, which makes you aware of types. However, you rarely see code with type hints. At first, I was skeptical that "Does Python need static typing?", But when I added a type hint to my code, "[oh my (py)!](Http: // blog) .zulip.org/2016/10/13/static-types-in-python-oh-mypy/) ", and I wanted to spread it, so I decided to write this article.

From now on, we will implement field extension in Python in three parts, using type hints. For implementation, I referred to the article "Introduction to Algebra with Swift" by taketo1024.

By the way, the author is not familiar with algebraic extension (as much as I read "Mathematics Girl / Galois Theory" by Hiroshi Yuki), so if there are any mistakes, I will tell you. I would appreciate it if you could.

Algebraic extension is carefully written in taketo1024's article and other web pages, so I won't go into much mathematical talk in this article, and let's focus on ** how to do it with Python **. I think.

Assumed readership

table of contents

  1. Monoid / group / ring / integer ring
  2. Field, rational number field, Euclidean ring, modulo ring, finite field
  3. Polynomial ring / quotient ring of polynomial / field extension

Python type hint feature

One of the bases of type hints is to write the code ** Function Annotation (PEP 3107) **. This is used to explain the arguments and return values of a function.

The following is an example of annotation taken from PEP 3107.

def compile(source: "something compilable",
            filename: "where the compilable thing comes from",
            mode: "is this a single statement or a suite?"):

The content of the function annotation does not affect the execution result of the program, but there are attempts to use the function annotation to inspect the code offline.

Since PEP 3107 does not specifically specify the content of annotations, various annotation styles may be scattered due to inspection tools. However, that would halve the benefits to the programmer, so from Python 3.5 ** type hints (PEP 484) ** A standardized framework called, has been introduced, and a related typing module is provided.

The following is an example annotation taken from PEP 484. For variables and strings, specify the class or type name instead of the description.

from typing import List
Vector = List[float]

def scale(scalar: float, vector: Vector) -> Vector:
    return [scalar * num for num in vector]

I will write it again, but the behavior of the program does not change or the annotation method is not forced depending on the annotation content. Also, it is not always necessary to follow this annotation method. However, standardization unifies the rules, and we can expect cooperation between programmers.

Inspection tool

Just because a type hint framework is in place doesn't mean that inspection tools are provided as part of Python, so you need to choose one. In this article, we will use ** mypy **, which is currently the de facto standard for PEP 484.

You can install mypy with the pip command as follows (note that it is mypy-lang, not mypy).

$ sudo pip3 install mypy-lang

Actual use will be done later in this article.

Implementation

Now let's make a "number".

Monoid

First is the monoid. A set that meets the following conditions is called a "monoid".

Closed for binary operation $ \ star $

  1. The associative law holds ($ x \ star (y \ star z) = (x \ star y) \ star z $)
  2. The identity element exists ($ e $ exists such that $ x \ star e = e \ star x = x $)

For example, natural numbers, real numbers, square matrices, etc. are monoids for "products". To express this in Python, first create a ** abstract base class ** for monoids. Add metaclass = ABCMeta to make it an abstract base class.

from abc import ABCMeta, abstractmethod

class Monoid(metaclass=ABCMeta):
    @abstractmethod
    def __mul__(self, x):
        pass

    @abstractmethod
    def identity(self):
        pass

    @abstractmethod
    def __eq__(self, x):
        pass

    def testAssociativity(self, a, b):
        return (self * a) * b == self * (a * b)

    def testIdentity(self):
        return self * self.identity() == self

Since we want all monoids to implement at least "binary operation $ \ star $", "identity element" and "equal", we declare an empty method with @abstractmethod decorator in the abstract base class. I will. As a result, ** if these three methods are not defined in the class that inherits Group, an error will occur during instantiation **.

The operation $ \ star $ substitutes for the Python operator *. To define the operator * for a class, define the __mul__ method. An instance of a class in which this operator is defined can be used to create an expression by connecting other objects with the * operator. For example:

class A(object):
    def __init__(self, data):
        self.data

    def __mul__(self, x):
        return self.data * x.data

a = A(5)
b = A(10)
print((a * b).data) # -> 50

When evaluating an expression, the connected objects are assigned to x in __mul__ and calculated, and the return value is the evaluation result of the expression. __eq__ corresponds to the operation==.

However, this alone does not represent that the monoid is ** closed ** for the operation $ \ star $. That's where the ** type hint ** comes in. Type hints can express the types of function arguments and return values **. Let's look at an example with type hints.

from typing import TypeVar

MonoidType = TypeVar("MonoidType", bound="Monoid")

class Monoid(metaclass=ABCMeta):
    @abstractmethod
    def __mul__(self: MonoidType, x: MonoidType) -> MonoidType:
        pass

    @abstractmethod
    def identity(self: MonoidType) -> MonoidType:
        pass

    @abstractmethod
    def __eq__(self, x): 
        pass

    def testAssociativity(self: MonoidType, a: MonoidType, b: MonoidType) -> bool:
        return (self * a) * b == self * (a * b)

    def testIdentity(self: MonoidType) -> bool:
        return self * self.identity() == self

Each argument of the function is followed by a : and a type signature. There is also a signature at the end of the def statement, following the-> . Here is a type hint.

Type hints allow you to give type information to function arguments, return values, and other variables. These are treated in the same way as comments when actually running the program, but they are useful information when using the type checker.

In each place, a variable called MonoidType is declared and used. This is called a ** type variable **, and variables annotated with the same type variable must be of the same type.

In the declaration of MonoidType,bound = "Monoid"is used. In this way, you can limit variables with MonoidType to instances of subclasses of Monoid.

Here, no type hint is given to __eq__. __eq__ is defined in ʻobject`, which is the basis of all classes, and if you give a different type hint, an error will occur.

group

A "group" is a monoid plus the inverse condition.

Closed for binary operation $ \ star $

  1. The associative law holds ($ x \ star (y \ star z) = (x \ star y) \ star z $)
  2. The identity element exists ($ e $ exists such that $ x \ star e = e \ star x = x $)
  3. There is an inverse element ($ x ^ {-1} $ exists such that $ x \ star x ^ {-1} = x ^ {-1} \ star x = e $)

The abstract base class of the group inherits the monoid, and the inverse element is defined by the method ʻinverse. In addition to defining the inverse element, it's a good idea to do the division definition truediv` here as well.

GroupType = TypeVar("GroupType", bound="Group")

class Group(Monoid, metaclass=ABCMeta):
    @abstractmethod
    def inverse(self: GroupType) -> GroupType:
        pass

    def __truediv__(self: GroupType, x: GroupType) -> GroupType:
        return self * x.inverse()

    def testInverse(self: GroupType) -> bool:
        return self * self.inverse() == self.identity()

Additive group

In particular, a set that forms a group for an operation called "additive group" is called an "additive group". Since the additive group assumes commutativity, we set four conditions as follows.

The operation $ \ oplus $ is closed and

  1. The associative law holds ($ x \ oplus (y \ oplus z) = (x \ oplus y) \ oplus z $)
  2. The identity element exists ($ x \ oplus 0 = 0 \ oplus x = x $ exists, $ 0 $ exists, zero element)
  3. Inverse element exists ($ -x $ exists such that $ x \ oplus (-x) = (-x) \ oplus x = 0 $, minus element)
  4. Commutative ($ x \ oplus y = y \ oplus x $)

Similar to the case of groups, but the code example is as follows. Instead of defining division in groups, define subtraction.

AdditiveGroupType = TypeVar("AdditiveGroupType", bound="AdditiveGroup")

class AdditiveGroup(metaclass=ABCMeta):

    @abstractmethod
    def __add__(self: AdditiveGroupType, x: AdditiveGroupType) -> AdditiveGroupType:
        pass

    @abstractmethod
    def zero(self: AdditiveGroupType) -> AdditiveGroupType:
        pass

    @abstractmethod
    def __neg__(self: AdditiveGroupType) -> AdditiveGroupType:
        pass

    def __sub__(self: AdditiveGroupType, x: AdditiveGroupType) -> AdditiveGroupType:
        return self + (-x)

    @abstractmethod
    def __eq__(self, x):
        pass

    def testAdditiveAssociativity(self: AdditiveGroupType, a: AdditiveGroupType, b: AdditiveGroupType) -> bool:
        return (self + a) + b == self + (a + b)

    def testZero(self: AdditiveGroupType) -> bool:
        return self + self.zero() == self

    def testNegative(self: AdditiveGroupType) -> bool:
        return self + (-self) == self.zero()

    def testAbelian(self: AdditiveGroupType, a: AdditiveGroupType) -> bool:
        return self + a == a + self

Looking at self + (-x), I realize once again that I am defining an operation.

ring

Groups and monoids set conditions for only one operation. The "ring" defines the conditions for two operations.

The operation $ \ star $ called multiplication and the operation $ \ oplus $ called addition are closed.

  1. Monoids about multiplication $ \ star $
  2. Abelian group for addition $ \ oplus $
  3. The distributive law holds between multiplication and addition ($ x \ star (y \ oplus z) = x \ star y \ oplus x \ star z $)

When defining a ring class, simply inherit the monoid and additive classes and implement the distributive law test code.

RingType = TypeVar("RingType", bound="Ring")

class Ring(Monoid, AdditiveGroup):
    def testDistributive(self: RingType, a: RingType, b: RingType) -> bool:
        return self * (a + b) == self * a + self * b

Ring of integers

You can finally implement the ring of integers. Inherit the abstract base class Ring of the ring and override the method declared in @ abstractmethod. Also, define the __repr__ method so that the contents of the ʻInteger` class can be displayed on the Python console.

If it is true, it would be nice if we could extend ʻint by writing only ʻidentity and zero, but unfortunately Python cannot do that, so we will define each method steadily.

class Integer(Ring):
    def __init__(self: "Integer", v: int) -> None:
        self.v = v

    def __repr__(self: "Integer") -> str:
        return str(self.v)

    def __mul__(self: "Integer", x: "Integer") -> "Integer":
        return Integer(self.v * x.v)

    def __add__(self: "Integer", x: "Integer") -> "Integer":
        return Integer(self.v + x.v)

    def __neg__(self: "Integer") -> "Integer":
        return Integer(-self.v)

    def __eq__(self, x):
        if not isinstance(x, Integer):
            return NotImplemented
        return self.v == x.v

    def identity(self: "Integer") -> "Integer":
        return Integer(1)

    def zero(self: "Integer") -> "Integer":
        return Integer(0)

Z = Integer

Now, let's use Z as an alias for ʻInteger`.

Each method specifies the ʻInteger type as a string. This is a forward reference because the definition of the ʻInteger class is not finished at the time of method definition. Use string literals instead of symbols when referencing forwards with type hints.

Analysis by mypy

After implementing the integer, let's check the code with mypy. To check, simply specify the file name in the mypy command and execute it.

$ mypy ./field_extension.py

If there are no problems, no error will be displayed. Now, let's try removing the __mul__ method from the ʻInteger` class and checking it.

$ mypy ./field_extension.py
field_extension.py:174: error: Cannot instantiate abstract class 'Integer' with abstract attribute '__mul__'
...

Rings for which multiplication is not defined will result in an error. This error will occur when you instantiate the ʻInteger` class without using mypy.

Next, let's change the argument type of the __mul__ method from ʻInteger to ʻint.

def __mul__(self: "Integer", x: int) -> "Integer":
    return Integer(self.v * x)

If you run mypy in this state, you will get an error that the types do not match.

$ mypy ./field_extension.py
field_extension.py: note: In class "Integer":
field_extension.py:91: error: Argument 1 of "__mul__" incompatible with supertype "Monoid"

At this point, we have abstracted the monoids, groups, and rings, and successfully implemented the ring of integers.

Next schedule

Next time, after touching on the field, I plan to make rational numbers, modulo rings, and finite fields.

Recommended Posts

Type in Python to implement algebraic extension (1) ~ Monoids, groups, rings, ring of integers ~
Type in Python to implement algebraic extension (3) ~ Polynomial ring / Polynomial quotient ring / Field extension ~
Type in Python to implement algebraic extension (2) ~ Field, rational number field, Euclidean ring, modulo ring, finite field ~
Implement the solution of Riccati algebraic equations in Python
Implement extension field in Python
I tried to implement blackjack of card game in Python
Reversible scrambling of integers in Python
Implement a deterministic finite automaton in Python to determine multiples of 3
I tried to implement PLSA in Python
I tried to implement permutation in Python
I tried to implement PLSA in Python 2
I tried to implement PPO in Python
[Introduction to Python] Thorough explanation of the character string type used in Python!
I tried to implement a card game of playing cards in Python
Try to implement Oni Maitsuji Miserable in python
[Python] How to use two types of type ()
How to implement Discord Slash Command in Python
Summary of how to import files in Python 3
Type Python scripts to run in QGIS Processing
How to implement shared memory in Python (mmap.mmap)
Summary of how to use MNIST in Python
Prime factorization of integers entered in Python ver.1
I tried to implement TOPIC MODEL in Python
How to get dictionary type elements of Python 2.7
Prime factorization ver.2 of integers input in Python
I tried to implement selection sort in python
How to handle datetime type in python sqlite3
I want to easily implement a timeout in python
Summary of tools needed to analyze data in Python
How to get the number of digits in Python
How to write a list / dictionary type of Python3
I tried to implement a pseudo pachislot in Python
I tried to implement GA (genetic algorithm) in Python
Convert Webpay Entity type to Dict type (recursively in Python)
[Python] I tried to get Json of squid ring 2
How to read csv containing only integers in Python
To do the equivalent of Ruby's ObjectSpace._id2ref in Python
Implement Enigma in python
Implement XENO in python
Implement Traceroute in Python 3
I tried to implement a one-dimensional cellular automaton in Python
Processing of python3 that seems to be usable in paiza
Python --Find out number of groups in the regex expression
How to develop in a virtual environment of Python [Memo]
Comparison of how to use higher-order functions in Python 2 and 3
How to implement Python EXE for Windows in Docker container
How to get a list of built-in exceptions in python
I tried to implement the mail sending function in Python
A story about trying to implement a private variable in Python.