elynx-tree 0.5.0.2 → 0.5.1.0

raw patch · 15 files changed

+335/−210 lines, 15 filesdep ~aesondep ~elynx-nexusdep ~elynx-toolsPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: aeson, elynx-nexus, elynx-tools, hspec, math-functions, microlens

API changes (from Hackage documentation)

Files

• ChangeLog.md +9/−0
• README.md +148/−44
• bench/Length.hs +8/−1
• elynx-tree.cabal +8/−8
• src/ELynx/Topology/Rooted.hs +9/−2
• src/ELynx/Tree.hs +0/−11
• src/ELynx/Tree/Distribution/BirthDeath.hs +1/−1
• src/ELynx/Tree/Import/Newick.hs +59/−89
• src/ELynx/Tree/Length.hs +5/−10
• src/ELynx/Tree/Parallel.hs +31/−8
• src/ELynx/Tree/Phylogeny.hs +23/−22
• src/ELynx/Tree/Rooted.hs +16/−1
• src/ELynx/Tree/Splittable.hs +2/−3
• src/ELynx/Tree/Support.hs +4/−5
• src/ELynx/Tree/Zipper.hs +12/−5

@@ -5,6 +5,15 @@ ## Unreleased changes  +## Version 0.5.1.0++-   **elynx-tree:** new functions `isValidPath`, `isLeaf`, `depth`; add conversion+    topology -> tree; various internal algorithmic improvements; improved error+    messages; simplified interface to Newick parsers; parallel fold map; Nix+    flake.+-   Remove unneeded dependencies.++ ## Version 0.5.0.2  -   Speed up mixture model simulation.

