Safe Haskell | None |
---|---|

Language | Haskell2010 |

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

- data TDiag = TDiag {}
- 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
- 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 :: forall t. Tree t -> Tree t -> Tree t
- 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

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

isValidTDiag :: TDiag -> Bool Source #

isPositive :: TDiag -> Bool Source #

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

# Binary trees

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

treeNumberOfLeaves :: Tree a -> Int Source #

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

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

# Conversion to/from BinTree

fromBinTree :: BinTree a -> Tree a Source #

# Pattern synonyms

# ASCII

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

Draws a binary tree; when the boolean flag is `True`

, we draw upside down

asciiTLabels :: T -> ASCII Source #

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

asciiTDiag :: TDiag -> ASCII Source #

Draws a tree diagram