Math.Combinat.Groups.Thompson.F

Thompson's group F.

See eg. https://en.wikipedia.org/wiki/Thompson_groups

Based mainly on James Michael Belk's PhD thesis "THOMPSON'S GROUP F"; see http://www.math.u-psud.fr/~breuilla/Belk.pdf

Tree diagrams

data TDiag

A tree diagram, consisting of two binary trees with the same number of leaves, representing an element of the group F.

Constructors

TDiag

Fields

_width :: !Int

the width is the number of leaves, minus 1, of both diagrams

_domain :: !T

the top diagram correspond to the domain

_range :: !T

the bottom diagram corresponds to the range

Instances

Eq TDiag

Ord TDiag

Show TDiag

HasWidth TDiag

DrawASCII TDiag

mkTDiag :: T -> T -> TDiag

Creates a tree diagram from two trees

mkTDiagDontReduce :: T -> T -> TDiag

Creates a tree diagram, but does not reduce it.

isValidTDiag :: TDiag -> Bool

isPositive :: TDiag -> Bool

isReduced :: TDiag -> Bool

x0 :: TDiag

The generator x0

x1 :: TDiag

The generator x1

xk :: Int -> TDiag

The generators x0, x1, x2 ...

identity :: TDiag

The identity element in the group F

positive :: T -> TDiag

A positive diagram is a diagram whose bottom tree (the range) is a right vine.

inverse :: TDiag -> TDiag

Swaps the top and bottom of a tree diagram. This is the inverse in the group F. (Note: we don't do reduction here, as this operation keeps the reducedness)

equivalent :: TDiag -> TDiag -> Bool

Decides whether two (possibly unreduced) tree diagrams represents the same group element in F.

Reduction of tree diagrams

reduce :: TDiag -> TDiag

Reduces a diagram. The result is a normal form of an element in the group F.

treeCaretList :: T -> [Int]

List of carets at the bottom of the tree, indexed by their left edge position

removeCarets :: [Int] -> T -> T

Remove the carets with the given indices (throws an error if there is no caret at the given index)

Composition of tree diagrams

compose :: TDiag -> TDiag -> TDiag

If diag1 corresponds to the PL function f, and diag2 to g, then compose diag1 diag2 will correspond to (g.f) (note that the order is opposite than normal function composition!)

This is the multiplication in the group F.

composeDontReduce :: TDiag -> TDiag -> TDiag

Compose two tree diagrams without reducing the result

extensionToCommonTree :: T -> T -> ([T], [T])

Given two binary trees, we return a pair of list of subtrees which, grafted the to leaves of the first (resp. the second) tree, results in the same extended tree.

Subdivions

subdivision1 :: T -> [Rational]

Returns the list of dyadic subdivision points

subdivision2 :: T -> [(Rational, Rational)]

Returns the list of dyadic intervals

Binary trees

data Tree a

A (strict) binary tree with labelled leaves (but unlabelled nodes)

Constructors

Branch !(Tree a) !(Tree a)

Leaf !a

Instances

Functor Tree

DrawASCII T

Eq a => Eq (Tree a)

Ord a => Ord (Tree a)

Show a => Show (Tree a)

HasNumberOfLeaves (Tree a)

HasWidth (Tree a)

graft :: Tree (Tree a) -> Tree a

The monadic join operation of binary trees

listGraft :: [Tree a] -> Tree b -> Tree a

A list version of graft

type T = Tree ()

A completely unlabelled binary tree

leaf :: T

branch :: T -> T -> T

caret :: T

treeNumberOfLeaves :: Tree a -> Int

treeWidth :: Tree a -> Int

The width of the tree is the number of leaves minus 1.

enumerate_ :: Tree a -> Tree Int

Enumerates the leaves a tree, starting from 0

enumerate :: Tree a -> (Int, Tree Int)

Enumerates the leaves a tree, and also returns the number of leaves

rightVine :: Int -> T

"Right vine" of the given width

leftVine :: Int -> T

"Left vine" of the given width

flipTree :: Tree a -> Tree a

Flips each node of a binary tree

Conversion to/from BinTree

toBinTree :: Tree a -> BinTree a

Tree and BinTree are the same type, except that Tree is strict.

TODO: maybe unify these two types? Until that, you can convert between the two with these functions if necessary.

fromBinTree :: BinTree a -> Tree a

Pattern synonyms

pattern Lf :: Tree ()

pattern Br :: Tree t -> Tree t -> Tree t

pattern Ct :: Tree ()

pattern X0 :: TDiag

pattern X1 :: TDiag

ASCII

asciiT :: T -> ASCII

Draws a binary tree, with all leaves at the same (bottom) row

asciiT' :: Bool -> T -> ASCII

Draws a binary tree; when the boolean flag is True, we draw upside down

asciiTLabels :: T -> ASCII

Draws a binary tree, with all leaves at the same (bottom) row, and labelling the leaves starting with 0 (continuing with letters after 9)

asciiTLabels' :: Bool -> T -> ASCII

When the flag is true, we draw upside down

asciiTDiag :: TDiag -> ASCII

Draws a tree diagram