@@ -2,7 +2,7 @@  # The ELynx Suite -Version: 0.5.0.2.+Version: 0.5.1.0. Reproducible evolution made easy.  <p align="center"><img src="https://travis-ci.org/dschrempf/elynx.svg?branch=master"/></p>@@ -71,11 +71,11 @@  Handle evolutionary sequences. -    slynx --help | head -n -16+    stack exec slynx -- --help | head -n -16 -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: slynx [-v|--verbosity VALUE] [-o|--output-file-basename NAME]                   [-f|--force] [--no-elynx-file] COMMAND@@ -84,8 +84,8 @@     Available options:       -h,--help                Show this help text       -V,--version             Show version-      -v,--verbosity VALUE     Be verbose; one of: Quiet Warning Info-                               Debug (default: Info)+      -v,--verbosity VALUE     Be verbose; one of: Quiet Warning Info Debug+                               (default: Info)       -o,--output-file-basename NAME                                Specify base name of output file       -f,--force               Ignore previous analysis and overwrite existing@@ -118,11 +118,11 @@  Concatenate multi sequence alignments. -    slynx concatenate --help+    stack exec slynx -- concatenate --help -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: slynx concatenate (-a|--alphabet NAME) INPUT-FILE       Concatenate sequences found in input files.@@ -139,11 +139,11 @@  Examine sequence with `slynx examine`. -    slynx examine --help+    stack exec slynx -- examine --help -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: slynx examine (-a|--alphabet NAME) INPUT-FILE [--per-site]       Examine sequences. If data is a multi sequence alignment, additionally analyze columns.@@ -161,11 +161,11 @@  Filter sequences with `filer-rows`. -    slynx filter-rows --help+    stack exec slynx -- filter-rows --help -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: slynx filter-rows (-a|--alphabet NAME) INPUT-FILE [--longer-than LENGTH]                               [--shorter-than LENGTH] [--standard-characters]@@ -184,11 +184,11 @@  Filter columns of multi sequence alignments with `filter-columns`. -    slynx filter-columns --help+    stack exec slynx -- filter-columns --help -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: slynx filter-columns (-a|--alphabet NAME) INPUT-FILE                                  [--standard-chars DOUBLE]@@ -208,11 +208,11 @@  Simulate sequences with `slynx simulate`. -    slynx simulate --help+    stack exec slynx -- simulate --help -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: slynx simulate (-t|--tree-file Name) [-s|--substitution-model MODEL]                            [-m|--mixture-model MODEL] [-e|--edm-file NAME] @@ -287,11 +287,11 @@  Sub-sample columns from multi sequence alignments. -    slynx sub-sample --help+    stack exec slynx -- sub-sample --help -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: slynx sub-sample (-a|--alphabet NAME) INPUT-FILE                             (-n|--number-of-sites INT)@@ -317,11 +317,11 @@  Translate sequences. -    slynx translate --help+    stack exec slynx -- translate --help -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: slynx translate (-a|--alphabet NAME) INPUT-FILE (-r|--reading-frame INT)                            (-u|--universal-code CODE)@@ -342,11 +342,11 @@  Handle phylogenetic trees in Newick format. -    tlynx --help | head -n -16+    stack exec tlynx -- --help | head -n -16 -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: tlynx [-v|--verbosity VALUE] [-o|--output-file-basename NAME]                   [-f|--force] [--no-elynx-file] COMMAND@@ -355,8 +355,8 @@     Available options:       -h,--help                Show this help text       -V,--version             Show version-      -v,--verbosity VALUE     Be verbose; one of: Quiet Warning Info-                               Debug (default: Info)+      -v,--verbosity VALUE     Be verbose; one of: Quiet Warning Info Debug+                               (default: Info)       -o,--output-file-basename NAME                                Specify base name of output file       -f,--force               Ignore previous analysis and overwrite existing@@ -382,11 +382,11 @@  Compute distances between phylogenetic trees. -    tlynx compare --help+    stack exec tlynx -- compare --help -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: tlynx compare [-n|--normalize] [-b|--bipartitions] [-t|--intersect]                           [-f|--newick-format FORMAT] NAMES@@ -407,15 +407,90 @@       -h,--help                Show this help text  +## Connect++Connect two phylogenetic tree in all ways (possibly honoring constraints).++    stack exec tlynx -- connect --help++    ELynx Suite version 0.5.1.0.+    Developed by Dominik Schrempf.+    Compiled on June 12, 2021, at 14:54 pm, UTC.+    +    Usage: tlynx connect [-f|--newick-format FORMAT] [-c|--contraints CONSTRAINTS]+                         TREE-FILE-A TREE-FILE-B+      Connect two phylogenetic trees in all ways (possibly honoring constraints).+    +    Available options:+      -h,--help                Show this help text+      -V,--version             Show version+      -f,--newick-format FORMAT+                               Newick tree format: Standard, IqTree, or RevBayes;+                               default: Standard; for detailed help, see 'tlynx+                               --help'+      -c,--contraints CONSTRAINTS+                               File containing one or more Newick trees to be used+                               as constraints+      TREE-FILE-A              File containing the first Newick tree+      TREE-FILE-B              File containing the second Newick tree+      -h,--help                Show this help text+++## Distancce++Compute distances between many phylogenetic trees.++    stack exec tlynx -- distance --help++    ELynx Suite version 0.5.1.0.+    Developed by Dominik Schrempf.+    Compiled on June 12, 2021, at 14:54 pm, UTC.+    +    Usage: tlynx distance (-d|--distance MEASURE) [-n|--normalize] [-t|--intersect] +                          [-s|--summary-statistics] +                          [-m|--master-tree-file MASTER-TREE-File] +                          [-f|--newick-format FORMAT] [INPUT-FILES]+      Compute distances between many phylogenetic trees.+    +    Available options:+      -h,--help                Show this help text+      -V,--version             Show version+      -d,--distance MEASURE    Type of distance to calculate (available distance+                               measures are listed below)+      -n,--normalize           Normalize trees before distance calculation; only+                               affect distances depending on branch lengths+      -t,--intersect           Compare intersections; i.e., before comparison, drop+                               leaves that are not present in the other tree+      -s,--summary-statistics  Report summary statistics only+      -m,--master-tree-file MASTER-TREE-File+                               Compare all trees to the tree in the master tree+                               file.+      -f,--newick-format FORMAT+                               Newick tree format: Standard, IqTree, or RevBayes;+                               default: Standard; for detailed help, see 'tlynx+                               --help'+      INPUT-FILES              Read tree(s) from INPUT-FILES; if more files are+                               given, one tree is expected per file+      -h,--help                Show this help text+    +    Distance measures:+      symmetric                Symmetric distance (Robinson-Foulds distance).+      incompatible-split[VAL]  Incompatible split distance. Collapse branches with (normalized)+                               support less than 0.0<=VAL<=1.0 before distance calculation;+                               if, let's say, VAL>0.7, only well supported differences contribute+                               to the total distance.+      branch-score             Branch score distance.++ ## Examine  Compute summary statistics of phylogenetic trees. -    tlynx examine --help+    stack exec tlynx -- examine --help -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: tlynx examine INPUT-FILE [-f|--newick-format FORMAT]       Compute summary statistics of phylogenetic trees.@@ -431,15 +506,44 @@       -h,--help                Show this help text  +## Shuffle++Shuffle a phylogenetic tree (keep coalescent times, but shuffle topology and+leaves).++    stack exec tlynx -- shuffle --help++    ELynx Suite version 0.5.1.0.+    Developed by Dominik Schrempf.+    Compiled on June 12, 2021, at 14:54 pm, UTC.+    +    Usage: tlynx shuffle [-f|--newick-format FORMAT] [-n|--replicates N] TREE-FILE +                         [-S|--seed [INT]]+      Shuffle a phylogenetic tree (keep coalescent times, but shuffle topology and leaves).+    +    Available options:+      -h,--help                Show this help text+      -V,--version             Show version+      -f,--newick-format FORMAT+                               Newick tree format: Standard, IqTree, or RevBayes;+                               default: Standard; for detailed help, see 'tlynx+                               --help'+      -n,--replicates N        Number of trees to generate+      TREE-FILE                File containing a Newick tree+      -S,--seed [INT]          Seed for random number generator; list of 32 bit+                               integers with up to 256 elements (default: random)+      -h,--help                Show this help text++ ## Simulate  Simulate phylogenetic trees using birth and death processes. -    tlynx simulate --help+    stack exec tlynx -- simulate --help -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: tlynx simulate (-t|--nTrees INT) (-n|--nLeaves INT) PROCESS                            [-u|--sub-sample DOUBLE] [-s|--summary-statistics] @@ -472,11 +576,11 @@  Validate and (optionally) redo past ELynx analyses. -    elynx --help | head -n -16+    stack exec elynx -- --help | head -n -16 -    ELynx Suite version 0.5.0.2.+    ELynx Suite version 0.5.1.0.     Developed by Dominik Schrempf.-    Compiled on February 19, 2021, at 13:42 pm, UTC.+    Compiled on June 12, 2021, at 14:54 pm, UTC.          Usage: elynx COMMAND       Validate and redo past ELynx analyses

