dual-tree 0.1.0.5 → 0.2
raw patch · 3 files changed
+37/−32 lines, 3 filesdep ~semigroups
Dependency ranges changed: semigroups
Files
- CHANGES +2/−2
- dual-tree.cabal +2/−2
- src/Data/Tree/DUAL/Internal.hs +33/−28
CHANGES view
@@ -1,6 +1,6 @@-* 0.1.0.5: 10 April 2014+* 0.2: 5 November 2013 - - allow semigroups-0.13+ - Expose internal d-annotations via foldDUAL * 0.1.0.4: 26 September 2013
dual-tree.cabal view
@@ -1,5 +1,5 @@ name: dual-tree-version: 0.1.0.5+version: 0.2 synopsis: Rose trees with cached and accumulating monoidal annotations description: Rose (n-ary) trees with both upwards- (/i.e./ cached) and downwards-traveling (/i.e./@@ -41,7 +41,7 @@ exposed-modules: Data.Tree.DUAL Data.Tree.DUAL.Internal build-depends: base >= 4.3 && < 4.8,- semigroups >= 0.8 && < 0.14,+ semigroups >= 0.8 && < 0.12, newtype >= 0.2 && < 0.3, monoid-extras >= 0.2 && < 0.4 hs-source-dirs: src
src/Data/Tree/DUAL/Internal.hs view
@@ -1,10 +1,10 @@+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE DeriveFunctor #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE MultiParamTypeClasses #-}-{-# LANGUAGE FlexibleInstances #-}-{-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE TypeOperators #-}-{-# LANGUAGE FlexibleContexts #-}-{-# LANGUAGE DeriveDataTypeable #-} ----------------------------------------------------------------------------- -- |@@ -50,14 +50,12 @@ ) where -import Control.Arrow ((***))-import Data.Functor ((<$>))-import Data.List.NonEmpty (NonEmpty(..))+import Control.Arrow ((***))+import Data.List.NonEmpty (NonEmpty (..)) import qualified Data.List.NonEmpty as NEL-import Data.Maybe (fromMaybe, catMaybes, mapMaybe)+import Data.Maybe (fromMaybe) import Data.Monoid.Action import Data.Semigroup-import Data.Tuple (swap) import Data.Typeable import Control.Newtype@@ -269,29 +267,34 @@ -- path from the root -> r -- ^ Replace @LeafU@ nodes -> (NonEmpty r -> r) -- ^ Combine results at a branch node+ -> (d -> r -> r) -- ^ Process an internal d node -> (a -> r -> r) -- ^ Process an internal datum -> DUALTreeNE d u a l -> r foldDUALNE = foldDUALNE' (Option Nothing) where- foldDUALNE' dacc lf _ _ _ (Leaf _ l) = lf (option mempty id dacc) l- foldDUALNE' _ _ lfU _ _ (LeafU _) = lfU- foldDUALNE' dacc lf lfU con ann (Concat ts)- = con (NEL.map (foldDUALNE' dacc lf lfU con ann . snd . unpack) ts)- foldDUALNE' dacc lf lfU con ann (Act d t)- = foldDUALNE' (dacc <> (Option (Just d))) lf lfU con ann . snd . unpack $ t- foldDUALNE' dacc lf lfU con ann (Annot a t)- = ann a (foldDUALNE' dacc lf lfU con ann . snd . unpack $ t)+ foldDUALNE' dacc lf _ _ _ _ (Leaf _ l) = lf (option mempty id dacc) l+ foldDUALNE' _ _ lfU _ _ _ (LeafU _) = lfU+ foldDUALNE' dacc lf lfU con down ann (Concat ts)+ = con (NEL.map (foldDUALNE' dacc lf lfU con down ann . snd . unpack) ts)+ foldDUALNE' dacc lf lfU con down ann (Act d t)+ = down d (foldDUALNE' (dacc <> (Option (Just d))) lf lfU con down ann . snd . unpack $ t)+ foldDUALNE' dacc lf lfU con down ann (Annot a t)+ = ann a (foldDUALNE' dacc lf lfU con down ann . snd . unpack $ t) -- | Fold for DUAL-trees. It is given access to the internal and leaf--- data, and the accumulated @d@ values at each leaf. It is also--- allowed to replace \"@u@-only\" leaves with a constant value. In--- particular, however, it is /not/ given access to any of the @u@--- annotations, the idea being that those are used only for--- /constructing/ trees. It is also not given access to @d@ values--- as they occur in the tree, only as they accumulate at leaves. If--- you do need access to @u@ or @d@ values, you can duplicate the--- values you need in the internal data nodes.+-- data, internal @d@ values, and the accumulated @d@ values at each+-- leaf. It is also allowed to replace \"@u@-only\" leaves with a+-- constant value. In particular, however, it is /not/ given access+-- to any of the @u@ annotations, the idea being that those are used+-- only for /constructing/ trees. If you do need access to @u@+-- values, you can duplicate the values you need in the internal+-- data nodes. --+-- Be careful not to mix up the @d@ values at internal nodes with+-- the @d@ values at leaves. Each @d@ value at a leaf satisfies the+-- property that it is the 'mconcat' of all internal @d@ values+-- along the path from the root to the leaf.+-- -- The result is @Nothing@ if and only if the tree is empty. foldDUAL :: (Semigroup d, Monoid d) => (d -> l -> r) -- ^ Process a leaf datum along with the@@ -299,12 +302,13 @@ -- path from the root -> r -- ^ Replace @u@-only nodes -> (NonEmpty r -> r) -- ^ Combine results at a branch node+ -> (d -> r -> r) -- ^ Process an internal d node -> (a -> r -> r) -- ^ Process an internal datum -> DUALTree d u a l -> Maybe r-foldDUAL _ _ _ _ (DUALTree (Option Nothing))+foldDUAL _ _ _ _ _ (DUALTree (Option Nothing)) = Nothing-foldDUAL l u c a (DUALTree (Option (Just (DUALTreeU (_, t)))))- = Just $ foldDUALNE l u c a t+foldDUAL l u c d a (DUALTree (Option (Just (DUALTreeU (_, t)))))+ = Just $ foldDUALNE l u c d a t -- | A specialized fold provided for convenience: flatten a tree into -- a list of leaves along with their @d@ annotations, ignoring@@ -315,4 +319,5 @@ (\d l -> [(l, d)]) [] (concat . NEL.toList)+ (flip const) (const id)