Safe Haskell	Safe-Inferred
Language	Haskell2010

Math.Combinat.Groups.Thompson.F

Contents

Tree diagrams
Reduction of tree diagrams
Composition of tree diagrams
Subdivions
Binary trees
Conversion to/from BinTree
Pattern synonyms
ASCII

Description

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

Synopsis

data TDiag = TDiag {
- _width :: !Int
- _domain :: !T
- _range :: !T
}
mkTDiag :: T -> T -> TDiag
mkTDiagDontReduce :: T -> T -> TDiag
isValidTDiag :: TDiag -> Bool
isPositive :: TDiag -> Bool
isReduced :: TDiag -> Bool
x0 :: TDiag
x1 :: TDiag
xk :: Int -> TDiag
identity :: TDiag
positive :: T -> TDiag
inverse :: TDiag -> TDiag
equivalent :: TDiag -> TDiag -> Bool
reduce :: TDiag -> TDiag
treeCaretList :: T -> [Int]
removeCarets :: [Int] -> T -> T
compose :: TDiag -> TDiag -> TDiag
composeDontReduce :: TDiag -> TDiag -> TDiag
extensionToCommonTree :: T -> T -> ([T], [T])
subdivision1 :: T -> [Rational]
subdivision2 :: T -> [(Rational, Rational)]
data Tree a
- = Branch !(Tree a) !(Tree a)
- | Leaf !a
graft :: Tree (Tree a) -> Tree a
listGraft :: [Tree a] -> Tree b -> Tree a
type T = Tree ()
leaf :: T
branch :: T -> T -> T
caret :: T
treeNumberOfLeaves :: Tree a -> Int
treeWidth :: Tree a -> Int
enumerate_ :: Tree a -> Tree Int
enumerate :: Tree a -> (Int, Tree Int)
rightVine :: Int -> T
leftVine :: Int -> T
flipTree :: Tree a -> Tree a
toBinTree :: Tree a -> BinTree a
fromBinTree :: BinTree a -> Tree a
pattern Lf :: Tree ()
pattern Br :: Tree a -> Tree a -> Tree a
pattern Ct :: Tree ()
pattern X0 :: TDiag
pattern X1 :: TDiag
asciiT :: T -> ASCII
asciiT' :: Bool -> T -> ASCII
asciiTLabels :: T -> ASCII
asciiTLabels' :: Bool -> T -> ASCII
asciiTDiag :: TDiag -> ASCII

Tree diagrams

data TDiag Source #

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

Instances details

Show TDiag Source #
Instance details Defined in Math.Combinat.Groups.Thompson.F Methods showsPrec :: Int -> TDiag -> ShowS # show :: TDiag -> String # showList :: [TDiag] -> ShowS #
DrawASCII TDiag Source #
Instance details Defined in Math.Combinat.Groups.Thompson.F Methods ascii :: TDiag -> ASCII Source #
HasWidth TDiag Source #
Instance details Defined in Math.Combinat.Groups.Thompson.F Methods width :: TDiag -> Int Source #
Eq TDiag Source #
Instance details Defined in Math.Combinat.Groups.Thompson.F Methods (==) :: TDiag -> TDiag -> Bool # (/=) :: TDiag -> TDiag -> Bool #
Ord TDiag Source #
Instance details Defined in Math.Combinat.Groups.Thompson.F Methods compare :: TDiag -> TDiag -> Ordering # (<) :: TDiag -> TDiag -> Bool # (<=) :: TDiag -> TDiag -> Bool # (>) :: TDiag -> TDiag -> Bool # (>=) :: TDiag -> TDiag -> Bool # max :: TDiag -> TDiag -> TDiag # min :: TDiag -> TDiag -> TDiag #

mkTDiag :: T -> T -> TDiag Source #

Creates a tree diagram from two trees

mkTDiagDontReduce :: T -> T -> TDiag Source #

Creates a tree diagram, but does not reduce it.

isValidTDiag :: TDiag -> Bool Source #

isPositive :: TDiag -> Bool Source #

isReduced :: TDiag -> Bool Source #

x0 :: TDiag Source #

The generator x0

x1 :: TDiag Source #

The generator x1

xk :: Int -> TDiag Source #

The generators x0, x1, x2 ...

identity :: TDiag Source #

The identity element in the group F

positive :: T -> TDiag Source #

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

inverse :: TDiag -> TDiag Source #

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 Source #

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

Reduction of tree diagrams

reduce :: TDiag -> TDiag Source #

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

treeCaretList :: T -> [Int] Source #

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

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

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 Source #

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 Source #

Compose two tree diagrams without reducing the result

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

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] Source #

Returns the list of dyadic subdivision points

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

Returns the list of dyadic intervals

Binary trees

data Tree a Source #

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

Constructors

Branch !(Tree a) !(Tree a)
Leaf !a

Instances

Instances details

Functor Tree Source #
Instance details Defined in Math.Combinat.Groups.Thompson.F Methods fmap :: (a -> b) -> Tree a -> Tree b # (<$) :: a -> Tree b -> Tree a #
DrawASCII T Source #
Instance details Defined in Math.Combinat.Groups.Thompson.F Methods ascii :: T -> ASCII Source #
Show a => Show (Tree a) Source #
Instance details Defined in Math.Combinat.Groups.Thompson.F Methods showsPrec :: Int -> Tree a -> ShowS # show :: Tree a -> String # showList :: [Tree a] -> ShowS #
HasNumberOfLeaves (Tree a) Source #
Instance details Defined in Math.Combinat.Groups.Thompson.F Methods numberOfLeaves :: Tree a -> Int Source #
HasWidth (Tree a) Source #
Instance details Defined in Math.Combinat.Groups.Thompson.F Methods width :: Tree a -> Int Source #
Eq a => Eq (Tree a) Source #
Instance details Defined in Math.Combinat.Groups.Thompson.F Methods (==) :: Tree a -> Tree a -> Bool # (/=) :: Tree a -> Tree a -> Bool #
Ord a => Ord (Tree a) Source #
Instance details Defined in Math.Combinat.Groups.Thompson.F Methods compare :: Tree a -> Tree a -> Ordering # (<) :: Tree a -> Tree a -> Bool # (<=) :: Tree a -> Tree a -> Bool # (>) :: Tree a -> Tree a -> Bool # (>=) :: Tree a -> Tree a -> Bool # max :: Tree a -> Tree a -> Tree a # min :: Tree a -> Tree a -> Tree a #