@@ -22,7 +22,14 @@ import ELynx.Tree.Length  lengthSumFoldl' :: [Length] -> Length-lengthSumFoldl' = foldl' (\x y -> toLength "lengthSumFoldl'" $ fromLength x + fromLength y) 0+lengthSumFoldl' =+  foldl'+    ( \x y ->+        either (error . (<>) "lengthSumFoldl'") id $+          toLength $+            fromLength x + fromLength y+    )+    0  lengthSumFoldl'Unsafe :: [Length] -> Length lengthSumFoldl'Unsafe = foldl' (\x y -> toLengthUnsafe $ fromLength x + fromLength y) 0

@@ -1,6 +1,6 @@ cabal-version:      2.2 name:               elynx-tree-version:            0.5.0.2+version:            0.5.1.0 license:            GPL-3.0-or-later license-file:       LICENSE copyright:          Dominik Schrempf (2020)@@ -76,7 +76,7 @@     default-language: Haskell2010     ghc-options:      -Wall -Wunused-packages     build-depends:-        aeson >=1.5.5.1,+        aeson >=1.5.6.0,         attoparsec >=0.13.2.5,         base >=4.14.1.0,         bytestring >=0.10.12.0,@@ -84,8 +84,8 @@         containers >=0.6.2.1,         deepseq >=1.4.4.0,         double-conversion >=2.0.2.0,-        elynx-nexus >=0.5.0.2,-        math-functions >=0.3.4.1,+        elynx-nexus >=0.5.1.0,+        math-functions >=0.3.4.2,         mwc-random >=0.14.0.0,         parallel >=3.2.2.0,         primitive >=0.7.1.0,@@ -118,9 +118,9 @@         base >=4.14.1.0,         bytestring >=0.10.12.0,         containers >=0.6.2.1,-        elynx-tools >=0.5.0.2,+        elynx-tools >=0.5.1.0,         elynx-tree -any,-        hspec >=2.7.8+        hspec >=2.7.10  benchmark tree-bench     type:             exitcode-stdio-1.0@@ -138,8 +138,8 @@     build-depends:         base >=4.7 && <5,         criterion >=1.5.9.0,-        elynx-tools >=0.5.0.2,+        elynx-tools >=0.5.1.0,         elynx-tree -any,-        microlens >=0.4.11.2,+        microlens >=0.4.12.0,         mwc-random >=0.14.0.0,         parallel >=3.2.2.0

@@ -28,6 +28,7 @@     Forest,     fromTree,     fromLabeledTree,+    toLabeledTreeWith,      -- * Access leaves, branches and labels     leaves,@@ -128,11 +129,17 @@ fromTree (T.Node lb []) = Leaf lb fromTree (T.Node _ xs) = Node $ fromTree <$> N.fromList xs --- | Convert a rooted, labeled rose tree to a rooted topology. Branch labels and--- internal node labels are lost.+-- | Convert a rooted, branch-labeled rose tree to a rooted topology. Branch+-- labels and internal node labels are lost. fromLabeledTree :: R.Tree e a -> Topology a fromLabeledTree (R.Node _ lb []) = Leaf lb fromLabeledTree (R.Node _ _ xs) = Node $ fromLabeledTree <$> N.fromList xs++-- | Convert a rooted topology to a rooted, branch-labeled rose tree. Use the+-- given node label at internal nodes.+toLabeledTreeWith :: a -> Topology a -> R.Tree () a+toLabeledTreeWith _ (Leaf lb) = R.Node () lb []+toLabeledTreeWith x (Node ts) = R.Node () x $ map (toLabeledTreeWith x) $ N.toList ts  -- TODO: Maybe use foldr similar to 'flatten'. -- | Set of leaves.

