Multi-way Trees and Forests

The Tree a type represents a lazy, possibly infinite, multi-way tree (also known as a rose tree). The Forest a type represents a forest of Tree as.

Warning: This API is experimental.

NOTE: This module is preliminary and may change at a future date. This module is intended to help converting a list of tags into a tree of tags.

Tree-based implementation of Graph and DynGraph You will probably have better performance using the Data.Graph.Inductive.PatriciaTree implementation instead.

The GTree struct is an opaque data structure representing a [balanced binary tree][glib-Balanced-Binary-Trees]. It should be accessed only by using the following functions.

This module provides functions to parse an XML document to a tree structure, either strictly or lazily. The GenericXMLString type class allows you to use any string type. Three string types are provided for here: String, ByteString and Text. Here is a complete example to get you started:

-- | A "hello world" example of hexpat that lazily parses a document, printing
-- it to standard out.

import Text.XML.Expat.Tree
import Text.XML.Expat.Format
import System.Environment
import System.Exit
import System.IO
import qualified Data.ByteString.Lazy as L

main = do
args <- getArgs
case args of
[filename] -> process filename
otherwise  -> do
hPutStrLn stderr "Usage: helloworld <file.xml>"
exitWith $ ExitFailure 1

process :: String -> IO ()
process filename = do
inputText <- L.readFile filename
-- Note: Because we're not using the tree, Haskell can't infer the type of
-- strings we're using so we need to tell it explicitly with a type signature.
let (xml, mErr) = parse defaultParseOptions inputText :: (UNode String, Maybe XMLParseError)
-- Process document before handling error, so we get lazy processing.
L.hPutStr stdout $ format xml
putStrLn ""
case mErr of
Nothing -> return ()
Just err -> do
hPutStrLn stderr $ "XML parse failed: "++show err
exitWith $ ExitFailure 2

Error handling in strict parses is very straightforward - just check the Either return value. Lazy parses are not so simple. Here are two working examples that illustrate the ways to handle errors. Here they are: Way no. 1 - Using a Maybe value

import Text.XML.Expat.Tree
import qualified Data.ByteString.Lazy as L
import Data.ByteString.Internal (c2w)

-- This is the recommended way to handle errors in lazy parses
main = do
let (tree, mError) = parse defaultParseOptions
(L.pack $ map c2w $ "<top><banana></apple></top>")
print (tree :: UNode String)

-- Note: We check the error _after_ we have finished our processing
-- on the tree.
case mError of
Just err -> putStrLn $ "It failed : "++show err
Nothing -> putStrLn "Success!"

Way no. 2 - Using exceptions parseThrowing can throw an exception from pure code, which is generally a bad way to handle errors, because Haskell's lazy evaluation means it's hard to predict where it will be thrown from. However, it may be acceptable in situations where it's not expected during normal operation, depending on the design of your program.

...
import Control.Exception.Extensible as E

-- This is not the recommended way to handle errors.
main = do
do
let tree = parseThrowing defaultParseOptions
(L.pack $ map c2w $ "<top><banana></apple></top>")
print (tree :: UNode String)
-- Because of lazy evaluation, you should not process the tree outside
-- the 'do' block, or exceptions could be thrown that won't get caught.
`E.catch` (\exc ->
case E.fromException exc of
Just (XMLParseException err) -> putStrLn $ "It failed : "++show err
Nothing -> E.throwIO exc)

Provides a simple data structure mirroring a directory tree on the filesystem, as well as useful functions for reading and writing file and directory structures in the IO monad. Errors are caught in a special constructor in the DirTree type. Defined instances of Functor, Traversable and Foldable allow for easily operating on a directory of files. For example, you could use Foldable.foldr to create a hash of the entire contents of a directory. The functions readDirectoryWithL and buildL allow for doing directory-traversing IO lazily as required by the execution of pure code. This allows you to treat large directories the same way as you would a lazy infinite list. The AnchoredDirTree type is a simple wrapper for DirTree to keep track of a base directory context for the DirTree. Please send me any requests, bugs, or other feedback on this module!

Tree diffing working on containers Tree.

