{-
Copyright (C) 2010-2015 Dr. Alistair Ward
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see .
-}
{- |
[@AUTHOR@] Dr. Alistair Ward
[@DESCRIPTION@]
* Defines a specific type of tree-structure, which is composed from either a datum, or a list of Tree-lists; .
* This more general tree-structure has the shape of a regular-expression match.
* This contrasts with the typical binary-tree, which is either empty, or contains a (left Tree, datum, right Tree).
-}
module RegExDot.Tree(
-- * Types
-- ** Type-synonyms
-- TreeList,
-- ** Data-types
Tree(..),
-- * Functions
pop
) where
import qualified Control.Arrow
import qualified Control.DeepSeq
import qualified Data.Foldable
import qualified Data.List
import qualified Data.Monoid
-- | A general purpose tree-type structure.
data Tree a =
Leaf a -- ^ The payload.
| Node [TreeList a] -- ^ Recurse. N.B.: a list of lists is required to contain the /MatchLists/ resulting from repeated /Alternatives/.
deriving Eq
-- | A list of 'Tree's; significant only because it is the essence of the recursive nature of 'Tree'.
type TreeList a = [Tree a]
instance Show a => Show (Tree a) where
showsPrec _ (Leaf a) = shows a
showsPrec _ (Node treeLists) = showList treeLists
instance Read a => Read (Tree a) where
readsPrec _ node@('[' : _) = Control.Arrow.first Node `map` readList node {-singleton-}
readsPrec _ leaf = Control.Arrow.first Leaf `map` reads leaf {-singleton-}
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Tree a) where
rnf (Leaf a) = Control.DeepSeq.rnf a
rnf (Node l) = Control.DeepSeq.rnf l
instance Functor Tree where
fmap f (Leaf a) = Leaf $ f a
fmap f (Node treeLists) = Node $ map (fmap {-recurse-} f `map`) treeLists
instance Data.Foldable.Foldable Tree where
foldMap f (Leaf a) = f a -- CAVEAT: 'f' should be Associative, as required by a Monoid.
foldMap f (Node treeLists) = Data.List.foldl' (Data.List.foldl' (\monoid -> (monoid `Data.Monoid.mappend`) . Data.Foldable.foldMap f)) Data.Monoid.mempty treeLists
-- | Deconstruct the specified 'Node'; i.e. lop the apex from the 'Tree', leaving a flat top.
pop
:: Tree a -- ^ The tree from which to extract the list of trees hanging immediately beneath its apex.
-> [TreeList a]
pop (Node treeLists) = treeLists
pop _ = error "RegExDot.Tree.pop:\tunexpected Leaf"