@@ -74,14 +74,3 @@  --   external        :: n -> Bool --   external   = not . internal---- -- -- | Glue branches together, so that one new tree emerges. It's root node is--- -- -- new, the sub-forest has to be given (a list of trees).--- -- glue :: (NodeType c)--- --      => PhyloLabel a b c       -- ^ New root node.--- --      -> [PhyloTree a b c]      -- ^ Sub-forest.--- --      -> PhyloTree a b c--- -- glue s@(PhyloLabel _ _ n) ts--- --   | extant n  = error "Root node cannot be of type 'Exant'."--- --   | extinct n = error "Root node cannot be of type 'Extinct'."--- --   | otherwise = Node s ts

@@ -83,7 +83,7 @@     res   | otherwise =     error $-      "PointProcess.quantile: p must be in range [0,1] but got "+      "BirthDeath.quantile: p must be in range [0,1] but got "         ++ show p         ++ "."   where

@@ -20,24 +20,15 @@ -- In particular, no conversion from _ to (space) is done right now. -- -- For a description of rooted 'Tree's, please see the 'ELynx.Tree.Rooted'------ Code snippet:------ @--- import Data.Attoparsec.ByteString--- import ELynx.Tree------ getOneNewick = either error id . parseOnly (oneNewick Standard)--- @ module ELynx.Tree.Import.Newick   ( NewickFormat (..),-    describeNewickFormat,     newick,-    parseNewick,     oneNewick,     parseOneNewick,+    readOneNewick,     someNewick,     parseSomeNewick,+    readSomeNewick,   ) where @@ -56,10 +47,14 @@  -- | Newick tree format. ----- >>> unlines $ map (("- " <>) . description) (allValues :: [NewickFormat])--- - Standard: Branch support values are stored in square brackets after branch lengths.--- - IqTree:   Branch support values are stored as node names after the closing bracket of forests.--- - RevBayes: Key-value pairs is provided in square brackets after node names as well as branch lengths. XXX: Key value pairs are ignored at the moment.+-- - Standard: Branch support values are stored in square brackets after branch+--   lengths.+--+-- - IqTree: Branch support values are stored as node names after the closing+--   bracket of forests.+--+-- - RevBayes: Key-value pairs are provided in square brackets after node names+--   as well as branch lengths. XXX: Key value pairs are ignored at the moment. data NewickFormat = Standard | IqTree | RevBayes   deriving (Eq, Show, Read, Bounded, Enum, Generic) @@ -67,56 +62,38 @@  instance ToJSON NewickFormat --- | Short description of the supported Newick formats.-describeNewickFormat :: NewickFormat -> String-describeNewickFormat Standard =-  "Standard: Branch support values are stored in square brackets after branch lengths."-describeNewickFormat IqTree =-  "IqTree:   Branch support values are stored as node names after the closing bracket of forests."-describeNewickFormat RevBayes =-  "RevBayes: Key-value pairs is provided in square brackets after node names as well as branch lengths. XXX: Key value pairs are ignored at the moment."- -- | Newick tree parser. Also succeeds when more trees follow. newick :: NewickFormat -> Parser (Tree Phylo Name)-newick Standard = newickStandard-newick IqTree = newickIqTree-newick RevBayes = newickRevBayes---- | See 'newick'.-parseNewick :: NewickFormat -> BS.ByteString -> Tree Phylo Name-parseNewick f = either error id . parseOnly (newick f)+newick f = case f of+  Standard -> p tree+  IqTree -> p treeIqTree+  RevBayes -> newickRevBayes+  where+    p t = skipWhile isSpace *> t <* char ';' <* skipWhile isSpace <?> "newick"  -- | One Newick tree parser. Fails when end of input is not reached. oneNewick :: NewickFormat -> Parser (Tree Phylo Name)-oneNewick Standard = oneNewickStandard-oneNewick IqTree = oneNewickIqTree-oneNewick RevBayes = oneNewickRevBayes+oneNewick f = newick f <* endOfInput <?> "oneNewick"  -- | See 'oneNewick'.-parseOneNewick :: NewickFormat -> BS.ByteString -> Tree Phylo Name-parseOneNewick f = either error id . parseOnly (oneNewick f)+parseOneNewick :: NewickFormat -> BS.ByteString -> Either String (Tree Phylo Name)+parseOneNewick f = parseOnly (oneNewick f) +-- | See 'oneNewick'; may fail with 'error'.+readOneNewick :: NewickFormat -> FilePath -> IO (Tree Phylo Name)+readOneNewick f fn = BS.readFile fn >>= (either error pure . parseOneNewick f)+ -- | One or more Newick trees parser. someNewick :: NewickFormat -> Parser (Forest Phylo Name)-someNewick Standard = someNewickStandard-someNewick IqTree = someNewickIqTree-someNewick RevBayes = someNewickRevBayes+someNewick f = some (newick f) <* endOfInput <?> "someNewick"  -- | See 'someNewick'.-parseSomeNewick :: NewickFormat -> BS.ByteString -> [Tree Phylo Name]-parseSomeNewick f = either error id . parseOnly (someNewick f)---- Parse a single Newick tree. Also succeeds when more trees follow.-newickStandard :: Parser (Tree Phylo Name)-newickStandard = skipWhile isSpace *> tree <* char ';' <* skipWhile isSpace <?> "newickStandard"---- Parse a single Newick tree. Fails when end of file is not reached.-oneNewickStandard :: Parser (Tree Phylo Name)-oneNewickStandard = newickStandard <* endOfInput <?> "oneNewickStandard"+parseSomeNewick :: NewickFormat -> BS.ByteString -> Either String [Tree Phylo Name]+parseSomeNewick f = parseOnly (someNewick f) --- Parse one ore more Newick trees until end of file.-someNewickStandard :: Parser (Forest Phylo Name)-someNewickStandard = some newickStandard <* endOfInput <?> "someNewickStandard"+-- | See 'someNewick'; may fail with 'error'.+readSomeNewick :: NewickFormat -> FilePath -> IO [Tree Phylo Name]+readSomeNewick f fn = BS.readFile fn >>= (either error pure . parseSomeNewick f)  tree :: Parser (Tree Phylo Name) tree = branched <|> leaf <?> "tree"@@ -148,40 +125,43 @@ name = Name . BL.fromStrict <$> takeWhile nameChar <?> "name"  phylo :: Parser Phylo-phylo = Phylo <$> optional branchLength <*> optional branchSupport <?> "phylo"+phylo = Phylo <$> optional branchLengthStandard <*> optional branchSupportStandard <?> "phylo"  -- Branch length.-branchLength :: Parser Length-branchLength = do+branchLengthSimple :: Parser Length+branchLengthSimple = (<?> "branchLengthSimple") $ do+  l <- double <?> "branchLengthSimple; double"+  case toLength l of+    Left e -> fail e+    Right pl -> pure pl++-- Branch length.+branchLengthStandard :: Parser Length+branchLengthStandard = do   _ <- char ':' <?> "branchLengthDelimiter"-  l <- double <?> "branchLength"-  return $ toLength "branchLength" l+  branchLengthSimple -branchSupport :: Parser Support-branchSupport =+branchSupportSimple :: Parser Support+branchSupportSimple = (<?> "branchSupportSimple") $   do-    _ <- char '[' <?> "branchSupportBegin"-    s <- double <?> "branchSupport"-    _ <- char ']' <?> "branchSupportEnd"-    return $ toSupport "branchSupport" s+    s <- double <?> "branchSupportSimple; double"+    case toSupport s of+      Left e -> fail e+      Right ps -> pure ps +branchSupportStandard :: Parser Support+branchSupportStandard = (<?> "branchSupportStandard") $ do+  _ <- char '[' <?> "branchSupportBegin"+  s <- branchSupportSimple+  _ <- char ']' <?> "branchSupportEnd"+  return s+ -------------------------------------------------------------------------------- -- IQ-TREE.-+-- -- IQ-TREE stores the branch support as node names after the closing bracket of -- a forest. Parse a single Newick tree. Also succeeds when more trees follow.-newickIqTree :: Parser (Tree Phylo Name)-newickIqTree = skipWhile isSpace *> treeIqTree <* char ';' <* skipWhile isSpace <?> "newickIqTree" --- See 'newickIqTree'. Parse a single Newick tree. Fails when end of file is not--- reached.-oneNewickIqTree :: Parser (Tree Phylo Name)-oneNewickIqTree = newickIqTree <* endOfInput <?> "oneNewickIqTree"---- See 'newickIqTree'. Parse one ore more Newick trees until end of file.-someNewickIqTree :: Parser (Forest Phylo Name)-someNewickIqTree = some newickIqTree <* endOfInput <?> "someNewickIqTree"- -- IQ-TREE stores the branch support as node names after the closing bracket of a forest. treeIqTree :: Parser (Tree Phylo Name) treeIqTree = branchedIqTree <|> leaf <?> "treeIqTree"@@ -190,11 +170,10 @@ branchedIqTree :: Parser (Tree Phylo Name) branchedIqTree = (<?> "branchedIqTree") $ do   f <- forestIqTree-  ms <- optional double-  let s = toSupport "branchedIqTree" <$> ms+  ms <- optional branchSupportSimple   n <- name-  b <- optional branchLength-  return $ Node (Phylo b s) n f+  mb <- optional branchLengthStandard+  return $ Node (Phylo mb ms) n f  -- IQ-TREE stores the branch support as node names after the closing bracket of a forest. forestIqTree :: Parser (Forest Phylo Name)@@ -220,15 +199,6 @@     <* char ';'     <* skipWhile isSpace <?> "newickRevBayes" --- See 'newickRevBayes'. Parse a single Newick tree. Fails when end of file is--- not reached.-oneNewickRevBayes :: Parser (Tree Phylo Name)-oneNewickRevBayes = newickRevBayes <* endOfInput <?> "oneNewickRevBayes"---- See 'newickRevBayes'. Parse one ore more Newick trees until end of file.-someNewickRevBayes :: Parser (Forest Phylo Name)-someNewickRevBayes = some newickRevBayes <* endOfInput <?> "someNewickRevBayes"- treeRevBayes :: Parser (Tree Phylo Name) treeRevBayes = branchedRevBayes <|> leafRevBayes <?> "treeRevBayes" @@ -250,7 +220,7 @@ nameRevBayes = name <* optional brackets <?> "nameRevBayes"  branchLengthRevBayes :: Parser Length-branchLengthRevBayes = branchLength <* optional brackets <?> "branchLengthRevBayes"+branchLengthRevBayes = branchLengthStandard <* optional brackets <?> "branchLengthRevBayes"  leafRevBayes :: Parser (Tree Phylo Name) leafRevBayes = (<?> "leafRevBayes") $ do

