combinat-0.2.8.2: Generate and manipulate various combinatorial objects.

Math.Combinat.Groups.Thompson.F

Description

Thompson's group F.

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

Synopsis

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 :: !Intthe width is the number of leaves, minus 1, of both diagrams_domain :: !Tthe top diagram correspond to the domain_range :: !Tthe bottom diagram corresponds to the range

Instances

 Source # Methods(==) :: TDiag -> TDiag -> Bool #(/=) :: TDiag -> TDiag -> Bool # Source # Methods(<) :: TDiag -> TDiag -> Bool #(<=) :: TDiag -> TDiag -> Bool #(>) :: TDiag -> TDiag -> Bool #(>=) :: TDiag -> TDiag -> Bool #max :: TDiag -> TDiag -> TDiag #min :: TDiag -> TDiag -> TDiag # Source # MethodsshowsPrec :: Int -> TDiag -> ShowS #show :: TDiag -> String #showList :: [TDiag] -> ShowS # Source # Methods Source # Methods

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

Creates a tree diagram from two trees

Creates a tree diagram, but does not reduce it.

The generator x0

The generator x1

The generators x0, x1, x2 ...

The identity element in the group F

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

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)

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

Reduction of tree diagrams

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

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.

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

 Source # Methodsfmap :: (a -> b) -> Tree a -> Tree b #(<\$) :: a -> Tree b -> Tree a # Source # Methods Eq a => Eq (Tree a) Source # Methods(==) :: Tree a -> Tree a -> Bool #(/=) :: Tree a -> Tree a -> Bool # Ord a => Ord (Tree a) Source # Methodscompare :: 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 # Show a => Show (Tree a) Source # MethodsshowsPrec :: Int -> Tree a -> ShowS #show :: Tree a -> String #showList :: [Tree a] -> ShowS # Source # Methods HasWidth (Tree a) Source # Methodswidth :: Tree a -> Int Source #

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

The monadic join operation of binary trees

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

A list version of graft

type T = Tree () Source #

A completely unlabelled binary tree

branch :: T -> T -> T Source #

treeWidth :: Tree a -> Int Source #

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

Enumerates the leaves a tree, starting from 0

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

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

"Right vine" of the given width

"Left vine" of the given width

flipTree :: Tree a -> Tree a Source #

Flips each node of a binary tree

Conversion to/from BinTree

toBinTree :: Tree a -> BinTree a Source #

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.

Pattern synonyms

pattern Lf :: Tree () Source #

pattern Br :: forall t. Tree t -> Tree t -> Tree t Source #

pattern Ct :: Tree () Source #

pattern X0 :: TDiag Source #

pattern X1 :: TDiag Source #

ASCII

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

asciiT' :: Bool -> T -> ASCII Source #

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

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

When the flag is true, we draw upside down

Draws a tree diagram