A new data structure for accurate on-line accumulation of rank-based statistics such as quantiles and trimmed means. . See original paper: "Computing extremely accurate quantiles using t-digest" by Ted Dunning and Otmar Ertl for more details https://github.com/tdunning/t-digest/blob/master/docs/t-digest-paper/histo.pdf.

Examples

>>> quantile 0.99 (tdigest [1..1000] :: TDigest 25)
Just 990.5

>>> quantile 0.99 (tdigest [1..1000] :: TDigest 3)
Just 989.0...

t-Digest is more precise in tails, especially median is imprecise:

>>> median (forceCompress $ tdigest [1..1000] :: TDigest 25)
Just 497.6...

Semigroup

This operation isn't strictly associative, but statistical variables shouldn't be affected.

>>> let td xs = tdigest xs :: TDigest 10

>>> median (td [1..500] <> (td [501..1000] <> td [1001..1500]))
Just 802...

>>> median ((td [1..500] <> td [501..1000]) <> td [1001..1500])
Just 726...

The linear is worst-case scenario:

>>> let td' xs = tdigest (fairshuffle xs) :: TDigest 10

>>> median (td' [1..500] <> (td' [501..1000] <> td' [1001..1500]))
Just 750.3789...

>>> median ((td' [1..500] <> td' [501..1000]) <> td' [1001..1500])
Just 750.3789...

A collection of methods for laying out various kinds of trees. This module is still experimental, and more layout methods will probably be added over time. Laying out a rose tree using a symmetric layout:

import Data.Tree
import Diagrams.TwoD.Layout.Tree

t1 = Node 'A' [Node 'B' (map lf "CDE"), Node 'F' [Node 'G' (map lf "HIJKLM"), Node 'N' (map lf "OPQR")]]
where lf x = Node x []

exampleSymmTree =
renderTree ((<> circle 1 # fc white) . text . (:[]))
(~~)
(symmLayout' (with & slHSep .~ 4 & slVSep .~ 4) t1)
# centerXY # pad 1.1

Laying out a rose tree of diagrams, with spacing automatically adjusted for the size of the diagrams:

import Data.Tree
import Data.Maybe (fromMaybe)
import Diagrams.TwoD.Layout.Tree

tD = Node (rect 1 3)
[ Node (circle 0.2) []
, Node (hcat . replicate 3 $ circle 1) []
, Node (eqTriangle 5) []
]

exampleSymmTreeWithDs =
renderTree id (~~)
(symmLayout' (with & slWidth  .~ fromMaybe (0,0) . extentX
& slHeight .~ fromMaybe (0,0) . extentY)
tD)
# centerXY # pad 1.1

Using a variant symmetric layout algorithm specifically for binary trees:

import Diagrams.TwoD.Layout.Tree
import Diagrams.Prelude hiding (Empty)

drawT = maybe mempty (renderTree (const (circle 0.05 # fc black)) (~~))
. symmLayoutBin' (with & slVSep .~ 0.5)

tree500 = drawT t # centerXY # pad 1.1
where t = genTree 500 0.05
-- genTree 500 0.05 randomly generates trees of size 500 +/- 5%,
-- definition not shown

Using force-based layout on a binary tree:

{-# LANGUAGE NoMonomorphismRestriction #-}
import Diagrams.Prelude hiding (Empty)
import Diagrams.TwoD.Layout.Tree

gent 0 = Empty
gent n = BNode n (gent (n-1)) (gent (n-1))

Just t' = uniqueXLayout 1 1 (gent 4)

fblEx = renderTree (\n -> (text (show n) # fontSizeL 0.5
<> circle 0.3 # fc white))
(~~)
(forceLayoutTree t')
# centerXY # pad 1.1

Using a radial layout:

import Diagrams.Prelude
import Diagrams.TwoD.Layout.Tree
import Data.Tree

t = Node 'A' [Node 'B' (map lf "CDE"), Node 'F' [Node 'G' (map lf "HIJKLM"), Node 'N' (map lf "OPQRS")], Node 'T' (map lf "UVWXYZ")]
where lf x = Node x []

radialEx =
renderTree (\n -> (text (show n) # fontSizeG 0.5
<> circle 0.5 # fc white))
(~~) (radialLayout t)
# centerXY # pad 1.1

Depth indexed perfect binary tree.

Tree diffing working on containers Tree.

Collects all functions pertaining to trees