rose-trees 0.0.2 → 0.0.2.1

raw patch · 5 files changed

+66/−45 lines, 5 filesdep +deepseqsetup-changedPVP: minor bump suggested

API additions: PVP suggests at least a minor version bump

Dependencies added: deepseq

API changes (from Hackage documentation)

Files

• Setup.hs +2/−0
• rose-trees.cabal +7/−7
• src/Data/Tree/Knuth.hs +22/−14
• src/Data/Tree/Knuth/Forest.hs +27/−22
• src/Data/Tree/Set.hs +8/−2

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -1,5 +1,5 @@ Name:                   rose-trees-Version:                0.0.2+Version:                0.0.2.1 Author:                 Athan Clark <athan.clark@gmail.com> Maintainer:             Athan Clark <athan.clark@gmail.com> License:                BSD3@@ -18,23 +18,23 @@                         Data.Tree.Knuth                         Data.Tree.Knuth.Forest                         Data.Tree.Set-  Build-Depends:        base >= 4.6 && < 5+  Build-Depends:        base >= 4.8 && < 5                       , containers+                      , deepseq+                      , mtl                       , semigroups                       , semigroupoids+                      , sets >= 0.0.5                       , witherable-                      , sets                       , QuickCheck                       , quickcheck-instances-                      , mtl-                      , criterion  Test-Suite spec   Type:                 exitcode-stdio-1.0   Default-Language:     Haskell2010   Hs-Source-Dirs:       src                       , test-  Ghc-Options:          -Wall+  Ghc-Options:          -Wall -threaded   Main-Is:              Spec.hs   Other-Modules:        Data.Tree.Knuth                         Data.Tree.Knuth.Forest@@ -58,7 +58,7 @@   Default-Language:     Haskell2010   Hs-Source-Dirs:       src                       , bench-  Ghc-Options:          -Wall+  Ghc-Options:          -Wall -threaded   Main-Is:              Bench.hs   Other-Modules:        Data.Tree.Knuth                         Data.Tree.Knuth.Forest

