TypeDefs.hs

{-# LANGUAGE CPP                #-}
{-# LANGUAGE DeriveDataTypeable #-}

-- ------------------------------------------------------------

{- |
   Module     : Data.Tree.NTree.TypeDefs
   Copyright  : Copyright (C) 2005-2010 Uwe Schmidt
   License    : MIT

   Maintainer : Uwe Schmidt (uwe\@fh-wedel.de)
   Stability  : stable
   Portability: portable

   Interface definition for trees

   n-ary tree structure (rose trees)

-}

-- ------------------------------------------------------------

module Data.Tree.NTree.TypeDefs
where

import           Control.DeepSeq     (NFData (..))
import           Control.FlatSeq     (WNFData (..), rlnf)

import           Data.Binary
import           Data.Tree.Class     (Tree (..))
import           Data.Typeable       (Typeable)

#if MIN_VERSION_base(4,13,0)
#else
import           Data.Monoid         ((<>))
#endif

#if MIN_VERSION_base(4,8,2)
#else
import           Control.Applicative ((<$>))
#endif

#if MIN_VERSION_base(4,8,0)
#else
import           Control.Applicative (Applicative (..))
import           Data.Foldable       (Foldable (..))
import           Data.Monoid         (Monoid (..))
import           Data.Traversable    (Traversable (..), sequenceA)
#endif

-- ------------------------------------------------------------

-- | n-ary ordered tree (rose trees)
--
-- a tree consists of a node and a possible empty list of children.
-- If the list of children is empty, the node is a leaf, else it's
-- an inner node.
--
-- NTree implements Eq, Ord, Show and Read

data NTree  a   = NTree a (NTrees a)
    deriving
    (Eq, Ord, Show, Read, Typeable)

-- | shortcut for a sequence of n-ary trees

type NTrees   a = [NTree a]

-- ------------------------------------------------------------

instance (NFData a) => NFData (NTree a) where
    rnf (NTree n cl)                    = rnf n `seq` rnf cl
    {-# INLINE rnf #-}

instance (WNFData a) => WNFData (NTree a) where
    rwnf (NTree n cl)                   = rwnf n `seq` rwnf cl
    {-# INLINE rwnf #-}

    -- | Evaluate a tree 2 steps deep, the top node and all children are evaluated with rwnf
    rwnf2 (NTree n cl)                  = rwnf n `seq` rlnf rwnf cl
    {-# INLINE rwnf2 #-}

-- ------------------------------------------------------------

instance (Binary a) => Binary (NTree a) where
    put (NTree n cs)    = put n >> put cs
    get                 = do
                          n  <- get
                          cs <- get
                          return (NTree n cs)

-- ------------------------------------------------------------

-- | NTree implements class Functor

instance Functor NTree where
    fmap f (NTree n cl)                 = NTree (f n) (map (fmap f) cl)
    {-# INLINE fmap #-}

-- ------------------------------------------------------------

-- | NTree implements class Foldable

instance Foldable NTree where
    foldMap f (NTree n cl)              = f n <> mconcat (map (foldMap f) cl)
    {-# INLINE foldMap #-}


-- ------------------------------------------------------------

-- | NTree implements class Taversable

instance Traversable NTree where
    traverse f (NTree n cl)             = NTree <$> f n <*> sequenceA (map (traverse f) cl)
    {-# INLINE traverse #-}

-- ------------------------------------------------------------

-- | Implementation of "Data.Tree.Class" interface for rose trees

instance Tree NTree where
    mkTree n cl                         = NTree n cl
    {-# INLINE mkTree #-}

    getNode           ~(NTree n _ )     = n
    {-# INLINE getNode #-}
    getChildren       ~(NTree _ cl)     = cl
    {-# INLINE getChildren #-}

    changeNode     cf ~(NTree n cl)     = NTree (cf n) cl
    {-# INLINE changeNode #-}
    changeChildren cf ~(NTree n cl)     = NTree n (cf cl)
    {-# INLINE changeChildren #-}

    foldTree        f ~(NTree n cs)     = f n (map (foldTree f) cs)
    {-# INLINE foldTree #-}

-- eof ------------------------------------------------------------