@@ -21,7 +21,6 @@     Length (fromLength),     toLength,     toLengthUnsafe,-    checkLength,     HasLength (..),     height,     rootHeight,@@ -88,19 +87,15 @@   setLen = const   modLen f = f --- | If negative, call 'error' indicating the calling function name.-toLength :: String -> Double -> Length-toLength s x-  | x < 0 = error $ s ++ ": Length is negative: " ++ show x ++ "."-  | otherwise = Length x+-- | Return 'Left' if negative.+toLength :: Double -> Either String Length+toLength x+  | x < 0 = Left $ "Length is negative: " ++ show x ++ "."+  | otherwise = Right $ Length x  -- | Do not check if value is negative. toLengthUnsafe :: Double -> Length toLengthUnsafe = Length---- | If negative, call 'error' with given calling function name.-checkLength :: String -> Length -> Length-checkLength s = toLength s . fromLength  -- | A data type with measurable and modifiable values. class HasLength e where

@@ -9,9 +9,17 @@ -- Portability :  portable -- -- Creation date: Mon Sep  7 13:36:45 2020.+--+-- Parallel evaluation up to a given layer. By convention layer 0 only has one+-- element: the root node. The layer 1 includes the daughter nodes of the root+-- node, and so on.+--+-- The layer to which a node belongs should not be confused with the 'depth' of+-- a tree. module ELynx.Tree.Parallel   ( parTree,     parBranchFoldMap,+    parBranchFoldMapWithLayer,     parNodeFoldMap,   ) where@@ -32,31 +40,46 @@ -- Evaluate the sub trees up to given layer in parallel. parTree :: (NFData e, NFData a) => Int -> Strategy (Tree e a) parTree n t@(Node br lb ts)-  | n == 0 = rdeepseq t   | n == 1 = do     ts' <- myParList rdeepseq ts     return $ Node br lb ts'   | n >= 2 = do     ts' <- myParList (parTree (n -1)) ts     return $ Node br lb ts'-  | otherwise = error "parTree: n is negative."+  | otherwise = rdeepseq t  branchFoldMap :: (e -> f) -> (f -> f -> f) -> Tree e a -> f branchFoldMap f op (Node br _ ts) = foldl' op (f br) $ map (branchFoldMap f op) ts  -- | Map and fold over branches. Evaluate the sub trees up to given layer in parallel. parBranchFoldMap :: NFData f => Int -> (e -> f) -> (f -> f -> f) -> Tree e a -> f-parBranchFoldMap 0 f op t = branchFoldMap f op t-parBranchFoldMap n f op (Node br _ ts)+parBranchFoldMap n f op t@(Node br _ ts)   | n >= 1 = foldl' op (f br) (map (parBranchFoldMap (n - 1) f op) ts `using` myParList rdeepseq)-  | otherwise = error "parBranchFoldMap: n is negative."+  | otherwise = branchFoldMap f op t +branchFoldMapWithLayer :: Int -> (Int -> e -> f) -> (f -> f -> f) -> Tree e a -> f+branchFoldMapWithLayer d f op (Node br _ ts) =+  foldl' op (f d br) (map (branchFoldMapWithLayer (d + 1) f op) ts)++-- | Map and fold over branches.+--+-- The used function has access to the layer of the node to which the handled+-- branch is attached to.+--+-- Evaluate the sub trees up to given layer in parallel.+parBranchFoldMapWithLayer :: NFData f => Int -> (Int -> e -> f) -> (f -> f -> f) -> Tree e a -> f+parBranchFoldMapWithLayer = go 0+  where+    go d n f op t@(Node br _ ts)+      | n >= 1 =+        foldl' op (f d br) (map (go (d + 1) (n - 1) f op) ts `using` myParList rdeepseq)+      | otherwise = branchFoldMapWithLayer d f op t+ nodeFoldMap :: (a -> b) -> (b -> b -> b) -> Tree e a -> b nodeFoldMap f op (Node _ lb ts) = foldl' op (f lb) $ map (nodeFoldMap f op) ts  -- | Map and fold over nodes. Evaluate the sub trees up to given layer in parallel. parNodeFoldMap :: NFData b => Int -> (a -> b) -> (b -> b -> b) -> Tree e a -> b-parNodeFoldMap 0 f op t = nodeFoldMap f op t-parNodeFoldMap n f op (Node _ lb ts)+parNodeFoldMap n f op t@(Node _ lb ts)   | n >= 1 = foldl' op (f lb) (map (parNodeFoldMap (n - 1) f op) ts `using` myParList rdeepseq)-  | otherwise = error "parNodeFoldMap: n is negative."+  | otherwise = nodeFoldMap f op t

