Notation
Python implementation of the Overview/Notation
Sections
Powersets and Partition functions
Introduction
The code in this Python commentary can be executed by copying and pasting the code into a Python interpreter running the implementation in AlignmentPy repository. Start your favourite Python interpreter and then load the AlignmentDev module. For example,
cd Alignment
python
from AlignmentDev import *
The AlignmentDev module imports these modules,
from Alignment import *
from AlignmentSubstrate import *
from AlignmentApprox import *
from AlignmentRandom import *
from AlignmentPracticable import *
from AlignmentAeson import *
from AlignmentAesonPretty import *
The AlignmentDev module also implements a number of frequently used abbreviations.
The types and functions described in this section are defined in the AlignmentUtil module.
Note that the type declarations below are Haskell type declarations. They are only comments in the Python code.
Represent
The Alignment types implement a __str__ method which approximates to a set-theoretic representation of the structure. For example SortedSet is wrapped by sset,
xx = sset(range(-10,10+1))
xx
# {-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
And SortedDict is wrapped by sdict,
mm = sdict([(i,i*2) for i in range(1,5+1)])
mm
# {(1, 2), (2, 4), (3, 6), (4, 8), (5, 10)}
Fraction is wrapped by ratio,
ratio(Fraction(34,3))
34 % 3
AlignmentDev also defines a way to represent a list on separate lines,
rpln(mm.items())
# (1, 2)
# (2, 4)
# (3, 6)
# (4, 8)
# (5, 10)
Set-builder notation
The notation used throughout this discussion is conventional set-theoretic with some additions. Sets are often defined using set-builder notation, for example $Z = \{ \mathrm{f}(x) : x \in X,~\mathrm{p}(x) \}$ where $\mathrm{f}(x)$ is a function, $X$ is another set and $\mathrm{p}(x)$ is a predicate.
Tuples, or lists, can be defined similarly where the order is not important, for example, $\sum (\mathrm{f}(x) : x \in X,~\mathrm{p}(x))$. Python has a special syntax for list comprehensions,
def f(x):
return x**2
def p(x):
return -5 < x and x < 5
xx = sset(range(-10,10+1))
xx
# {-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
[f(x) for x in xx if p(x)]
# [16, 9, 4, 1, 0, 1, 4, 9, 16]
sum([f(x) for x in xx if p(x)])
60
zz = sset([f(x) for x in xx if p(x)])
zz
# {0, 1, 4, 9, 16}
sum(zz)
30
Powersets and Partition functions
The powerset function is defined as $\mathrm{P}(A) := \{X : X \subseteq A \}$,
setsPowerset :: Ord a => Set.Set a -> Set.Set (Set.Set a)
For example,
rpln(setsPowerset(sset([1,2,3])))
# {}
# {1}
# {1, 2}
# {1, 2, 3}
# {1, 3}
# {2}
# {2, 3}
# {3}
The partition function $\mathrm{B}$ is the set of all partitions of an argument set. A partition is a set of non-empty disjoint subsets, called components, which union to equal the argument, \[ \forall P \in \mathrm{B}(A)~\forall C\in P~(C \neq \emptyset) \] and \[ \forall P \in \mathrm{B}(A)~\forall C,D \in P~(C \neq D \implies C \cap D = \emptyset) \] and \[ \forall P \in \mathrm{B}(A)~(\bigcup P = A) \]
setsSetPartition :: Ord a => Set.Set a -> Set.Set (Set.Set (Set.Set a))
For example,
rpln(setsSetPartition(sset([1,2,3])))
# { {1}, {2}, {3} }
# { {1}, {2, 3} }
# { {1, 2}, {3} }
# { {1, 2, 3} }
# { {1, 3}, {2} }
A partition $P \in \mathrm{B}(A)$ is a parent of a partition $Q \in \mathrm{B}(A)$, if each component of $Q$ is a subset of a component in $P$, $\forall D \in Q~\exists C \in P~(D \subseteq C)$.
A parent partition is a decrement partition if it has one fewer components, $|P| = |Q| - 1$.
Relations
A relation $A \in \mathrm{P}(\mathcal{X} \times \mathcal{Y})$ between the set $\mathcal{X}$ and the set $\mathcal{Y}$ is a set of pairs, $\forall (x,y) \in A~(x \in \mathcal{X}~\wedge~y \in \mathcal{Y})$.
The domain of a relation is $\mathrm{dom}(A) := \{x : (x,y) \in A\}$ and the range is $\mathrm{ran}(A) := \{y : (x,y) \in A\}$,
relationsDomain :: (Ord a, Ord b) => Set.Set (a,b) -> Set.Set a
relationsRange :: (Ord a, Ord b) => Set.Set (a,b) -> Set.Set b
For example,
dom = relationsDomain
ran = relationsRange
rr = sset([(i,i*2) for i in range(1,5+1)])
rr
# {(1, 2), (2, 4), (3, 6), (4, 8), (5, 10)}
dom(rr)
# {1, 2, 3, 4, 5}
ran(rr)
# {2, 4, 6, 8, 10}
Functions
Functions are special cases of relations such that each element of the domain appears exactly once. Functions can be finite or infinite. For example, $\{(1,2),(2,4)\} \subset \{(x,2x) : x \in \mathbf{R}\}$. The powerset of functional relations between sets is denoted $\to$. For example, $\{(x,2x) : x \in \mathbf{R}\} \in \mathbf{R} \to \mathbf{R}$,
relationsIsFunc :: (Ord a) => Set.Set (a,b) -> Bool
For example,
isfunc = relationsIsFunc
rr = sset([(i,i*2) for i in range(1,5+1)])
isfunc(rr)
True
ss = sset([(i,i//2) for i in range(1,7+1)])
isfunc(ss)
True
isfunc(rr|ss)
False
The application of the function $F \in \mathcal{X} \to \mathcal{Y}$ to an argument $x \in \mathcal{X}$ is denoted by $F(x) \in \mathcal{Y}$ or $F_x \in \mathcal{Y}$.
Functions $F \in \mathcal{X} \to \mathcal{Y}$ and $G \in \mathcal{Y} \to \mathcal{Z}$ can be composed $G \circ F \in \mathcal{X} \to \mathcal{Z}$.
The inverse of a function, $\mathrm{inverse} \in (\mathcal{X} \to \mathcal{Y}) \to (\mathcal{Y} \to \mathrm{P}(\mathcal{X}))$, is defined $\mathrm{inverse}(F) := \{(y,\{x : (x,z) \in F,~z=y\}) : y \in \mathrm{ran}(F) \}$, and is sometimes denoted $F^{-1}$,
functionsInverse :: (Ord a, Ord b) => Map.Map a b -> Map.Map b (Set.Set a)
For example,
inv = functionsInverse
ff = sdict([(i,i*2) for i in range(1,5+1)])
inv(ff)
# {(2, {1}), (4, {2}), (6, {3}), (8, {4}), (10, {5})}
gg = sdict([(i,i//2) for i in range(1,7+1)])
inv(gg)
# {(0, {1}), (1, {2, 3}), (2, {4, 5}), (3, {6, 7})}
The range of the inverse is a partition of the domain, $\mathrm{ran}(F^{-1}) \in \mathrm{B}(\mathrm{dom}(F))$.
Functions may be recursive. Algorithms are represented as recursive functions.
The powerset of bijective relations, or one-to-one functions, is denoted $\leftrightarrow$. The cardinality of the domain of a bijective function equals the range, $F \in \mathrm{dom}(F) \leftrightarrow \mathrm{ran}(F) \implies |\mathrm{dom}(F)|= |\mathrm{ran}(F)|$.
Total functions are denoted with a colon. For example, the left total function $F \in X :\to Y$ requires that $\mathrm{dom}(F)=X$ but only that $\mathrm{ran}(F) \subseteq Y$.
Orders
An order $D$ on some set $X$ is a choice of the enumerations, $D \in X :\leftrightarrow: \{1 \ldots |X|\}$. Given the order, any subset $Y \subseteq X$ can be enumerated. Define $\mathrm{order}(D,Y) \in Y :\leftrightarrow: \{1 \ldots |Y|\}$ such that $\forall a,b \in Y~(D_a \leq D_b \implies \mathrm{order}(D,Y)(a) \leq \mathrm{order}(D,Y)(b))$.
Numbers
The set of natural numbers $\mathbf{N}$ is taken to include $0$. The set $\mathbf{N}_{>0}$ excludes $0$. The space of a non-zero natural number is the natural logarithm, $\mathrm{space}(n) := \ln n$. The set of rational numbers is denoted $\mathbf{Q}$. The set of log-rational numbers is denoted $\ln \mathbf{Q}_{>0} = \{\ln q : q \in \mathbf{Q}_{>0}\}$. The set of real numbers is denoted $\mathbf{R}$.
Factorial
The factorial of a non-zero natural number $n \in \mathbf{N}_{>0}$ is written $n! = \prod \{1 \ldots n\}$,
factorial :: Integer -> Integer
For example,
[factorial(i) for i in range(1,10+1)]
# [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
The unit-translated gamma function is the real function that corresponds to the factorial function. It is defined $(\Gamma_!) \in \mathbf{R} \to \mathbf{R}$ as $\Gamma_! x = \Gamma (x+1)$ which is such that $\forall n \in \mathbf{N}_{>0}~(\Gamma_! n = \Gamma (n+1) = n!)$. The log gamma function is defined in SciPy,
gammaln :: Double -> Double
For example,
def facln(x):
return gammaln(float(x) + 1)
[exp(facln(x)) for x in range(1,10+1)]
# [1.0, 2.0, 6.0, 24.000000000000004, 119.99999999999997, 720.0000000000001, 5040.000000000002, 40320.00000000002, 362879.9999999998, 3628800.0000000023]
[exp(facln(x/10)) for x in range(20,30+1)]
# [2.0, 2.197620278392477, 2.4239654799353683, 2.683437381955768, 2.9812064268103327, 3.3233509704478426, 3.717023853036792, 4.170651783796604, 4.694174205740422, 5.299329733809704, 6.0]
Aggregate functions
Given a relation $A \subset \mathcal{X} \times \mathcal{Y}$ such that an order operator is defined on the range, $\mathcal{Y}$, the $\mathrm{max}$ function returns the maximum subset, $\mathrm{max} \in \mathrm{P}(\mathcal{X} \times \mathcal{Y}) \to (\mathcal{X} \to \mathcal{Y})$ \[ \mathrm{max}(A) := \{(x,y) : (x,y) \in A,~\forall (r,s) \in A~(s \leq y)\} \] For convenience define the functions $\mathrm{maxd}(A) := \mathrm{dom}(\mathrm{max}(A))$ and $\mathrm{maxr}(A) := m$, where $\{m\} = \mathrm{ran}(\mathrm{max}(A))$. The corresponding functions for minimum, $\mathrm{min}$, $\mathrm{mind}$ and $\mathrm{minr}$, are similarly defined.
Given a relation $A \subset \mathcal{X} \times \mathcal{Y}$ such that the arithmetic operators are defined on the range, $\mathcal{Y}$, the $\mathrm{sum}$ function is defined $\mathrm{sum}(A) := \sum (y : (x,y) \in A)$,
relationsSum :: (Ord a, Ord b, Num b) => Set.Set (a,b) -> b
For example,
rr = sset([(i,ratio(i*2)) for i in range(1,10+1)])
ratio(relationsSum(rr))
# 110 % 1
The relation can be normalised, $\mathrm{normalise}(A) := \{(x,y/\mathrm{sum}(A)) : (x,y) \in A\}$. Define notation $\hat{A} := \mathrm{normalise}(A)$. A normalised relation is such that its sum is one, $\mathrm{sum}(\hat{A}) = 1$,
relationsNormalise :: (Ord a, Ord b, Fractional b) => Set.Set (a,b) -> Set.Set (a,b)
For example,
[(i,ratio(r)) for (i,r) in relationsNormalise(rr)]
# [(1, 1 % 55), (2, 2 % 55), (3, 3 % 55), (4, 4 % 55), (5, 1 % 11), (6, 6 % 55), (7, 7 % 55), (8, 8 % 55), (9, 9 % 55), (10, 2 % 11)]
ratio(relationsSum(relationsNormalise(rr)))
# 1 % 1
Probability functions
The set of probability functions $\mathcal{P}$ is the set of rational valued functions such that the values are bounded $[0,1]$ and sum to $1$, $\mathcal{P} \subset \mathcal{X} \to \mathbf{Q}_{[0,1]}$ and $\forall P \in \mathcal{P}~(\mathrm{sum}(P)=1)$. The normalisation of a positive rational valued function $F \in \mathcal{X} \to \mathbf{Q}_{\geq 0}$ is a probability function, $\hat{F} \in \mathcal{P}$.
The entropy of positive rational valued functions, $\mathrm{entropy} \in (\mathcal{X} \to \mathbf{Q}_{\geq 0}) \to \mathbf{Q}_{\geq 0} \ln \mathbf{Q}_{> 0}$, is defined as $\mathrm{entropy}(N) := -\sum (\hat{N}_x \ln \hat{N}_x : x \in \mathrm{dom}(N),~N_x > 0)$. The entropy of a singleton is zero, $\mathrm{entropy}(\{(\cdot,1)\}) = 0$,
entropy :: [Rational] -> Double
For example,
entropy([1,1,1,1,1])
1.6094379124341005
entropy([Fraction(1,5)]*5)
1.6094379124341005
entropy([1,2,3,4,5])
1.4897503188505912
entropy([1,1])
0.6931471805599453
entropy([1,2])
0.6365141682948128
entropy([1])
-0.0
Entropy is maximised in uniform functions as the cardinality tends to infinity, $\mathrm{entropy}(X \times \{1/|X|\}) = \ln |X|$,
[entropy([1]*i) for i in [1,2,3,4,5]]
# [-0.0, 0.6931471805599453, 1.0986122886681096, 1.3862943611198906, 1.6094379124341005]
[log(i) for i in [1,2,3,4,5]]
# [0.0, 0.6931471805599453, 1.0986122886681098, 1.3862943611198906, 1.6094379124341003]
Given some finite function $F \in \mathcal{X} \to \mathcal{Y}$, where $0 < |F| < \infty$, a probability function may be constructed from its distribution, $\{(y,|X|) : (y,X) \in F^{-1}\}^{\wedge} \in (\mathcal{Y} \to \mathbf{Q}_{\geq 0}) \cap \mathcal{P}$,
def inv(ll):
return slist(functionsInverse(sdict(ll)).items())
def norm(nn):
return [(i,ratio(r)) for (i,r) in relationsNormalise([(x,ratio(y)) for (x,y) in nn])]
ff = [(1,3),(2,1),(3,1),(4,1),(5,3),(6,2)]
rpln(inv(ff))
# (1, {2, 3, 4})
# (2, {6})
# (3, {1, 5})
rpln(norm([(y,len(xx)) for (y,xx) in inv(ff)]))
# (1, 1 % 2)
# (2, 1 % 6)
# (3, 1 % 3)
The probability function of an arbitrarily chosen finite function is likely to have high entropy,
def ent(nn):
return entropy([y for (_,y) in nn])
ent(norm([(y,len(xx)) for (y,xx) in inv(ff)]))
1.0114042647073518
gg = [(1,1),(2,1),(3,1),(4,1),(5,1),(6,2)]
rpln(inv(gg))
# (1, {1, 2, 3, 4, 5})
# (2, {6})
rpln(norm([(y,len(xx)) for (y,xx) in inv(gg)]))
# (1, 5 % 6)
# (2, 1 % 6)
ent(norm([(y,len(xx)) for (y,xx) in inv(gg)]))
0.45056120886630463
See Maximum Entropy for more discussion of probability functions and entropy.
A probability function $P(z) \in (X :\to \mathbf{Q}_{\geq 0}) \cap \mathcal{P}$, parameterised by some parameter $z \in Z = \mathrm{dom}(P)$, has a corresponding likelihood function $L(x) \in Z :\to \mathbf{Q}_{\geq 0}$, parameterised by coordinate $x \in X$, such that $L(x)(z) = P(z)(x)$. The maximum likelihood estimate $\tilde{z}$ of the parameter, $z$, at coordinate $x \in X$ is the mode of the likelihood function, \[ \begin{eqnarray} \{\tilde{z}\} &=& \mathrm{maxd}(L(x))\\ &=& \mathrm{maxd}(\{(z,P(z)(x)) : z \in Z\})\\ &=& \{z : z \in Z,~\forall z’ \in Z~(P(z)(x) \geq P(z’)(x))\} \end{eqnarray} \]
Lists
A list is a object valued function of the natural numbers $\mathcal{L}(\mathcal{X}) \subset \mathbf{N} \to \mathcal{X}$, such that $\forall L \in \mathcal{L}(\mathcal{X})~(L \neq \emptyset \implies \mathrm{dom}(L) = \{1 \ldots |L|\})$. Two lists $L,M \in \mathcal{L}(\mathcal{X})$ may be concatenated, $\mathrm{concat}(L,M) := L \cup \{(|L|+i,x) : (i,x) \in M\}$. Lists of type a are implemented in Python with the list type [a].
Trees
A tree is recursively defined as a tree valued function of objects, $\mathrm{trees}(\mathcal{X}) = \mathcal{X} \to \mathrm{trees}(\mathcal{X})$. In AlignmentUtil a Tree is defined as a Map.Map of any type a to a Tree of a,
data Tree a = Tree (Map.Map a (Tree a))
The nodes of the tree $T \in \mathrm{trees}(\mathcal{X})$ are $\mathrm{nodes}(T) := T \cup \bigcup \{\mathrm{nodes}(R) : (x,R) \in T\}$, and the elements are $\mathrm{elements}(T) := \mathrm{dom}(\mathrm{nodes}(T))$. The paths of a tree $\mathrm{paths}(T) \subset \mathcal{L}(\mathcal{X})$ is a set of lists. Given a set of lists $Q \subset \mathcal{L}(\mathcal{X})$ a tree can be constructed $\mathrm{tree}(Q) \in \mathrm{trees}(\mathcal{X})$,
treesNodes :: (Ord a, Ord (Tree a)) => Tree a -> Set.Set (a, Tree a)
treesElements :: (Ord a, Ord (Tree a)) => Tree a -> Set.Set a
treesPaths :: (Ord a, Ord (Tree a)) => Tree a -> Set.Set [a]
pathsTree :: (Ord a, Ord (Tree a)) => Set.Set [a] -> Tree a
For example,
tt = pathsTree([
[1,2],
[1,3],
[1,3,4],
[1,3,4,5,6,7],
[1],
[1,8],
[9]])
rpln(treesPaths(tt))
# [1, 2]
# [1, 3, 4, 5, 6, 7]
# [1, 8]
# [9]
tt
# {(1, {(2, {}), (3, {(4, {(5, {(6, {(7, {})})})})}), (8, {})}), (9, {})}
rpln(treesNodes(tt))
# (1, {(2, {}), (3, {(4, {(5, {(6, {(7, {})})})})}), (8, {})})
# (2, {})
# (3, {(4, {(5, {(6, {(7, {})})})})})
# (4, {(5, {(6, {(7, {})})})})
# (5, {(6, {(7, {})})})
# (6, {(7, {})})
# (7, {})
# (8, {})
# (9, {})
treesElements(tt)
# {1, 2, 3, 4, 5, 6, 7, 8, 9}