@@ -2,6 +2,8 @@     DeriveFunctor   , DeriveFoldable   , DeriveTraversable+  , DeriveGeneric+  , DeriveDataTypeable   , GeneralizedNewtypeDeriving   , MultiParamTypeClasses   , FlexibleInstances@@ -24,21 +26,25 @@ import qualified Data.Tree.Knuth.Forest as KF  import Data.Semigroup-import Data.Foldable as F import Data.Maybe import qualified Data.Set.Class as Sets-import Control.Applicative import Control.Monad+import Control.DeepSeq +import Data.Data+import GHC.Generics import Test.QuickCheck  -newtype KnuthTree a = KnuthTree { unKnuthTree :: (a, KF.KnuthForest a) }-  deriving (Show, Eq, Functor, Foldable, Traversable)+newtype KnuthTree a = KnuthTree+  { unKnuthTree :: (a, KF.KnuthForest a)+  } deriving (Show, Eq, Functor, Foldable, Traversable, Generic, Data, Typeable) +instance NFData a => NFData (KnuthTree a)+ instance Arbitrary a => Arbitrary (KnuthTree a) where   arbitrary = do-    x <- arbitrary+    x  <- arbitrary     xs <- arbitrary     return $ KnuthTree (x,xs) @@ -80,27 +86,27 @@ isSubtreeOf xss yss@(KnuthTree (_,ys)) = xss == yss || go ys   where     go KF.Nil = False-    go zss@(KF.Fork x xc xs) = xss == fromJust (firstTree zss) || go xs || go xc+    go zss@(KF.Fork _ xc xs) = xss == fromJust (firstTree zss) || go xs || go xc  -- | Bottom-up depth-first isSubtreeOf' :: Eq a => KnuthTree a -> KnuthTree a -> Bool isSubtreeOf' xss yss@(KnuthTree (_,ys)) = go ys || xss == yss   where     go KF.Nil = False-    go zss@(KF.Fork x xc xs) = go xc || go xs || xss == fromJust (firstTree zss)+    go zss@(KF.Fork _ xc xs) = go xc || go xs || xss == fromJust (firstTree zss)  isProperSubtreeOf :: Eq a => KnuthTree a -> KnuthTree a -> Bool isProperSubtreeOf xss (KnuthTree (_,ys)) = go ys   where     go KF.Nil = False-    go zss@(KF.Fork x xc xs) = xss == fromJust (firstTree zss) || go xs || go xc+    go zss@(KF.Fork _ xc xs) = xss == fromJust (firstTree zss) || go xs || go xc  -- | Bottom-up depth-first isProperSubtreeOf' :: Eq a => KnuthTree a -> KnuthTree a -> Bool isProperSubtreeOf' xss (KnuthTree (_,ys)) = go ys   where     go KF.Nil = False-    go zss@(KF.Fork x xc xs) = go xc || go xs || xss == fromJust (firstTree zss)+    go zss@(KF.Fork _ xc xs) = go xc || go xs || xss == fromJust (firstTree zss)  isChildOf :: Eq a => a -> KnuthTree a -> Bool isChildOf x (KnuthTree (_,ys)) = KF.isChildOf x ys@@ -117,8 +123,9 @@ singleton x = KnuthTree (x,KF.Nil)  delete :: Eq a => a -> KnuthTree a -> Maybe (KnuthTree a)-delete x (KnuthTree (y,ys)) | x == y = Nothing-                            | otherwise = Just $ KnuthTree (y, KF.delete x ys)+delete x (KnuthTree (y,ys))+  | x == y    = Nothing+  | otherwise = Just $ KnuthTree (y, KF.delete x ys)  -- ** Combination @@ -131,10 +138,11 @@   return $ KnuthTree (y,KF.intersection xs ys)  difference :: Eq a => KnuthTree a -> KnuthTree a -> Maybe (KnuthTree a)-difference xss@(KnuthTree (x,xs)) (KnuthTree (y,ys)) = do+difference xss@(KnuthTree (x,_)) (KnuthTree (y,ys)) = do   guard $ x /= y   return $ KnuthTree (x,go ys)   where     go KF.Nil = KF.Nil-    go zss@(KF.Fork x xc xs) | xss == fromJust (firstTree zss) = KF.Nil-                             | otherwise = KF.Fork x (go xc) (go xs)+    go zss@(KF.Fork x' xc xs)+      | xss == fromJust (firstTree zss) = KF.Nil+      | otherwise                       = KF.Fork x' (go xc) (go xs)

@@ -1,5 +1,8 @@ {-# LANGUAGE     DeriveFunctor+  , DeriveGeneric+  , DeriveTraversable+  , DeriveDataTypeable   , MultiParamTypeClasses   , FlexibleInstances   #-}@@ -7,30 +10,36 @@ module Data.Tree.Knuth.Forest where  import Prelude hiding (foldr, elem)-import Data.Monoid hiding ((<>)) import Data.Semigroup import Data.Foldable hiding (elem) import Data.Witherable-import Data.Traversable import qualified Data.Set.Class as Sets import Control.Applicative import Control.Monad +import Data.Data+import GHC.Generics+import Control.DeepSeq import Test.QuickCheck   -- * Forest -data KnuthForest a = Fork { kNode :: a-                          , kChildren :: KnuthForest a-                          , kSiblings :: KnuthForest a }-                   | Nil-  deriving (Show, Eq, Functor)+data KnuthForest a+  = Fork { kNode     :: a+         , kChildren :: KnuthForest a+         , kSiblings :: KnuthForest a+         }+  | Nil+  deriving (Show, Eq, Functor, Traversable, Generic, Data, Typeable) +instance NFData a => NFData (KnuthForest a)+ instance Arbitrary a => Arbitrary (KnuthForest a) where-  arbitrary = oneof [ return Nil-                    , liftA3 Fork arbitrary arbitrary arbitrary-                    ]+  arbitrary =+    oneof [ return Nil+          , liftA3 Fork arbitrary arbitrary arbitrary+          ]   -- | Siblings before children@@ -38,8 +47,8 @@   compare (Fork x xc xs) (Fork y yc ys) =     compare x y <> compare xs ys <> compare xc yc   compare Nil Nil = EQ-  compare Nil _ = LT-  compare _ Nil = GT+  compare Nil _   = LT+  compare _ Nil   = GT  -- | Zippy instance Applicative KnuthForest where@@ -55,8 +64,8 @@  -- | Breadth-first instance Monad KnuthForest where-  return x = Fork x Nil Nil-  Nil >>= _ = Nil+  return = pure+  Nil            >>= _ = Nil   (Fork x xc xs) >>= f = f x `union` (xs >>= f) `union` (xc >>= f)  instance MonadPlus KnuthForest where@@ -67,7 +76,7 @@   (<>) = union  instance Monoid (KnuthForest a) where-  mempty = Nil+  mempty  = Nil   mappend = union  -- | Breadth-first@@ -76,15 +85,11 @@   foldr f acc (Fork x xc xs) =     foldr f (foldr f (f x acc) xs) xc -instance Traversable KnuthForest where-  sequenceA Nil = pure Nil-  sequenceA (Fork x xc xs) = liftA3 Fork x (sequenceA xc) (sequenceA xs)- instance Witherable KnuthForest where   catMaybes Nil = Nil   catMaybes (Fork mx xc xs) = case mx of     Nothing -> Nil-    Just x -> Fork x (catMaybes xc) (catMaybes xs)+    Just x  -> Fork x (catMaybes xc) (catMaybes xs)  instance Sets.HasUnion (KnuthForest a) where   union = union@@ -176,9 +181,9 @@ -- ** Combination  union :: KnuthForest a -> KnuthForest a -> KnuthForest a-union Nil y = y+union Nil             y = y union (Fork x xc Nil) y = Fork x xc y-union (Fork x xc xs) y = Fork x xc $ union xs y+union (Fork x xc xs)  y = Fork x xc $ union xs y  intersection :: Eq a => KnuthForest a -> KnuthForest a -> KnuthForest a intersection Nil _ = Nil

@@ -1,5 +1,7 @@ {-# LANGUAGE     DeriveFoldable+  , DeriveGeneric+  , DeriveDataTypeable   , FlexibleInstances   , MultiParamTypeClasses   #-}@@ -10,13 +12,15 @@ import qualified Data.Set as Set import qualified Data.Foldable as F import qualified Data.Maybe as M-import Data.Monoid hiding ((<>)) import Data.Semigroup import Data.Semigroup.Foldable import qualified Data.Set.Class as Sets import Control.Applicative import Control.Monad +import Data.Data+import GHC.Generics+import Control.DeepSeq import Test.QuickCheck import Test.QuickCheck.Instances @@ -24,7 +28,9 @@ data SetTree a = SetTree   { sNode     :: a   , sChildren :: Set.Set (SetTree a)-  } deriving (Show, Eq, Ord, Foldable)+  } deriving (Show, Eq, Ord, Foldable, Generic, Data, Typeable)++instance NFData a => NFData (SetTree a)  instance (Ord a, Arbitrary a) => Arbitrary (SetTree a) where   arbitrary = liftA2 SetTree arbitrary arbitrary