@@ -32,7 +32,7 @@ -- -- 4. Uniqueness of the leaves is not ensured by the data type, but has to be -- checked at runtime. Functions relying on the tree to have unique leaves do--- perform this check, and return 'Left' with an error message, if the tree has+-- perform this check, and return 'Left' with a message, if the tree has -- duplicate leaves. -- -- Note: 'Tree's are rooted.@@ -94,8 +94,6 @@ -- | The equality check is slow because the order of children is considered to -- be arbitrary. ----- NOTE: The equality check is only meaningful if the trees have unique leaves.--- -- Return 'Left' if a tree does not have unique leaves. equal :: (Eq e, Eq a, Ord a) => Tree e a -> Tree e a -> Either String Bool equal tL tR@@ -168,9 +166,10 @@ -- If the current root node is multifurcating, a bifurcating root node with the -- empty label is introduced by 'split'ting the leftmost branch. The 'Monoid' -- instance of the node label and the 'Splittable' instance of the branch length--- are used. Note that in this case, the degree of the former root node is--- decreased by one!+-- are used. --+-- NOTE: In this case, the degree of the former root node is decreased by one!+-- -- Given that the root note is bifurcating, the root node is moved to the -- required position specified by the outgroup. --@@ -212,35 +211,37 @@ midpoint :: (Semigroup e, Splittable e, HasLength e) => Tree e a -> Either String (Tree e a) midpoint (Node _ _ []) = Left "midpoint: Root node is a leaf." midpoint (Node _ _ [_]) = Left "midpoint: Root node has degree two."-midpoint t@(Node _ _ [_, _]) = getMidpoint <$> roots t+midpoint t@(Node _ _ [_, _]) = roots t >>= getMidpoint midpoint _ = Left "midpoint: Root node is multifurcating." -findMinIndex :: Ord a => [a] -> Int+-- Find the index of the smallest element.+findMinIndex :: Ord a => [a] -> Either String Int findMinIndex (x : xs) = go (0, x) 1 xs   where-    go (i, _) _ [] = i+    go (i, _) _ [] = Right i     go (i, z) j (y : ys) = if z < y then go (i, z) (j + 1) ys else go (j, y) (j + 1) ys-findMinIndex [] = error "findMinIndex: Empty list."+findMinIndex [] = Left "findMinIndex: Empty list." -getMidpoint :: HasLength e => [Tree e a] -> Tree e a+getMidpoint :: HasLength e => [Tree e a] -> Either String (Tree e a) getMidpoint ts = case t of-  (Node br lb [l, r]) ->+  Right (Node br lb [l, r]) ->     let hl = height l         hr = height r         dh = (hl - hr) / 2-     in Node-          br-          lb-          [ applyStem (modLen (subtract dh)) l,-            applyStem (modLen (+ dh)) r-          ]+     in Right $+          Node+            br+            lb+            [ applyStem (modLen (subtract dh)) l,+              applyStem (modLen (+ dh)) r+            ]   -- Explicitly use 'error' here, because roots is supposed to return trees with   -- bifurcating root nodes.-  _ -> error "getMidpoint: Root node is not bifurcating."+  Right _ -> error "getMidpoint: Root node is not bifurcating; please contact maintainer."+  Left e -> Left e   where     dhs = map getDeltaHeight ts-    i = findMinIndex dhs-    t = ts !! i+    t = (ts !!) <$> findMinIndex dhs  -- find index of minimum; take this tree and move root to the midpoint of the branch @@ -249,7 +250,7 @@ getDeltaHeight (Node _ _ [l, r]) = abs $ height l - height r -- Explicitly use 'error' here, because roots is supposed to return trees with -- bifurcating root nodes.-getDeltaHeight _ = error "getDeltaHeight: Root node is not bifurcating."+getDeltaHeight _ = error "getDeltaHeight: Root node is not bifurcating; please contact maintainer."  -- | For a rooted tree with a bifurcating root node, get all possible rooted -- trees.@@ -485,5 +486,5 @@   st <- phyloToSupportTree t   case zipTreesWith PhyloExplicit const lt st of     -- Explicit use of error, since this case should not happen.-    Nothing -> error "toExplicitTree: Can not zip two trees with the same topology."+    Nothing -> error "toExplicitTree: Can not zip two trees with different topologies; please contact maintainer."     Just zt -> return zt

