data-forest 0.1.0.10 → 0.1.0.11
raw patch · 5 files changed
+240/−261 lines, 5 filesdep ~basePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base
API changes (from Hackage documentation)
Files
- changelog.md +4/−0
- data-forest.cabal +19/−22
- readme.md +2/−2
- src/Data/Forest.hs +115/−144
- test/Main.hs +100/−93
changelog.md view
@@ -1,3 +1,7 @@+## 0.1.0.11 (2023-06-26)++Raise language version to GHC2021+ ## 0.1.0.10 (2022-12-29) Metadata changes only
data-forest.cabal view
@@ -1,15 +1,12 @@ cabal-version: 3.0 name: data-forest-version: 0.1.0.10+version: 0.1.0.11 category: Data Structures synopsis: A simple multi-way tree data structure -description: In some contexts, forests (collections of zero- or more trees) are more important than trees. The /data-forest/- library provides a @Tree@ type much like the one from the popular- /containers/ library, but it also provides a @Forest@ type with- its own @Functor@ and @Foldable@ instances.+description:+ A forest is a collection of zero or more trees. homepage: https://github.com/typeclasses/data-forest @@ -20,25 +17,25 @@ license: Apache-2.0 license-file: license.txt -extra-doc-files: *.md+extra-source-files: *.md common base- default-language: Haskell2010- default-extensions: NoImplicitPrelude- ghc-options: -Wall- build-depends:- base ^>=4.14 || ^>=4.15 || ^>=4.16 || ^>=4.17+ default-language: GHC2021+ default-extensions: NoImplicitPrelude+ ghc-options: -Wall+ build-depends:+ , base ^>= 4.16 || ^>= 4.17 || ^>= 4.18 library- import: base- hs-source-dirs: src- exposed-modules:- Data.Forest+ import: base+ hs-source-dirs: src+ exposed-modules:+ Data.Forest test-suite test- import: base- type: exitcode-stdio-1.0- main-is: Main.hs- hs-source-dirs: test- build-depends:- data-forest+ import: base+ type: exitcode-stdio-1.0+ main-is: Main.hs+ hs-source-dirs: test+ build-depends:+ , data-forest
readme.md view
@@ -1,4 +1,4 @@ In some contexts, forests (collections of zero or more trees) are more important-than trees. The *data-forest* library provides a `Tree` type much like the one-from the popular *containers* library, but it also provides a `Forest` type with+than trees. The `data-forest` library provides a `Tree` type much like the one+from the popular `containers` library, but it also provides a `Forest` type with its own `Functor` and `Foldable` instances.
src/Data/Forest.hs view
@@ -1,42 +1,33 @@-{- |--Multi-way trees (also known as /rose trees/) and forests, similar to @Data.Tree@-from the popular /containers/ library.---}--{-# LANGUAGE DeriveFoldable, DeriveFunctor, DeriveTraversable,- GeneralizedNewtypeDeriving #-}-+-- | Multi-way trees (also known as /rose trees/) and forests,+-- similar to @Data.Tree@ from the /containers/ library. module Data.Forest- (- -- * Importing+ ( -- * Importing -- $imports -- * Types- Forest- , Tree+ Forest,+ Tree, -- * Constructing- , forest- , tree- , leaf- , leaves+ forest,+ tree,+ leaf,+ leaves, -- * Deconstructing- , trees- , root- , subforest- , subtrees+ trees,+ root,+ subforest,+ subtrees, -- * Folds- , foldForest- , foldTree+ foldForest,+ foldTree, -- * Forest functor -- $functor-- ) where+ )+where import Data.Eq (Eq) import Data.Foldable (Foldable)@@ -47,29 +38,26 @@ import Data.Traversable (Traversable) import Prelude (Show) ---------------------------------------------------------------------------------- -- | A forest is defined completely by its 'trees'. -- -- To construct a forest, use 'forest' or 'leaves'.- newtype Forest a = Forest- { trees :: [Tree a] -- ^ The trees that constitute the forest.- }- deriving (Eq, Show, Functor, Foldable, Traversable, Semigroup, Monoid)+ { -- | The trees that constitute the forest.+ trees :: [Tree a]+ }+ deriving (Eq, Show, Functor, Foldable, Traversable, Semigroup, Monoid) -- | A tree is defined completely by its 'root' and its 'subforest'. -- -- To construct a tree, use 'tree' or 'leaf'.- data Tree a = Tree- { root :: a -- ^ The value at the root node of the tree.- , subforest :: Forest a -- ^ The forest containing all descendants- -- of the tree's 'root'.- }- deriving (Eq, Show, Functor, Foldable, Traversable)----------------------------------------------------------------------------------+ { -- | The value at the root node of the tree.+ root :: a,+ -- | The forest containing all descendants+ -- of the tree's 'root'.+ subforest :: Forest a+ }+ deriving (Eq, Show, Functor, Foldable, Traversable) -- | Construct a forest from a list of trees. --@@ -100,119 +88,102 @@ subtrees :: Tree a -> [Tree a] subtrees t = trees (subforest t) -{- | Catamorphism on forests.-->>>-:{-example :: Forest Char-example = forest- [ tree 'a' $ leaves "bc"- , tree 'd' $ forest- [ leaf 'e'- , tree 'f' $ leaves "g"- ]- ]-:}-->>> foldForest (intercalate ", " . fmap (\(a, b) -> [a] <> " [" <> b <> "]")) example-"a [b [], c []], d [e [], f [g []]]"---}+-- | Catamorphism on forests.+--+-- >>>+-- :{+-- example :: Forest Char+-- example = forest+-- [ tree 'a' $ leaves "bc"+-- , tree 'd' $ forest+-- [ leaf 'e'+-- , tree 'f' $ leaves "g"+-- ]+-- ]+-- :}+--+-- >>> foldForest (intercalate ", " . fmap (\(a, b) -> [a] <> " [" <> b <> "]")) example+-- "a [b [], c []], d [e [], f [g []]]" foldForest :: ([(a, b)] -> b) -> Forest a -> b foldForest f =- go+ go where go (Forest ts) = f $ (\t -> (root t, go (subforest t))) <$> ts -{- | Catamorphism on trees.-->>>-:{-example :: Tree Char-example = tree 'a' $ forest- [ tree 'b' $ leaves "cd"- , tree 'e' $ forest- [ leaf 'f'- , tree 'g' $ leaves "h"- ]- ]-:}-->>> foldTree (\a bs -> [a] <> " [" <> intercalate ", " bs <> "]") example-"a [b [c [], d []], e [f [], g [h []]]]"---}+-- | Catamorphism on trees.+--+-- >>>+-- :{+-- example :: Tree Char+-- example = tree 'a' $ forest+-- [ tree 'b' $ leaves "cd"+-- , tree 'e' $ forest+-- [ leaf 'f'+-- , tree 'g' $ leaves "h"+-- ]+-- ]+-- :}+--+-- >>> foldTree (\a bs -> [a] <> " [" <> intercalate ", " bs <> "]") example+-- "a [b [c [], d []], e [f [], g [h []]]]" foldTree :: (a -> [b] -> b) -> Tree a -> b foldTree f =- go+ go where go t = f (root t) (go <$> subtrees t) ------------------------------------------------------------------------------------{- $setup-->>> import Prelude->>> import Data.Char->>> import Data.Foldable->>> import Data.Function->>> import Data.List->>> import Data.Semigroup---}------------------------------------------------------------------------------------{- $imports--Recommended imports:--> import Data.Forest (Forest, Tree)-> import qualified Data.Forest as Forest---}------------------------------------------------------------------------------------{- $functor--One notable difference of this 'Forest' from that of the /containers/ library is-that this 'Forest' is a newtype rather than a type alias, and so it provides a-more appropriate 'Functor' instance:-->>>-:{-example :: Forest Char-example = forest- [ tree 'a' $ leaves "bc"- , tree 'd' $ forest- [ leaf 'e'- , tree 'f' $ leaves "g"- ]- ]-:}-->>>-:{-showCharForest f =- intercalate ", " (showCharTree <$> trees f)- where- showCharTree t = case trees (subforest t) of- [] -> [root t]- [t'] -> [root t] <> ": " <> showCharTree t'- _ -> [root t] <> ": (" <> showCharForest (subforest t) <> ")"-:}-->>> showCharForest example-"a: (b, c), d: (e, f: g)"-->>> showCharForest (fmap toUpper example)-"A: (B, C), D: (E, F: G)"--Likewise, 'Forest''s 'Foldable' instance folds over the elements of the forest.+-- $setup+--+-- >>> import Prelude+-- >>> import Data.Char+-- >>> import Data.Foldable+-- >>> import Data.Function+-- >>> import Data.List+-- >>> import Data.Semigroup ->>> toList example-"abcdefg"+-- $imports+--+-- Recommended imports:+--+-- > import Data.Forest (Forest, Tree)+-- > import qualified Data.Forest as Forest --}+-- $functor+--+-- One notable difference of this 'Forest' from that of the /containers/ library is+-- that this 'Forest' is a newtype rather than a type alias, and so it provides a+-- more appropriate 'Functor' instance:+--+-- >>>+-- :{+-- example :: Forest Char+-- example = forest+-- [ tree 'a' $ leaves "bc"+-- , tree 'd' $ forest+-- [ leaf 'e'+-- , tree 'f' $ leaves "g"+-- ]+-- ]+-- :}+--+-- >>>+-- :{+-- showCharForest f =+-- intercalate ", " (showCharTree <$> trees f)+-- where+-- showCharTree t = case trees (subforest t) of+-- [] -> [root t]+-- [t'] -> [root t] <> ": " <> showCharTree t'+-- _ -> [root t] <> ": (" <> showCharForest (subforest t) <> ")"+-- :}+--+-- >>> showCharForest example+-- "a: (b, c), d: (e, f: g)"+--+-- >>> showCharForest (fmap toUpper example)+-- "A: (B, C), D: (E, F: G)"+--+-- Likewise, 'Forest''s 'Foldable' instance folds over the elements of the forest.+--+-- >>> toList example+-- "abcdefg"
test/Main.hs view
@@ -1,99 +1,109 @@ module Main (main) where -import Control.Applicative (Applicative (pure, (<*>)), (<$>))-import Control.Monad (Functor (fmap), Monad (return, (>>=)))-import Data.Bool (Bool, (&&))-import Data.Char (Char, toUpper)-import Data.Eq (Eq ((==)))-import Data.Foldable (Foldable (null, toList))-import Data.Forest (Forest (..), Tree (..), foldForest,- foldTree, forest, leaf, leaves, tree)-import Data.Function (($), (.))-import Data.List (intercalate, map)-import Data.Semigroup (Semigroup ((<>)))-import Numeric.Natural (Natural)-import System.Exit (die)-import System.IO (IO, putStrLn)-import Text.Show (Show (show))+import Control.Applicative (Applicative (pure, (<*>)), (<$>))+import Control.Monad (Functor (fmap), Monad (return, (>>=)))+import Data.Bool (Bool, (&&))+import Data.Char (Char, toUpper)+import Data.Eq (Eq ((==)))+import Data.Foldable (Foldable (null, toList))+import Data.Forest+ ( Forest (..),+ Tree (..),+ foldForest,+ foldTree,+ forest,+ leaf,+ leaves,+ tree,+ )+import Data.Function (($), (.))+import Data.List (intercalate, map)+import Data.Semigroup (Semigroup ((<>)))+import Numeric.Natural (Natural)+import System.Exit (die)+import System.IO (IO, putStrLn)+import Text.Show (Show (show)) main :: IO () main = dieIfFailures $ do- test 1 $- let- example :: Forest Char- example = forest- [ tree 'a' $ leaves "bc"- , tree 'd' $ forest- [ leaf 'e'- , tree 'f' $ leaves "g"- ]- ]- in- foldForest ( intercalate ", " .- fmap (\(a, b) -> [a] <> " [" <> b <> "]")- )- example- == "a [b [], c []], d [e [], f [g []]]"+ test 1 $+ let example :: Forest Char+ example =+ forest+ [ tree 'a' $ leaves "bc",+ tree 'd' $+ forest+ [ leaf 'e',+ tree 'f' $ leaves "g"+ ]+ ]+ in foldForest+ ( intercalate ", "+ . fmap (\(a, b) -> [a] <> " [" <> b <> "]")+ )+ example+ == "a [b [], c []], d [e [], f [g []]]" - test 2 $- let- example :: Tree Char- example = tree 'a' $ forest- [ tree 'b' $ leaves "cd"- , tree 'e' $ forest- [ leaf 'f'- , tree 'g' $ leaves "h"+ test 2 $+ let example :: Tree Char+ example =+ tree 'a' $+ forest+ [ tree 'b' $ leaves "cd",+ tree 'e' $+ forest+ [ leaf 'f',+ tree 'g' $ leaves "h" ] ]- in- foldTree (\a bs ->- [a] <> " [" <> intercalate ", " bs <> "]"- )- example- == "a [b [c [], d []], e [f [], g [h []]]]"+ in foldTree+ ( \a bs ->+ [a] <> " [" <> intercalate ", " bs <> "]"+ )+ example+ == "a [b [c [], d []], e [f [], g [h []]]]" - test 3 $- let- example :: Forest Char- example = forest- [ tree 'a' $ leaves "bc"- , tree 'd' $ forest- [ leaf 'e'- , tree 'f' $ leaves "g"- ]- ]- showCharForest f =- intercalate ", " (showCharTree <$> trees f)- where- showCharTree t = case trees (subforest t) of- [] -> [root t]- [t'] -> [root t] <> ": " <> showCharTree t'- _ -> [root t] <> ": (" <> showCharForest (subforest t) <> ")"- in- showCharForest example- == "a: (b, c), d: (e, f: g)"- &&- showCharForest (fmap toUpper example)- == "A: (B, C), D: (E, F: G)"+ test 3 $+ let example :: Forest Char+ example =+ forest+ [ tree 'a' $ leaves "bc",+ tree 'd' $+ forest+ [ leaf 'e',+ tree 'f' $ leaves "g"+ ]+ ]+ showCharForest f =+ intercalate ", " (showCharTree <$> trees f)+ where+ showCharTree t = case trees (subforest t) of+ [] -> [root t]+ [t'] -> [root t] <> ": " <> showCharTree t'+ _ -> [root t] <> ": (" <> showCharForest (subforest t) <> ")"+ in showCharForest example+ == "a: (b, c), d: (e, f: g)"+ && showCharForest (fmap toUpper example)+ == "A: (B, C), D: (E, F: G)" - test 4 $- let- example :: Forest Char- example = forest- [ tree 'a' $ leaves "bc"- , tree 'd' $ forest- [ leaf 'e'- , tree 'f' $ leaves "g"- ]- ]- in- toList example == "abcdefg"+ test 4 $+ let example :: Forest Char+ example =+ forest+ [ tree 'a' $ leaves "bc",+ tree 'd' $+ forest+ [ leaf 'e',+ tree 'f' $ leaves "g"+ ]+ ]+ in toList example == "abcdefg" dieIfFailures :: Failures a -> IO a dieIfFailures (Failures fs x) =- if null fs- then do putStrLn "💯"; return x- else die $ intercalate " " (map (("🔥" <> ) . show) fs)+ if null fs+ then do putStrLn "💯"; return x+ else die $ intercalate " " (map (("🔥" <>) . show) fs) type TestNumber = Natural @@ -102,15 +112,12 @@ data Failures a = Failures [TestNumber] a -instance Functor Failures- where- fmap f (Failures a x) = Failures a (f x)+instance Functor Failures where+ fmap f (Failures a x) = Failures a (f x) -instance Applicative Failures- where- pure x = Failures [] x- Failures a f <*> Failures b x = Failures (a <> b) (f x)+instance Applicative Failures where+ pure x = Failures [] x+ Failures a f <*> Failures b x = Failures (a <> b) (f x) -instance Monad Failures- where- Failures a x >>= f = let Failures b y = f x in Failures (a <> b) y+instance Monad Failures where+ Failures a x >>= f = let Failures b y = f x in Failures (a <> b) y