@@ -79,6 +79,7 @@      -- * Structure     degree,+    depth,     prune,     dropNodesWith,     dropLeavesWith,@@ -320,9 +321,23 @@ identify :: Traversable t => t a -> t Int identify = snd . mapAccumL (\i _ -> (i + 1, i)) (0 :: Int) --- | The degree of the root node.+-- | Degree of the root node.+--+-- The degree of a node is the number of branches attached to the node. degree :: Tree e a -> Int degree = (+ 1) . length . forest++-- | Depth of a tree.+--+-- The [depth of a tree](https://en.wikipedia.org/wiki/Tree-depth) is the+-- largest number of nodes traversed on a path from the root to a leaf.+--+-- By convention, the depth is larger equal 1. That is, the depth of a leaf tree+-- is 1.+depth :: Tree e a -> Int+depth = maximum . go 1+  where go n (Node _ _ []) = [n]+        go n (Node _ _ xs) = concatMap (go (n+1)) xs  -- | Prune degree two nodes. --

@@ -14,10 +14,9 @@   ) where --- | A data type that can be combined using '<>' and split into one out of two--- equal entities.+-- | A data type that can be split into two equal entities. ----- The following equality should hold:+-- For 'Semigroup's, the following equality should hold: -- -- @ -- split x <> split x = x

@@ -59,11 +59,10 @@   setSup = const   modSup f = f --- | If negative, call 'error' indicating the calling function name.-toSupport :: String -> Double -> Support-toSupport s x-  | x < 0 = error $ s ++ ": Support is negative: " ++ show x ++ "."-  | otherwise = Support x+-- | Return 'Left' if negative.+toSupport :: Double -> Either String Support+toSupport x | x < 0 = Left $ "Support is negative: " ++ show x ++ "."+            | otherwise = Right $ Support x  -- | Do not check if value is negative. toSupportUnsafe :: Double -> Support

@@ -29,9 +29,10 @@     -- * Paths     Path,     goPath,-    validPath,     goPathUnsafe,     getSubTreeUnsafe,+    isValidPath,+    isLeafPath,      -- * Modification     insertTree,@@ -170,10 +171,16 @@ goPath pos pth = foldlM (flip goChild) pth pos  -- | Check if a path is valid in that it leads to a node on a tree.-validPath :: Tree e a -> Path -> Either String Path-validPath t p = case goPath p (fromTree t) of-  Nothing -> Left "validPath: Path is invalid."-  Just _ -> Right p+isValidPath :: Tree e a -> Path -> Bool+isValidPath t p = case goPath p (fromTree t) of+  Nothing -> False+  Just _ -> True++-- | Check if a path leads to a leaf.+isLeafPath :: Tree e a -> Path -> Bool+isLeafPath t p = case goPath p (fromTree t) of+  Nothing -> False+  Just pos -> null $ forest (current pos)  -- | Got to node with given path. --