{-# LANGUAGE BangPatterns #-}{-# LANGUAGE PatternGuards #-}{-# LANGUAGE CPP #-}
#if __GLASGOW_HASKELL__
{-# LANGUAGE DeriveDataTypeable #-}{-# LANGUAGE DeriveGeneric #-}{-# LANGUAGE DeriveLift #-}{-# LANGUAGE Trustworthy #-}
#endif

#include "containers.h"
------------------------------------------------------------------------------- |-- Module : Data.Tree-- Copyright : (c) The University of Glasgow 2002-- License : BSD-style (see the file libraries/base/LICENSE)---- Maintainer : libraries@haskell.org-- Portability : portable---- = Multi-way Trees and Forests---- The @'Tree' a@ type represents a lazy, possibly infinite, multi-way tree-- (also known as a /rose tree/).---- The @'Forest' a@ type represents a forest of @'Tree' a@s.-------------------------------------------------------------------------------moduleData.Tree(-- * Trees and ForestsTree (..),Forest ,PostOrder (..)-- * Construction,unfoldTree ,unfoldForest ,unfoldTreeM ,unfoldForestM ,unfoldTreeM_BF ,unfoldForestM_BF -- * Elimination,foldTree ,flatten ,levels ,leaves ,edges ,pathsToRoot ,pathsFromRoot -- * Ascii Drawings,drawTree ,drawForest )whereimportUtils.Containers.Internal.Prelude asPreludeimportPrelude()importData.Bits((.&.))importData.Foldable(toList)importqualifiedData.FoldableasFoldableimportData.List.NonEmpty(NonEmpty(..))importData.Traversable(foldMapDefault)importControl.Monad(liftM)importControl.Monad.Fix(MonadFix(..),fix)importData.Sequence (Seq ,empty ,singleton ,(<|) ,(|>) ,fromList ,ViewL (..),ViewR (..),viewl ,viewr )importControl.DeepSeq(NFData(rnf),NFData1(liftRnf))
#ifdef __GLASGOW_HASKELL__
importData.Data(Data)importGHC.Generics(Generic,Generic1)importqualifiedGHC.ExtsimportLanguage.Haskell.TH.Syntax(Lift)-- See Note [ Template Haskell Dependencies ]importLanguage.Haskell.TH()
#endif
importControl.Monad.Zip(MonadZip(..))
#ifdef __GLASGOW_HASKELL__
importData.Coerce(coerce)
#endif
importData.Functor.Classes
#if !MIN_VERSION_base(4,11,0)
importData.Semigroup(Semigroup(..))
#endif

#if MIN_VERSION_base(4,18,0)
importqualifiedData.Foldable1asFoldable1
#endif
-- | Non-empty, possibly infinite, multi-way trees; also known as /rose trees/.dataTree a =Node {forall a. Tree a -> a
rootLabel ::a ,-- ^ label valueforall a. Tree a -> [Tree a]
subForest ::[Tree a ]-- ^ zero or more child trees}
#ifdef __GLASGOW_HASKELL__
deriving(Tree a -> Tree a -> Bool
(Tree a -> Tree a -> Bool)
-> (Tree a -> Tree a -> Bool) -> Eq (Tree a)
forall a. Eq a => Tree a -> Tree a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => Tree a -> Tree a -> Bool
== :: Tree a -> Tree a -> Bool
$c/= :: forall a. Eq a => Tree a -> Tree a -> Bool
/= :: Tree a -> Tree a -> Bool
Eq,Eq (Tree a)
Eq (Tree a) =>
(Tree a -> Tree a -> Ordering)
-> (Tree a -> Tree a -> Bool)
-> (Tree a -> Tree a -> Bool)
-> (Tree a -> Tree a -> Bool)
-> (Tree a -> Tree a -> Bool)
-> (Tree a -> Tree a -> Tree a)
-> (Tree a -> Tree a -> Tree a)
-> Ord (Tree a)
Tree a -> Tree a -> Bool
Tree a -> Tree a -> Ordering
Tree a -> Tree a -> Tree a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (Tree a)
forall a. Ord a => Tree a -> Tree a -> Bool
forall a. Ord a => Tree a -> Tree a -> Ordering
forall a. Ord a => Tree a -> Tree a -> Tree a
$ccompare :: forall a. Ord a => Tree a -> Tree a -> Ordering
compare :: Tree a -> Tree a -> Ordering
$c< :: forall a. Ord a => Tree a -> Tree a -> Bool
< :: Tree a -> Tree a -> Bool
$c<= :: forall a. Ord a => Tree a -> Tree a -> Bool
<= :: Tree a -> Tree a -> Bool
$c> :: forall a. Ord a => Tree a -> Tree a -> Bool
> :: Tree a -> Tree a -> Bool
$c>= :: forall a. Ord a => Tree a -> Tree a -> Bool
>= :: Tree a -> Tree a -> Bool
$cmax :: forall a. Ord a => Tree a -> Tree a -> Tree a
max :: Tree a -> Tree a -> Tree a
$cmin :: forall a. Ord a => Tree a -> Tree a -> Tree a
min :: Tree a -> Tree a -> Tree a
Ord-- ^ @since 0.6.5,ReadPrec [Tree a]
ReadPrec (Tree a)
Int -> ReadS (Tree a)
ReadS [Tree a]
(Int -> ReadS (Tree a))
-> ReadS [Tree a]
-> ReadPrec (Tree a)
-> ReadPrec [Tree a]
-> Read (Tree a)
forall a. Read a => ReadPrec [Tree a]
forall a. Read a => ReadPrec (Tree a)
forall a. Read a => Int -> ReadS (Tree a)
forall a. Read a => ReadS [Tree a]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: forall a. Read a => Int -> ReadS (Tree a)
readsPrec :: Int -> ReadS (Tree a)
$creadList :: forall a. Read a => ReadS [Tree a]
readList :: ReadS [Tree a]
$creadPrec :: forall a. Read a => ReadPrec (Tree a)
readPrec :: ReadPrec (Tree a)
$creadListPrec :: forall a. Read a => ReadPrec [Tree a]
readListPrec :: ReadPrec [Tree a]
Read,Int -> Tree a -> ShowS
[Tree a] -> ShowS
Tree a -> String
(Int -> Tree a -> ShowS)
-> (Tree a -> String) -> ([Tree a] -> ShowS) -> Show (Tree a)
forall a. Show a => Int -> Tree a -> ShowS
forall a. Show a => [Tree a] -> ShowS
forall a. Show a => Tree a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> Tree a -> ShowS
showsPrec :: Int -> Tree a -> ShowS
$cshow :: forall a. Show a => Tree a -> String
show :: Tree a -> String
$cshowList :: forall a. Show a => [Tree a] -> ShowS
showList :: [Tree a] -> ShowS
Show,Typeable (Tree a)
Typeable (Tree a) =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> Tree a -> c (Tree a))
-> (forall (c :: * -> *).
 (forall b r. Data b => c (b -> r) -> c r)
 -> (forall r. r -> c r) -> Constr -> c (Tree a))
-> (Tree a -> Constr)
-> (Tree a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
 Typeable t =>
 (forall d. Data d => c (t d)) -> Maybe (c (Tree a)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
 Typeable t =>
 (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Tree a)))
-> ((forall b. Data b => b -> b) -> Tree a -> Tree a)
-> (forall r r'.
 (r -> r' -> r)
 -> r -> (forall d. Data d => d -> r') -> Tree a -> r)
-> (forall r r'.
 (r' -> r -> r)
 -> r -> (forall d. Data d => d -> r') -> Tree a -> r)
-> (forall u. (forall d. Data d => d -> u) -> Tree a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> Tree a -> u)
-> (forall (m :: * -> *).
 Monad m =>
 (forall d. Data d => d -> m d) -> Tree a -> m (Tree a))
-> (forall (m :: * -> *).
 MonadPlus m =>
 (forall d. Data d => d -> m d) -> Tree a -> m (Tree a))
-> (forall (m :: * -> *).
 MonadPlus m =>
 (forall d. Data d => d -> m d) -> Tree a -> m (Tree a))
-> Data (Tree a)
Tree a -> Constr
Tree a -> DataType
(forall b. Data b => b -> b) -> Tree a -> Tree a
forall a. Data a => Typeable (Tree a)
forall a. Data a => Tree a -> Constr
forall a. Data a => Tree a -> DataType
forall a.
Data a =>
(forall b. Data b => b -> b) -> Tree a -> Tree a
forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> Tree a -> u
forall a u. Data a => (forall d. Data d => d -> u) -> Tree a -> [u]
forall a r r'.
Data a =>
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r
forall a r r'.
Data a =>
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r
forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> Tree a -> m (Tree a)
forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Tree a -> m (Tree a)
forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Tree a)
forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Tree a -> c (Tree a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Tree a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Tree a))
forall a.
Typeable a =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
 (forall b r. Data b => c (b -> r) -> c r)
 -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
 Typeable t =>
 (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
 Typeable t =>
 (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
 (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
 (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
 Monad m =>
 (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
 MonadPlus m =>
 (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
 MonadPlus m =>
 (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> Tree a -> u
forall u. (forall d. Data d => d -> u) -> Tree a -> [u]
forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r
forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Tree a -> m (Tree a)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Tree a -> m (Tree a)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Tree a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Tree a -> c (Tree a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Tree a))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Tree a))
$cgfoldl :: forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Tree a -> c (Tree a)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Tree a -> c (Tree a)
$cgunfold :: forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Tree a)
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Tree a)
$ctoConstr :: forall a. Data a => Tree a -> Constr
toConstr :: Tree a -> Constr
$cdataTypeOf :: forall a. Data a => Tree a -> DataType
dataTypeOf :: Tree a -> DataType
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Tree a))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Tree a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Tree a))
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Tree a))
$cgmapT :: forall a.
Data a =>
(forall b. Data b => b -> b) -> Tree a -> Tree a
gmapT :: (forall b. Data b => b -> b) -> Tree a -> Tree a
$cgmapQl :: forall a r r'.
Data a =>
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r
gmapQl :: forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r
$cgmapQr :: forall a r r'.
Data a =>
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r
gmapQr :: forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r
$cgmapQ :: forall a u. Data a => (forall d. Data d => d -> u) -> Tree a -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> Tree a -> [u]
$cgmapQi :: forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> Tree a -> u
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Tree a -> u
$cgmapM :: forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> Tree a -> m (Tree a)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Tree a -> m (Tree a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Tree a -> m (Tree a)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Tree a -> m (Tree a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Tree a -> m (Tree a)
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Tree a -> m (Tree a)
Data,(forall x. Tree a -> Rep (Tree a) x)
-> (forall x. Rep (Tree a) x -> Tree a) -> Generic (Tree a)
forall x. Rep (Tree a) x -> Tree a
forall x. Tree a -> Rep (Tree a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (Tree a) x -> Tree a
forall a x. Tree a -> Rep (Tree a) x
$cfrom :: forall a x. Tree a -> Rep (Tree a) x
from :: forall x. Tree a -> Rep (Tree a) x
$cto :: forall a x. Rep (Tree a) x -> Tree a
to :: forall x. Rep (Tree a) x -> Tree a
Generic-- ^ @since 0.5.8,(forall a. Tree a -> Rep1 Tree a)
-> (forall a. Rep1 Tree a -> Tree a) -> Generic1 Tree
forall a. Rep1 Tree a -> Tree a
forall a. Tree a -> Rep1 Tree a
forall k (f :: k -> *).
(forall (a :: k). f a -> Rep1 f a)
-> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
$cfrom1 :: forall a. Tree a -> Rep1 Tree a
from1 :: forall a. Tree a -> Rep1 Tree a
$cto1 :: forall a. Rep1 Tree a -> Tree a
to1 :: forall a. Rep1 Tree a -> Tree a
Generic1-- ^ @since 0.5.8,(forall (m :: * -> *). Quote m => Tree a -> m Exp)
-> (forall (m :: * -> *). Quote m => Tree a -> Code m (Tree a))
-> Lift (Tree a)
forall a (m :: * -> *). (Lift a, Quote m) => Tree a -> m Exp
forall a (m :: * -> *).
(Lift a, Quote m) =>
Tree a -> Code m (Tree a)
forall t.
(forall (m :: * -> *). Quote m => t -> m Exp)
-> (forall (m :: * -> *). Quote m => t -> Code m t) -> Lift t
forall (m :: * -> *). Quote m => Tree a -> m Exp
forall (m :: * -> *). Quote m => Tree a -> Code m (Tree a)
$clift :: forall a (m :: * -> *). (Lift a, Quote m) => Tree a -> m Exp
lift :: forall (m :: * -> *). Quote m => Tree a -> m Exp
$cliftTyped :: forall a (m :: * -> *).
(Lift a, Quote m) =>
Tree a -> Code m (Tree a)
liftTyped :: forall (m :: * -> *). Quote m => Tree a -> Code m (Tree a)
Lift-- ^ @since 0.6.6)
#else
deriving(Eq,Ord,Read,Show)
#endif
-- | This type synonym exists primarily for historical-- reasons.typeForest a =[Tree a ]-- | @since 0.5.9instanceEq1Tree whereliftEq :: forall a b. (a -> b -> Bool) -> Tree a -> Tree b -> Bool
liftEq a -> b -> Bool
eq =Tree a -> Tree b -> Bool
leq whereleq :: Tree a -> Tree b -> Bool
leq (Node a
a [Tree a]
fr )(Node b
a' [Tree b]
fr' )=a -> b -> Bool
eq a
a b
a' Bool -> Bool -> Bool
&&(Tree a -> Tree b -> Bool) -> [Tree a] -> [Tree b] -> Bool
forall a b. (a -> b -> Bool) -> [a] -> [b] -> Bool
forall (f :: * -> *) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEqTree a -> Tree b -> Bool
leq [Tree a]
fr [Tree b]
fr' -- | @since 0.5.9instanceOrd1Tree whereliftCompare :: forall a b. (a -> b -> Ordering) -> Tree a -> Tree b -> Ordering
liftCompare a -> b -> Ordering
cmp =Tree a -> Tree b -> Ordering
lcomp wherelcomp :: Tree a -> Tree b -> Ordering
lcomp (Node a
a [Tree a]
fr )(Node b
a' [Tree b]
fr' )=a -> b -> Ordering
cmp a
a b
a' Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<>(Tree a -> Tree b -> Ordering) -> [Tree a] -> [Tree b] -> Ordering
forall a b. (a -> b -> Ordering) -> [a] -> [b] -> Ordering
forall (f :: * -> *) a b.
Ord1 f =>
(a -> b -> Ordering) -> f a -> f b -> Ordering
liftCompareTree a -> Tree b -> Ordering
lcomp [Tree a]
fr [Tree b]
fr' -- | @since 0.5.9instanceShow1Tree whereliftShowsPrec :: forall a.
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Tree a -> ShowS
liftShowsPrec Int -> a -> ShowS
shw [a] -> ShowS
shwl Int
p (Node a
a [Tree a]
fr )=Bool -> ShowS -> ShowS
showParen(Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>Int
10)(ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$String -> ShowS
showStringString
"Node {rootLabel = "ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Int -> a -> ShowS
shw Int
0a
a ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.String -> ShowS
showStringString
", "ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.String -> ShowS
showStringString
"subForest = "ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Int -> a -> ShowS) -> ([a] -> ShowS) -> [Tree a] -> ShowS
forall a.
(Int -> a -> ShowS) -> ([a] -> ShowS) -> [Tree a] -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> [f a] -> ShowS
liftShowListInt -> a -> ShowS
shw [a] -> ShowS
shwl [Tree a]
fr ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.String -> ShowS
showStringString
"}"-- | @since 0.5.9instanceRead1Tree whereliftReadsPrec :: forall a. (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Tree a)
liftReadsPrec Int -> ReadS a
rd ReadS [a]
rdl Int
p =Bool -> ReadS (Tree a) -> ReadS (Tree a)
forall a. Bool -> ReadS a -> ReadS a
readParen(Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>Int
10)(ReadS (Tree a) -> ReadS (Tree a))
-> ReadS (Tree a) -> ReadS (Tree a)
forall a b. (a -> b) -> a -> b
$\String
s ->do(String
"Node",String
s1 )<-ReadS String
lexString
s (String
"{",String
s2 )<-ReadS String
lexString
s1 (String
"rootLabel",String
s3 )<-ReadS String
lexString
s2 (String
"=",String
s4 )<-ReadS String
lexString
s3 (a
a ,String
s5 )<-Int -> ReadS a
rd Int
0String
s4 (String
",",String
s6 )<-ReadS String
lexString
s5 (String
"subForest",String
s7 )<-ReadS String
lexString
s6 (String
"=",String
s8 )<-ReadS String
lexString
s7 ([Tree a]
fr ,String
s9 )<-(Int -> ReadS a) -> ReadS [a] -> ReadS [Tree a]
forall a. (Int -> ReadS a) -> ReadS [a] -> ReadS [Tree a]
forall (f :: * -> *) a.
Read1 f =>
(Int -> ReadS a) -> ReadS [a] -> ReadS [f a]
liftReadListInt -> ReadS a
rd ReadS [a]
rdl String
s8 (String
"}",String
s10 )<-ReadS String
lexString
s9 (Tree a, String) -> [(Tree a, String)]
forall a. a -> [a]
forall (f :: * -> *) a. Applicative f => a -> f a
pure(a -> [Tree a] -> Tree a
forall a. a -> [Tree a] -> Tree a
Node a
a [Tree a]
fr ,String
s10 )instanceFunctorTree wherefmap :: forall a b. (a -> b) -> Tree a -> Tree b
fmap=(a -> b) -> Tree a -> Tree b
forall a b. (a -> b) -> Tree a -> Tree b
fmapTree a
x <$ :: forall a b. a -> Tree b -> Tree a
<$ Node b
_[Tree b]
ts =a -> [Tree a] -> Tree a
forall a. a -> [Tree a] -> Tree a
Node a
x ((Tree b -> Tree a) -> [Tree b] -> [Tree a]
forall a b. (a -> b) -> [a] -> [b]
map(a
x a -> Tree b -> Tree a
forall a b. a -> Tree b -> Tree a
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$)[Tree b]
ts )fmapTree ::(a ->b )->Tree a ->Tree b fmapTree :: forall a b. (a -> b) -> Tree a -> Tree b
fmapTree a -> b
f (Node a
x [Tree a]
ts )=b -> [Tree b] -> Tree b
forall a. a -> [Tree a] -> Tree a
Node (a -> b
f a
x )((Tree a -> Tree b) -> [Tree a] -> [Tree b]
forall a b. (a -> b) -> [a] -> [b]
map((a -> b) -> Tree a -> Tree b
forall a b. (a -> b) -> Tree a -> Tree b
fmapTree a -> b
f )[Tree a]
ts )
#ifdef __GLASGOW_HASKELL__
{-# NOINLINE[1]fmapTree #-}{-# RULES"fmapTree/coerce"fmapTree coerce=coerce#-}
#endif
instanceApplicativeTree wherepure :: forall a. a -> Tree a
purea
x =a -> [Tree a] -> Tree a
forall a. a -> [Tree a] -> Tree a
Node a
x []Node a -> b
f [Tree (a -> b)]
tfs <*> :: forall a b. Tree (a -> b) -> Tree a -> Tree b
<*>tx :: Tree a
tx @(Node a
x [Tree a]
txs )=b -> [Tree b] -> Tree b
forall a. a -> [Tree a] -> Tree a
Node (a -> b
f a
x )((Tree a -> Tree b) -> [Tree a] -> [Tree b]
forall a b. (a -> b) -> [a] -> [b]
map(a -> b
f (a -> b) -> Tree a -> Tree b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>)[Tree a]
txs [Tree b] -> [Tree b] -> [Tree b]
forall a. [a] -> [a] -> [a]
++(Tree (a -> b) -> Tree b) -> [Tree (a -> b)] -> [Tree b]
forall a b. (a -> b) -> [a] -> [b]
map(Tree (a -> b) -> Tree a -> Tree b
forall a b. Tree (a -> b) -> Tree a -> Tree b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*>Tree a
tx )[Tree (a -> b)]
tfs )liftA2 :: forall a b c. (a -> b -> c) -> Tree a -> Tree b -> Tree c
liftA2 a -> b -> c
f (Node a
x [Tree a]
txs )ty :: Tree b
ty @(Node b
y [Tree b]
tys )=c -> [Tree c] -> Tree c
forall a. a -> [Tree a] -> Tree a
Node (a -> b -> c
f a
x b
y )((Tree b -> Tree c) -> [Tree b] -> [Tree c]
forall a b. (a -> b) -> [a] -> [b]
map(a -> b -> c
f a
x (b -> c) -> Tree b -> Tree c
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>)[Tree b]
tys [Tree c] -> [Tree c] -> [Tree c]
forall a. [a] -> [a] -> [a]
++(Tree a -> Tree c) -> [Tree a] -> [Tree c]
forall a b. (a -> b) -> [a] -> [b]
map(\Tree a
tx ->(a -> b -> c) -> Tree a -> Tree b -> Tree c
forall a b c. (a -> b -> c) -> Tree a -> Tree b -> Tree c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2a -> b -> c
f Tree a
tx Tree b
ty )[Tree a]
txs )Node a
x [Tree a]
txs <* :: forall a b. Tree a -> Tree b -> Tree a
<* ty :: Tree b
ty @(Node b
_[Tree b]
tys )=a -> [Tree a] -> Tree a
forall a. a -> [Tree a] -> Tree a
Node a
x ((Tree b -> Tree a) -> [Tree b] -> [Tree a]
forall a b. (a -> b) -> [a] -> [b]
map(a
x a -> Tree b -> Tree a
forall a b. a -> Tree b -> Tree a
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$)[Tree b]
tys [Tree a] -> [Tree a] -> [Tree a]
forall a. [a] -> [a] -> [a]
++(Tree a -> Tree a) -> [Tree a] -> [Tree a]
forall a b. (a -> b) -> [a] -> [b]
map(Tree a -> Tree b -> Tree a
forall a b. Tree a -> Tree b -> Tree a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<*Tree b
ty )[Tree a]
txs )Node a
_[Tree a]
txs *> :: forall a b. Tree a -> Tree b -> Tree b
*>ty :: Tree b
ty @(Node b
y [Tree b]
tys )=b -> [Tree b] -> Tree b
forall a. a -> [Tree a] -> Tree a
Node b
y ([Tree b]
tys [Tree b] -> [Tree b] -> [Tree b]
forall a. [a] -> [a] -> [a]
++(Tree a -> Tree b) -> [Tree a] -> [Tree b]
forall a b. (a -> b) -> [a] -> [b]
map(Tree a -> Tree b -> Tree b
forall a b. Tree a -> Tree b -> Tree b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*>Tree b
ty )[Tree a]
txs )instanceMonadTree whereNode a
x [Tree a]
ts >>= :: forall a b. Tree a -> (a -> Tree b) -> Tree b
>>=a -> Tree b
f =casea -> Tree b
f a
x ofNode b
x' [Tree b]
ts' ->b -> [Tree b] -> Tree b
forall a. a -> [Tree a] -> Tree a
Node b
x' ([Tree b]
ts' [Tree b] -> [Tree b] -> [Tree b]
forall a. [a] -> [a] -> [a]
++(Tree a -> Tree b) -> [Tree a] -> [Tree b]
forall a b. (a -> b) -> [a] -> [b]
map(Tree a -> (a -> Tree b) -> Tree b
forall a b. Tree a -> (a -> Tree b) -> Tree b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>=a -> Tree b
f )[Tree a]
ts )-- | @since 0.5.11instanceMonadFixTree wheremfix :: forall a. (a -> Tree a) -> Tree a
mfix=(a -> Tree a) -> Tree a
forall a. (a -> Tree a) -> Tree a
mfixTree mfixTree ::(a ->Tree a )->Tree a mfixTree :: forall a. (a -> Tree a) -> Tree a
mfixTree a -> Tree a
f |Node a
a [Tree a]
children <-(Tree a -> Tree a) -> Tree a
forall a. (a -> a) -> a
fix(a -> Tree a
f (a -> Tree a) -> (Tree a -> a) -> Tree a -> Tree a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Tree a -> a
forall a. Tree a -> a
rootLabel )=a -> [Tree a] -> Tree a
forall a. a -> [Tree a] -> Tree a
Node a
a ((Int -> Tree a -> Tree a) -> [Int] -> [Tree a] -> [Tree a]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith(\Int
i Tree a
_->(a -> Tree a) -> Tree a
forall a. (a -> Tree a) -> Tree a
mfixTree (([Tree a] -> Int -> Tree a
forall a. HasCallStack => [a] -> Int -> a
!!Int
i )([Tree a] -> Tree a) -> (a -> [Tree a]) -> a -> Tree a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Tree a -> [Tree a]
forall a. Tree a -> [Tree a]
subForest (Tree a -> [Tree a]) -> (a -> Tree a) -> a -> [Tree a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.a -> Tree a
f ))[Int
0..][Tree a]
children )-- | Traverses in pre-order.instanceTraversableTree wheretraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Tree a -> f (Tree b)
traverse a -> f b
f =Tree a -> f (Tree b)
go wherego :: Tree a -> f (Tree b)
go (Node a
x [Tree a]
ts )=(b -> [Tree b] -> Tree b) -> f b -> f [Tree b] -> f (Tree b)
forall a b c. (a -> b -> c) -> f a -> f b -> f c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2b -> [Tree b] -> Tree b
forall a. a -> [Tree a] -> Tree a
Node (a -> f b
f a
x )((Tree a -> f (Tree b)) -> [Tree a] -> f [Tree b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverseTree a -> f (Tree b)
go [Tree a]
ts ){-# INLINEtraverse#-}-- | Folds in pre-order.-- See Note [Implemented Foldable Tree functions]instanceFoldableTree wherefold :: forall m. Monoid m => Tree m -> m
fold =(m -> m) -> Tree m -> m
forall m a. Monoid m => (a -> m) -> Tree a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMapm -> m
forall a. a -> a
id{-# INLINABLEfold#-}foldMap :: forall m a. Monoid m => (a -> m) -> Tree a -> m
foldMap=(a -> m) -> Tree a -> m
forall (t :: * -> *) m a.
(Traversable t, Monoid m) =>
(a -> m) -> t a -> m
foldMapDefault{-# INLINEfoldMap#-}foldr :: forall a b. (a -> b -> b) -> b -> Tree a -> b
foldr a -> b -> b
f b
z =\Tree a
t ->Tree a -> b -> b
go Tree a
t b
z -- Use a lambda to allow inlining with two argumentswherego :: Tree a -> b -> b
go (Node a
x [Tree a]
ts )=a -> b -> b
f a
x (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Tree a -> (b -> b) -> b -> b) -> (b -> b) -> [Tree a] -> b -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr(\Tree a
t b -> b
k ->Tree a -> b -> b
go Tree a
t (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
.b -> b
k )b -> b
forall a. a -> a
id[Tree a]
ts -- This is equivalent to the following simpler definition, but has been found to optimize-- better in benchmarks:-- go (Node x ts) z' = f x (foldr go z' ts){-# INLINEfoldr#-}foldl' :: forall b a. (b -> a -> b) -> b -> Tree a -> b
foldl' b -> a -> b
f =b -> Tree a -> b
go wherego :: b -> Tree a -> b
go !b
z (Node a
x [Tree a]
ts )=(b -> Tree a -> b) -> b -> [Tree a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'b -> Tree a -> b
go (b -> a -> b
f b
z a
x )[Tree a]
ts {-# INLINEfoldl'#-}foldr1 :: forall a. (a -> a -> a) -> Tree a -> a
foldr1 =(a -> a) -> (a -> a -> a) -> Tree a -> a
forall a b. (a -> b) -> (a -> b -> b) -> Tree a -> b
foldrMap1 a -> a
forall a. a -> a
idfoldl1 :: forall a. (a -> a -> a) -> Tree a -> a
foldl1 =(a -> a) -> (a -> a -> a) -> Tree a -> a
forall a b. (a -> b) -> (b -> a -> b) -> Tree a -> b
foldlMap1 a -> a
forall a. a -> a
idnull :: forall a. Tree a -> Bool
null Tree a
_=Bool
False{-# INLINEnull#-}elem :: forall a. Eq a => a -> Tree a -> Bool
elem =(a -> Bool) -> Tree a -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any((a -> Bool) -> Tree a -> Bool)
-> (a -> a -> Bool) -> a -> Tree a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==){-# INLINABLEelem#-}maximum :: forall a. Ord a => Tree a -> a
maximum =(a -> a) -> (a -> a -> a) -> Tree a -> a
forall a b. (a -> b) -> (b -> a -> b) -> Tree a -> b
foldlMap1' a -> a
forall a. a -> a
ida -> a -> a
forall a. Ord a => a -> a -> a
max{-# INLINABLEmaximum#-}minimum :: forall a. Ord a => Tree a -> a
minimum =(a -> a) -> (a -> a -> a) -> Tree a -> a
forall a b. (a -> b) -> (b -> a -> b) -> Tree a -> b
foldlMap1' a -> a
forall a. a -> a
ida -> a -> a
forall a. Ord a => a -> a -> a
min{-# INLINABLEminimum#-}sum :: forall a. Num a => Tree a -> a
sum =(a -> a) -> (a -> a -> a) -> Tree a -> a
forall a b. (a -> b) -> (b -> a -> b) -> Tree a -> b
foldlMap1' a -> a
forall a. a -> a
ida -> a -> a
forall a. Num a => a -> a -> a
(+){-# INLINABLEsum#-}product :: forall a. Num a => Tree a -> a
product =(a -> a) -> (a -> a -> a) -> Tree a -> a
forall a b. (a -> b) -> (b -> a -> b) -> Tree a -> b
foldlMap1' a -> a
forall a. a -> a
ida -> a -> a
forall a. Num a => a -> a -> a
(*){-# INLINABLEproduct#-}
#if MIN_VERSION_base(4,18,0)
-- | Folds in pre-order.---- @since 0.6.7-- See Note [Implemented Foldable1 Tree functions]instanceFoldable1.Foldable1Tree wherefoldMap1 :: forall m a. Semigroup m => (a -> m) -> Tree a -> m
foldMap1 a -> m
f =Tree a -> m
go where-- We'd like to write---- go (Node x (t : ts)) = f x <> Foldable1.foldMap1 go (t :| ts)---- but foldMap1 for NonEmpty isn't very good, so we don't. See-- https://github.com/haskell/containers/pull/921#issuecomment-1410398618go :: Tree a -> m
go (Node a
x [])=a -> m
f a
x go (Node a
x (Tree a
t :[Tree a]
ts ))=a -> m
f a
x m -> m -> m
forall a. Semigroup a => a -> a -> a
<>(Tree a -> m) -> (Tree a -> m -> m) -> NonEmpty (Tree a) -> m
forall a b. (a -> b) -> (a -> b -> b) -> NonEmpty a -> b
forall (t :: * -> *) a b.
Foldable1 t =>
(a -> b) -> (a -> b -> b) -> t a -> b
Foldable1.foldrMap1Tree a -> m
go (\Tree a
t' m
z ->Tree a -> m
go Tree a
t' m -> m -> m
forall a. Semigroup a => a -> a -> a
<>m
z )(Tree a
t Tree a -> [Tree a] -> NonEmpty (Tree a)
forall a. a -> [a] -> NonEmpty a
:|[Tree a]
ts ){-# INLINEfoldMap1#-}foldMap1' :: forall m a. Semigroup m => (a -> m) -> Tree a -> m
foldMap1' a -> m
f =(a -> m) -> (m -> a -> m) -> Tree a -> m
forall a b. (a -> b) -> (b -> a -> b) -> Tree a -> b
foldlMap1' a -> m
f (\m
z a
x ->m
z m -> m -> m
forall a. Semigroup a => a -> a -> a
<>a -> m
f a
x ){-# INLINEfoldMap1'#-}toNonEmpty :: forall a. Tree a -> NonEmpty a
toNonEmpty (Node a
x [Tree a]
ts )=a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:|(Tree a -> [a]) -> [Tree a] -> [a]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMapTree a -> [a]
forall a. Tree a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList[Tree a]
ts maximum :: forall a. Ord a => Tree a -> a
maximum =Tree a -> a
forall a. Ord a => Tree a -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
Foldable.maximum{-# INLINABLEmaximum#-}minimum :: forall a. Ord a => Tree a -> a
minimum =Tree a -> a
forall a. Ord a => Tree a -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
Foldable.minimum{-# INLINABLEminimum#-}foldrMap1 :: forall a b. (a -> b) -> (a -> b -> b) -> Tree a -> b
foldrMap1=(a -> b) -> (a -> b -> b) -> Tree a -> b
forall a b. (a -> b) -> (a -> b -> b) -> Tree a -> b
foldrMap1 foldlMap1' :: forall a b. (a -> b) -> (b -> a -> b) -> Tree a -> b
foldlMap1' =(a -> b) -> (b -> a -> b) -> Tree a -> b
forall a b. (a -> b) -> (b -> a -> b) -> Tree a -> b
foldlMap1' foldlMap1 :: forall a b. (a -> b) -> (b -> a -> b) -> Tree a -> b
foldlMap1 =(a -> b) -> (b -> a -> b) -> Tree a -> b
forall a b. (a -> b) -> (b -> a -> b) -> Tree a -> b
foldlMap1 
#endif
foldrMap1 ::(a ->b )->(a ->b ->b )->Tree a ->b foldrMap1 :: forall a b. (a -> b) -> (a -> b -> b) -> Tree a -> b
foldrMap1 a -> b
f a -> b -> b
g =Tree a -> b
go wherego :: Tree a -> b
go (Node a
x [])=a -> b
f a
x go (Node a
x (Tree a
t :[Tree a]
ts ))=a -> b -> b
g a
x ((Tree a -> b) -> (Tree a -> b -> b) -> Tree a -> [Tree a] -> b
forall a b. (a -> b) -> (a -> b -> b) -> a -> [a] -> b
foldrMap1NE Tree a -> b
go (\Tree a
t' b
z ->(a -> b -> b) -> b -> Tree a -> b
forall a b. (a -> b -> b) -> b -> Tree a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldra -> b -> b
g b
z Tree a
t' )Tree a
t [Tree a]
ts ){-# INLINEfoldrMap1 #-}-- This is foldrMap1 for Data.List.NonEmpty, but is not available before-- base 4.18.foldrMap1NE ::(a ->b )->(a ->b ->b )->a ->[a ]->b foldrMap1NE :: forall a b. (a -> b) -> (a -> b -> b) -> a -> [a] -> b
foldrMap1NE a -> b
f a -> b -> b
g =a -> [a] -> b
go wherego :: a -> [a] -> b
go a
x []=a -> b
f a
x go a
x (a
x' :[a]
xs )=a -> b -> b
g a
x (a -> [a] -> b
go a
x' [a]
xs ){-# INLINEfoldrMap1NE #-}foldlMap1' ::(a ->b )->(b ->a ->b )->Tree a ->b foldlMap1' :: forall a b. (a -> b) -> (b -> a -> b) -> Tree a -> b
foldlMap1' a -> b
f b -> a -> b
g =-- Use a lambda to allow inlining with two arguments\(Node a
x [Tree a]
ts )->(b -> Tree a -> b) -> b -> [Tree a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'((b -> a -> b) -> b -> Tree a -> b
forall b a. (b -> a -> b) -> b -> Tree a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'b -> a -> b
g )(a -> b
f a
x )[Tree a]
ts {-# INLINEfoldlMap1' #-}foldlMap1 ::(a ->b )->(b ->a ->b )->Tree a ->b foldlMap1 :: forall a b. (a -> b) -> (b -> a -> b) -> Tree a -> b
foldlMap1 a -> b
f b -> a -> b
g =-- Use a lambda to allow inlining with two arguments\(Node a
x [Tree a]
ts )->(b -> Tree a -> b) -> b -> [Tree a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl((b -> a -> b) -> b -> Tree a -> b
forall b a. (b -> a -> b) -> b -> Tree a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldlb -> a -> b
g )(a -> b
f a
x )[Tree a]
ts {-# INLINEfoldlMap1 #-}instanceNFDataa =>NFData(Tree a )wherernf :: Tree a -> ()
rnf(Node a
x [Tree a]
ts )=a -> ()
forall a. NFData a => a -> ()
rnfa
x () -> () -> ()
forall a b. a -> b -> b
`seq`[Tree a] -> ()
forall a. NFData a => a -> ()
rnf[Tree a]
ts -- | @since 0.8instanceNFData1Tree whereliftRnf :: forall a. (a -> ()) -> Tree a -> ()
liftRnfa -> ()
rnfx =Tree a -> ()
go wherego :: Tree a -> ()
go (Node a
x [Tree a]
ts )=a -> ()
rnfx a
x () -> () -> ()
forall a b. a -> b -> b
`seq`(Tree a -> ()) -> [Tree a] -> ()
forall a. (a -> ()) -> [a] -> ()
forall (f :: * -> *) a. NFData1 f => (a -> ()) -> f a -> ()
liftRnfTree a -> ()
go [Tree a]
ts -- | @since 0.5.10.1instanceMonadZipTree wheremzipWith :: forall a b c. (a -> b -> c) -> Tree a -> Tree b -> Tree c
mzipWith a -> b -> c
f (Node a
a [Tree a]
as )(Node b
b [Tree b]
bs )=c -> [Tree c] -> Tree c
forall a. a -> [Tree a] -> Tree a
Node (a -> b -> c
f a
a b
b )((Tree a -> Tree b -> Tree c) -> [Tree a] -> [Tree b] -> [Tree c]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
forall (m :: * -> *) a b c.
MonadZip m =>
(a -> b -> c) -> m a -> m b -> m c
mzipWith((a -> b -> c) -> Tree a -> Tree b -> Tree c
forall a b c. (a -> b -> c) -> Tree a -> Tree b -> Tree c
forall (m :: * -> *) a b c.
MonadZip m =>
(a -> b -> c) -> m a -> m b -> m c
mzipWitha -> b -> c
f )[Tree a]
as [Tree b]
bs )munzip :: forall a b. Tree (a, b) -> (Tree a, Tree b)
munzip (Node (a
a ,b
b )[Tree (a, b)]
ts )=(a -> [Tree a] -> Tree a
forall a. a -> [Tree a] -> Tree a
Node a
a [Tree a]
as ,b -> [Tree b] -> Tree b
forall a. a -> [Tree a] -> Tree a
Node b
b [Tree b]
bs )where([Tree a]
as ,[Tree b]
bs )=[(Tree a, Tree b)] -> ([Tree a], [Tree b])
forall a b. [(a, b)] -> ([a], [b])
forall (m :: * -> *) a b. MonadZip m => m (a, b) -> (m a, m b)
munzip((Tree (a, b) -> (Tree a, Tree b))
-> [Tree (a, b)] -> [(Tree a, Tree b)]
forall a b. (a -> b) -> [a] -> [b]
mapTree (a, b) -> (Tree a, Tree b)
forall a b. Tree (a, b) -> (Tree a, Tree b)
forall (m :: * -> *) a b. MonadZip m => m (a, b) -> (m a, m b)
munzip[Tree (a, b)]
ts )-- | 2-dimensional ASCII drawing of a tree.---- ==== __Examples__---- > putStr $ drawTree $ fmap show (Node 1 [Node 2 [], Node 3 []])---- @-- 1-- |-- +- 2-- |-- `- 3-- @--drawTree ::Tree String->StringdrawTree :: Tree String -> String
drawTree =[String] -> String
unlines([String] -> String)
-> (Tree String -> [String]) -> Tree String -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Tree String -> [String]
draw -- | 2-dimensional ASCII drawing of a forest.---- ==== __Examples__---- > putStr $ drawForest $ map (fmap show) [(Node 1 [Node 2 [], Node 3 []]), (Node 10 [Node 20 []])]---- @-- 1-- |-- +- 2-- |-- `- 3---- 10-- |-- `- 20-- @--drawForest ::[Tree String]->StringdrawForest :: [Tree String] -> String
drawForest =[String] -> String
unlines([String] -> String)
-> ([Tree String] -> [String]) -> [Tree String] -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Tree String -> String) -> [Tree String] -> [String]
forall a b. (a -> b) -> [a] -> [b]
mapTree String -> String
drawTree draw ::Tree String->[String]draw :: Tree String -> [String]
draw (Node String
x [Tree String]
ts0 )=String -> [String]
linesString
x [String] -> [String] -> [String]
forall a. [a] -> [a] -> [a]
++[Tree String] -> [String]
drawSubTrees [Tree String]
ts0 wheredrawSubTrees :: [Tree String] -> [String]
drawSubTrees []=[]drawSubTrees [Tree String
t ]=String
"|"String -> [String] -> [String]
forall a. a -> [a] -> [a]
:String -> String -> [String] -> [String]
forall {a}. [a] -> [a] -> [[a]] -> [[a]]
shift String
"`- "String
" "(Tree String -> [String]
draw Tree String
t )drawSubTrees (Tree String
t :[Tree String]
ts )=String
"|"String -> [String] -> [String]
forall a. a -> [a] -> [a]
:String -> String -> [String] -> [String]
forall {a}. [a] -> [a] -> [[a]] -> [[a]]
shift String
"+- "String
"| "(Tree String -> [String]
draw Tree String
t )[String] -> [String] -> [String]
forall a. [a] -> [a] -> [a]
++[Tree String] -> [String]
drawSubTrees [Tree String]
ts shift :: [a] -> [a] -> [[a]] -> [[a]]
shift [a]
first [a]
other =([a] -> [a] -> [a]) -> [[a]] -> [[a]] -> [[a]]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith[a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
(++)([a]
first [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[a] -> [[a]]
forall a. a -> [a]
repeat[a]
other )-- | Returns the elements of a tree in pre-order.---- @flatten == Data.Foldable.'toList'@---- @---- a-- / \\ => [a,b,c]-- b c-- @---- ==== __Examples__---- > flatten (Node 1 [Node 2 [], Node 3 []]) == [1,2,3]flatten ::Tree a ->[a ]flatten :: forall a. Tree a -> [a]
flatten =Tree a -> [a]
forall a. Tree a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList-- | Returns the list of nodes at each level of the tree.---- @---- a-- / \\ => [[a], [b,c]]-- b c-- @---- ==== __Examples__---- > levels (Node 1 [Node 2 [], Node 3 []]) == [[1],[2,3]]--levels ::Tree a ->[[a ]]levels :: forall a. Tree a -> [[a]]
levels Tree a
t =([Tree a] -> [a]) -> [[Tree a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map((Tree a -> a) -> [Tree a] -> [a]
forall a b. (a -> b) -> [a] -> [b]
mapTree a -> a
forall a. Tree a -> a
rootLabel )([[Tree a]] -> [[a]]) -> [[Tree a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$([Tree a] -> Bool) -> [[Tree a]] -> [[Tree a]]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile(Bool -> Bool
not(Bool -> Bool) -> ([Tree a] -> Bool) -> [Tree a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.[Tree a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null)([[Tree a]] -> [[Tree a]]) -> [[Tree a]] -> [[Tree a]]
forall a b. (a -> b) -> a -> b
$([Tree a] -> [Tree a]) -> [Tree a] -> [[Tree a]]
forall a. (a -> a) -> a -> [a]
iterate((Tree a -> [Tree a]) -> [Tree a] -> [Tree a]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMapTree a -> [Tree a]
forall a. Tree a -> [Tree a]
subForest )[Tree a
t ]-- | Fold a tree into a "summary" value.---- For each node in the tree, apply @f@ to the @rootLabel@ and the result-- of applying @f@ to each @subForest@.---- This is also known as the catamorphism on trees.---- ==== __Examples__---- Sum the values in a tree:---- > foldTree (\x xs -> sum (x:xs)) (Node 1 [Node 2 [], Node 3 []]) == 6---- Find the maximum value in the tree:---- > foldTree (\x xs -> maximum (x:xs)) (Node 1 [Node 2 [], Node 3 []]) == 3---- Count the number of leaves in the tree:---- > foldTree (\_ xs -> if null xs then 1 else sum xs) (Node 1 [Node 2 [], Node 3 []]) == 2---- Find depth of the tree; i.e. the number of branches from the root of the tree to the furthest leaf:---- > foldTree (\_ xs -> if null xs then 0 else 1 + maximum xs) (Node 1 [Node 2 [], Node 3 []]) == 1---- You can even implement traverse using foldTree:---- > traverse' f = foldTree (\x xs -> liftA2 Node (f x) (sequenceA xs))------ @since 0.5.8foldTree ::(a ->[b ]->b )->Tree a ->b foldTree :: forall a b. (a -> [b] -> b) -> Tree a -> b
foldTree a -> [b] -> b
f =Tree a -> b
go wherego :: Tree a -> b
go (Node a
x [Tree a]
ts )=a -> [b] -> b
f a
x ((Tree a -> b) -> [Tree a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
mapTree a -> b
go [Tree a]
ts )-- | Build a (possibly infinite) tree from a seed value.---- @unfoldTree f b@ constructs a tree by starting with the tree-- @Node { rootLabel=b, subForest=[] }@ and repeatedly applying @f@ to each-- 'rootLabel' value in the tree's leaves to generate its 'subForest'.---- For a monadic version, see 'unfoldTreeM' (depth-first) and-- 'unfoldTreeM_BF' (breadth-first).---- ==== __Examples__---- Construct the tree of @Integer@s where each node has two children:-- @left = 2*x@ and @right = 2*x + 1@, where @x@ is the 'rootLabel' of the node.-- Stop when the values exceed 7.---- > let buildNode x = if 2*x + 1 > 7 then (x, []) else (x, [2*x, 2*x+1])-- > putStr $ drawTree $ fmap show $ unfoldTree buildNode 1---- @---- 1-- |-- +- 2-- | |-- | +- 4-- | |-- | `- 5-- |-- `- 3-- |-- +- 6-- |-- `- 7-- @--unfoldTree ::(b ->(a ,[b ]))->b ->Tree a unfoldTree :: forall b a. (b -> (a, [b])) -> b -> Tree a
unfoldTree b -> (a, [b])
f b
b =let(a
a ,[b]
bs )=b -> (a, [b])
f b
b ina -> [Tree a] -> Tree a
forall a. a -> [Tree a] -> Tree a
Node a
a ((b -> (a, [b])) -> [b] -> [Tree a]
forall b a. (b -> (a, [b])) -> [b] -> [Tree a]
unfoldForest b -> (a, [b])
f [b]
bs )-- | Build a (possibly infinite) forest from a list of seed values.---- @unfoldForest f seeds@ invokes 'unfoldTree' on each seed value.---- For a monadic version, see 'unfoldForestM' (depth-first) and-- 'unfoldForestM_BF' (breadth-first).--unfoldForest ::(b ->(a ,[b ]))->[b ]->[Tree a ]unfoldForest :: forall b a. (b -> (a, [b])) -> [b] -> [Tree a]
unfoldForest b -> (a, [b])
f =(b -> Tree a) -> [b] -> [Tree a]
forall a b. (a -> b) -> [a] -> [b]
map((b -> (a, [b])) -> b -> Tree a
forall b a. (b -> (a, [b])) -> b -> Tree a
unfoldTree b -> (a, [b])
f )-- | Monadic tree builder, in depth-first order.unfoldTreeM ::Monadm =>(b ->m (a ,[b ]))->b ->m (Tree a )unfoldTreeM :: forall (m :: * -> *) b a.
Monad m =>
(b -> m (a, [b])) -> b -> m (Tree a)
unfoldTreeM b -> m (a, [b])
f b
b =do(a
a ,[b]
bs )<-b -> m (a, [b])
f b
b [Tree a]
ts <-(b -> m (a, [b])) -> [b] -> m [Tree a]
forall (m :: * -> *) b a.
Monad m =>
(b -> m (a, [b])) -> [b] -> m [Tree a]
unfoldForestM b -> m (a, [b])
f [b]
bs Tree a -> m (Tree a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return(a -> [Tree a] -> Tree a
forall a. a -> [Tree a] -> Tree a
Node a
a [Tree a]
ts )-- | Monadic forest builder, in depth-first order.unfoldForestM ::Monadm =>(b ->m (a ,[b ]))->[b ]->m ([Tree a ])unfoldForestM :: forall (m :: * -> *) b a.
Monad m =>
(b -> m (a, [b])) -> [b] -> m [Tree a]
unfoldForestM b -> m (a, [b])
f =(b -> m (Tree a)) -> [b] -> m [Tree a]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> [a] -> m [b]
Prelude.mapM((b -> m (a, [b])) -> b -> m (Tree a)
forall (m :: * -> *) b a.
Monad m =>
(b -> m (a, [b])) -> b -> m (Tree a)
unfoldTreeM b -> m (a, [b])
f )-- | Monadic tree builder, in breadth-first order.---- See 'unfoldTree' for more info.---- Implemented using an algorithm adapted from-- /Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design/,-- by Chris Okasaki, /ICFP'00/.unfoldTreeM_BF ::Monadm =>(b ->m (a ,[b ]))->b ->m (Tree a )unfoldTreeM_BF :: forall (m :: * -> *) b a.
Monad m =>
(b -> m (a, [b])) -> b -> m (Tree a)
unfoldTreeM_BF b -> m (a, [b])
f b
b =(Seq (Tree a) -> Tree a) -> m (Seq (Tree a)) -> m (Tree a)
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftMSeq (Tree a) -> Tree a
forall {a}. Seq a -> a
getElement (m (Seq (Tree a)) -> m (Tree a)) -> m (Seq (Tree a)) -> m (Tree a)
forall a b. (a -> b) -> a -> b
$(b -> m (a, [b])) -> Seq b -> m (Seq (Tree a))
forall (m :: * -> *) b a.
Monad m =>
(b -> m (a, [b])) -> Seq b -> m (Seq (Tree a))
unfoldForestQ b -> m (a, [b])
f (b -> Seq b
forall a. a -> Seq a
singleton b
b )wheregetElement :: Seq a -> a
getElement Seq a
xs =caseSeq a -> ViewL a
forall a. Seq a -> ViewL a
viewl Seq a
xs ofa
x :< Seq a
_->a
x ViewL a
EmptyL ->String -> a
forall a. HasCallStack => String -> a
errorString
"unfoldTreeM_BF"-- | Monadic forest builder, in breadth-first order.---- See 'unfoldForest' for more info.---- Implemented using an algorithm adapted from-- /Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design/,-- by Chris Okasaki, /ICFP'00/.unfoldForestM_BF ::Monadm =>(b ->m (a ,[b ]))->[b ]->m ([Tree a ])unfoldForestM_BF :: forall (m :: * -> *) b a.
Monad m =>
(b -> m (a, [b])) -> [b] -> m [Tree a]
unfoldForestM_BF b -> m (a, [b])
f =(Seq (Tree a) -> [Tree a]) -> m (Seq (Tree a)) -> m [Tree a]
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftMSeq (Tree a) -> [Tree a]
forall a. Seq a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList(m (Seq (Tree a)) -> m [Tree a])
-> ([b] -> m (Seq (Tree a))) -> [b] -> m [Tree a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(b -> m (a, [b])) -> Seq b -> m (Seq (Tree a))
forall (m :: * -> *) b a.
Monad m =>
(b -> m (a, [b])) -> Seq b -> m (Seq (Tree a))
unfoldForestQ b -> m (a, [b])
f (Seq b -> m (Seq (Tree a)))
-> ([b] -> Seq b) -> [b] -> m (Seq (Tree a))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.[b] -> Seq b
forall a. [a] -> Seq a
fromList -- Takes a sequence (queue) of seeds and produces a sequence (reversed queue) of-- trees of the same length.unfoldForestQ ::Monadm =>(b ->m (a ,[b ]))->Seq b ->m (Seq (Tree a ))unfoldForestQ :: forall (m :: * -> *) b a.
Monad m =>
(b -> m (a, [b])) -> Seq b -> m (Seq (Tree a))
unfoldForestQ b -> m (a, [b])
f Seq b
aQ =caseSeq b -> ViewL b
forall a. Seq a -> ViewL a
viewl Seq b
aQ ofViewL b
EmptyL ->Seq (Tree a) -> m (Seq (Tree a))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
returnSeq (Tree a)
forall a. Seq a
empty b
a :< Seq b
aQ' ->do(a
b ,[b]
as )<-b -> m (a, [b])
f b
a Seq (Tree a)
tQ <-(b -> m (a, [b])) -> Seq b -> m (Seq (Tree a))
forall (m :: * -> *) b a.
Monad m =>
(b -> m (a, [b])) -> Seq b -> m (Seq (Tree a))
unfoldForestQ b -> m (a, [b])
f ((Seq b -> b -> Seq b) -> Seq b -> [b] -> Seq b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Prelude.foldlSeq b -> b -> Seq b
forall a. Seq a -> a -> Seq a
(|>) Seq b
aQ' [b]
as )let(Seq (Tree a)
tQ' ,[Tree a]
ts )=[Tree a] -> [b] -> Seq (Tree a) -> (Seq (Tree a), [Tree a])
forall a' b'. [a'] -> [b'] -> Seq a' -> (Seq a', [a'])
splitOnto [][b]
as Seq (Tree a)
tQ Seq (Tree a) -> m (Seq (Tree a))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return(a -> [Tree a] -> Tree a
forall a. a -> [Tree a] -> Tree a
Node a
b [Tree a]
ts Tree a -> Seq (Tree a) -> Seq (Tree a)
forall a. a -> Seq a -> Seq a
<| Seq (Tree a)
tQ' )wheresplitOnto ::[a' ]->[b' ]->Seq a' ->(Seq a' ,[a' ])splitOnto :: forall a' b'. [a'] -> [b'] -> Seq a' -> (Seq a', [a'])
splitOnto [a']
as []Seq a'
q =(Seq a'
q ,[a']
as )splitOnto [a']
as (b'
_:[b']
bs )Seq a'
q =caseSeq a' -> ViewR a'
forall a. Seq a -> ViewR a
viewr Seq a'
q ofSeq a'
q' :> a'
a ->[a'] -> [b'] -> Seq a' -> (Seq a', [a'])
forall a' b'. [a'] -> [b'] -> Seq a' -> (Seq a', [a'])
splitOnto (a'
a a' -> [a'] -> [a']
forall a. a -> [a] -> [a]
:[a']
as )[b']
bs Seq a'
q' ViewR a'
EmptyR ->String -> (Seq a', [a'])
forall a. HasCallStack => String -> a
errorString
"unfoldForestQ"-- | \(O(n)\). The leaves of the tree in left-to-right order.---- A leaf is a node with no children.---- ==== __Examples__---- >>> :{-- leaves $-- Node 1-- [ Node 2-- [ Node 4 []-- , Node 5 []-- ]-- , Node 3-- [ Node 6 []-- ]-- ]-- :}-- [4,5,6]-- >>> leaves (Node "root" [])-- ["root"]---- @since 0.8leaves ::Tree a ->[a ]
#ifdef __GLASGOW_HASKELL__
leaves :: forall a. Tree a -> [a]
leaves Tree a
t =(forall b. (a -> b -> b) -> b -> b) -> [a]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
GHC.Exts.build((forall b. (a -> b -> b) -> b -> b) -> [a])
-> (forall b. (a -> b -> b) -> b -> b) -> [a]
forall a b. (a -> b) -> a -> b
$\a -> b -> b
cons b
nil ->letgo :: Tree a -> b -> b
go (Node a
x [])b
z =a -> b -> b
cons a
x b
z go (Node a
_[Tree a]
ts )b
z =(Tree a -> b -> b) -> b -> [Tree a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldrTree a -> b -> b
go b
z [Tree a]
ts inTree a -> b -> b
go Tree a
t b
nil {-# INLINEleaves #-}-- Inline for list fusion
#else
leavest=letgo(Nodex[])z=x:zgo(Node_ts)z=foldrgoztsingot[]
#endif
-- | \(O(n)\). The edges of the tree as parent-child pairs in pre-order.---- A tree with \(n\) nodes has \(n-1\) edges.---- ==== __Examples__---- >>> :{-- edges $-- Node 1-- [ Node 2-- [ Node 4 []-- , Node 5 []-- ]-- , Node 3-- [ Node 6 []-- ]-- ]-- :}-- [(1,2),(2,4),(2,5),(1,3),(3,6)]-- >>> edges (Node "root" [])-- []---- @since 0.8edges ::Tree a ->[(a ,a )]
#ifdef __GLASGOW_HASKELL__
edges :: forall a. Tree a -> [(a, a)]
edges (Node a
x0 [Tree a]
ts0 )=(forall b. ((a, a) -> b -> b) -> b -> b) -> [(a, a)]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
GHC.Exts.build((forall b. ((a, a) -> b -> b) -> b -> b) -> [(a, a)])
-> (forall b. ((a, a) -> b -> b) -> b -> b) -> [(a, a)]
forall a b. (a -> b) -> a -> b
$\(a, a) -> b -> b
cons b
nil ->letgo :: a -> b -> [Tree a] -> b
go a
p =(Tree a -> b -> b) -> b -> [Tree a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr(\(Node a
x [Tree a]
ts )b
z ->(a, a) -> b -> b
cons (a
p ,a
x )(a -> b -> [Tree a] -> b
go a
x b
z [Tree a]
ts ))ina -> b -> [Tree a] -> b
go a
x0 b
nil [Tree a]
ts0 {-# INLINEedges #-}-- Inline for list fusion
#else
edges(Nodex0ts0)=letgop=foldr(\(Nodexts)z->(p,x):goxzts)ingox0[]ts0
#endif
-- | \(O(n)\). Labels on the paths from each node to the root.---- ==== __Examples__---- >>> :{-- pathsToRoot $-- Node 1-- [ Node 2 []-- , Node 3 []-- ]-- :}-- Node {rootLabel = 1 :| [], subForest = [Node {rootLabel = 2 :| [1], subForest = []},Node {rootLabel = 3 :| [1], subForest = []}]}-- >>> pathsToRoot (Node "root" [])-- Node {rootLabel = "root" :| [], subForest = []}---- @since 0.8pathsToRoot ::Tree a ->Tree (NonEmptya )pathsToRoot :: forall a. Tree a -> Tree (NonEmpty a)
pathsToRoot =[a] -> Tree a -> Tree (NonEmpty a)
forall {a}. [a] -> Tree a -> Tree (NonEmpty a)
go []wherego :: [a] -> Tree a -> Tree (NonEmpty a)
go [a]
ps (Node a
x [Tree a]
ts )=NonEmpty a -> [Tree (NonEmpty a)] -> Tree (NonEmpty a)
forall a. a -> [Tree a] -> Tree a
Node (a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:|[a]
ps )((Tree a -> Tree (NonEmpty a)) -> [Tree a] -> [Tree (NonEmpty a)]
forall a b. (a -> b) -> [a] -> [b]
map([a] -> Tree a -> Tree (NonEmpty a)
go (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ps ))[Tree a]
ts )-- | Labels on the paths from the root to each node.---- If the path orientation is not important, consider using 'pathsToRoot'-- instead because it is more efficient.---- ==== __Examples__---- >>> :{-- pathsFromRoot $-- Node 1-- [ Node 2 []-- , Node 3 []-- ]-- :}-- Node {rootLabel = 1 :| [], subForest = [Node {rootLabel = 1 :| [2], subForest = []},Node {rootLabel = 1 :| [3], subForest = []}]}-- >>> pathsFromRoot (Node "root" [])-- Node {rootLabel = "root" :| [], subForest = []}---- @since 0.8-- See Note [pathsFromRoot implementation]pathsFromRoot ::Tree a ->Tree (NonEmptya )pathsFromRoot :: forall a. Tree a -> Tree (NonEmpty a)
pathsFromRoot (Node a
x0 [Tree a]
ts0 )=NonEmpty a -> [Tree (NonEmpty a)] -> Tree (NonEmpty a)
forall a. a -> [Tree a] -> Tree a
Node (a
x0 a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:|[])((Tree a -> Tree (NonEmpty a)) -> [Tree a] -> [Tree (NonEmpty a)]
forall a b. (a -> b) -> [a] -> [b]
map(BQ a -> Tree a -> Tree (NonEmpty a)
forall {a}. BQ a -> Tree a -> Tree (NonEmpty a)
go (a -> BQ a
forall a. a -> BQ a
singletonBQ a
x0 ))[Tree a]
ts0 )wherego :: BQ a -> Tree a -> Tree (NonEmpty a)
go !BQ a
q (Node a
x [Tree a]
ts )=NonEmpty a -> [Tree (NonEmpty a)] -> Tree (NonEmpty a)
forall a. a -> [Tree a] -> Tree a
Node (BQ a -> NonEmpty a
forall a. BQ a -> NonEmpty a
toNonEmptyBQ BQ a
q' )((Tree a -> Tree (NonEmpty a)) -> [Tree a] -> [Tree (NonEmpty a)]
forall a b. (a -> b) -> [a] -> [b]
map(BQ a -> Tree a -> Tree (NonEmpty a)
go BQ a
q' )[Tree a]
ts )where!q' :: BQ a
q' =BQ a -> a -> BQ a
forall a. BQ a -> a -> BQ a
snocBQ BQ a
q a
x -- An implementation of Chris Okasaki's banker's queue.-- Invariant: length front >= length reardataBQ a =BQ a -- head{-# UNPACK#-}!Word-- length front + length rear[a ]-- front![a ]-- rear (reversed)singletonBQ ::a ->BQ a singletonBQ :: forall a. a -> BQ a
singletonBQ a
x =a -> Word -> [a] -> [a] -> BQ a
forall a. a -> Word -> [a] -> [a] -> BQ a
BQ a
x Word
0[][]snocBQ ::BQ a ->a ->BQ a snocBQ :: forall a. BQ a -> a -> BQ a
snocBQ (BQ a
x0 Word
n [a]
f [a]
r )a
x |Bool
doReverse =a -> Word -> [a] -> [a] -> BQ a
forall a. a -> Word -> [a] -> [a] -> BQ a
BQ a
x0 (Word
n Word -> Word -> Word
forall a. Num a => a -> a -> a
+Word
1)([a]
f [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++[a] -> [a]
forall a. [a] -> [a]
reverse(a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
r ))[]|Bool
otherwise=a -> Word -> [a] -> [a] -> BQ a
forall a. a -> Word -> [a] -> [a] -> BQ a
BQ a
x0 (Word
n Word -> Word -> Word
forall a. Num a => a -> a -> a
+Word
1)[a]
f (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
r )wheredoReverse :: Bool
doReverse =(Word
n Word -> Word -> Word
forall a. Num a => a -> a -> a
+Word
2)Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&.(Word
n Word -> Word -> Word
forall a. Num a => a -> a -> a
+Word
1)Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
==Word
0-- We reverse whenever the length of r would exceed that of f.-- This happens every time n+2 is a power of 2.toNonEmptyBQ ::BQ a ->NonEmptya toNonEmptyBQ :: forall a. BQ a -> NonEmpty a
toNonEmptyBQ (BQ a
x0 Word
_[a]
f [a]
r )=case[a]
r of[]->a
x0 a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:|[a]
f -- optimization, no need to rebuild f[a]
_->a
x0 a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:|([a]
f [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++[a] -> [a]
forall a. [a] -> [a]
reverse[a]
r )-- | A newtype over 'Tree' that folds and traverses in post-order.---- @since 0.8newtypePostOrder a =PostOrder {forall a. PostOrder a -> Tree a
unPostOrder ::Tree a }
#ifdef __GLASGOW_HASKELL__
deriving(PostOrder a -> PostOrder a -> Bool
(PostOrder a -> PostOrder a -> Bool)
-> (PostOrder a -> PostOrder a -> Bool) -> Eq (PostOrder a)
forall a. Eq a => PostOrder a -> PostOrder a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => PostOrder a -> PostOrder a -> Bool
== :: PostOrder a -> PostOrder a -> Bool
$c/= :: forall a. Eq a => PostOrder a -> PostOrder a -> Bool
/= :: PostOrder a -> PostOrder a -> Bool
Eq,Eq (PostOrder a)
Eq (PostOrder a) =>
(PostOrder a -> PostOrder a -> Ordering)
-> (PostOrder a -> PostOrder a -> Bool)
-> (PostOrder a -> PostOrder a -> Bool)
-> (PostOrder a -> PostOrder a -> Bool)
-> (PostOrder a -> PostOrder a -> Bool)
-> (PostOrder a -> PostOrder a -> PostOrder a)
-> (PostOrder a -> PostOrder a -> PostOrder a)
-> Ord (PostOrder a)
PostOrder a -> PostOrder a -> Bool
PostOrder a -> PostOrder a -> Ordering
PostOrder a -> PostOrder a -> PostOrder a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (PostOrder a)
forall a. Ord a => PostOrder a -> PostOrder a -> Bool
forall a. Ord a => PostOrder a -> PostOrder a -> Ordering
forall a. Ord a => PostOrder a -> PostOrder a -> PostOrder a
$ccompare :: forall a. Ord a => PostOrder a -> PostOrder a -> Ordering
compare :: PostOrder a -> PostOrder a -> Ordering
$c< :: forall a. Ord a => PostOrder a -> PostOrder a -> Bool
< :: PostOrder a -> PostOrder a -> Bool
$c<= :: forall a. Ord a => PostOrder a -> PostOrder a -> Bool
<= :: PostOrder a -> PostOrder a -> Bool
$c> :: forall a. Ord a => PostOrder a -> PostOrder a -> Bool
> :: PostOrder a -> PostOrder a -> Bool
$c>= :: forall a. Ord a => PostOrder a -> PostOrder a -> Bool
>= :: PostOrder a -> PostOrder a -> Bool
$cmax :: forall a. Ord a => PostOrder a -> PostOrder a -> PostOrder a
max :: PostOrder a -> PostOrder a -> PostOrder a
$cmin :: forall a. Ord a => PostOrder a -> PostOrder a -> PostOrder a
min :: PostOrder a -> PostOrder a -> PostOrder a
Ord,ReadPrec [PostOrder a]
ReadPrec (PostOrder a)
Int -> ReadS (PostOrder a)
ReadS [PostOrder a]
(Int -> ReadS (PostOrder a))
-> ReadS [PostOrder a]
-> ReadPrec (PostOrder a)
-> ReadPrec [PostOrder a]
-> Read (PostOrder a)
forall a. Read a => ReadPrec [PostOrder a]
forall a. Read a => ReadPrec (PostOrder a)
forall a. Read a => Int -> ReadS (PostOrder a)
forall a. Read a => ReadS [PostOrder a]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: forall a. Read a => Int -> ReadS (PostOrder a)
readsPrec :: Int -> ReadS (PostOrder a)
$creadList :: forall a. Read a => ReadS [PostOrder a]
readList :: ReadS [PostOrder a]
$creadPrec :: forall a. Read a => ReadPrec (PostOrder a)
readPrec :: ReadPrec (PostOrder a)
$creadListPrec :: forall a. Read a => ReadPrec [PostOrder a]
readListPrec :: ReadPrec [PostOrder a]
Read,Int -> PostOrder a -> ShowS
[PostOrder a] -> ShowS
PostOrder a -> String
(Int -> PostOrder a -> ShowS)
-> (PostOrder a -> String)
-> ([PostOrder a] -> ShowS)
-> Show (PostOrder a)
forall a. Show a => Int -> PostOrder a -> ShowS
forall a. Show a => [PostOrder a] -> ShowS
forall a. Show a => PostOrder a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> PostOrder a -> ShowS
showsPrec :: Int -> PostOrder a -> ShowS
$cshow :: forall a. Show a => PostOrder a -> String
show :: PostOrder a -> String
$cshowList :: forall a. Show a => [PostOrder a] -> ShowS
showList :: [PostOrder a] -> ShowS
Show,Typeable (PostOrder a)
Typeable (PostOrder a) =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> PostOrder a -> c (PostOrder a))
-> (forall (c :: * -> *).
 (forall b r. Data b => c (b -> r) -> c r)
 -> (forall r. r -> c r) -> Constr -> c (PostOrder a))
-> (PostOrder a -> Constr)
-> (PostOrder a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
 Typeable t =>
 (forall d. Data d => c (t d)) -> Maybe (c (PostOrder a)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
 Typeable t =>
 (forall d e. (Data d, Data e) => c (t d e))
 -> Maybe (c (PostOrder a)))
-> ((forall b. Data b => b -> b) -> PostOrder a -> PostOrder a)
-> (forall r r'.
 (r -> r' -> r)
 -> r -> (forall d. Data d => d -> r') -> PostOrder a -> r)
-> (forall r r'.
 (r' -> r -> r)
 -> r -> (forall d. Data d => d -> r') -> PostOrder a -> r)
-> (forall u. (forall d. Data d => d -> u) -> PostOrder a -> [u])
-> (forall u.
 Int -> (forall d. Data d => d -> u) -> PostOrder a -> u)
-> (forall (m :: * -> *).
 Monad m =>
 (forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a))
-> (forall (m :: * -> *).
 MonadPlus m =>
 (forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a))
-> (forall (m :: * -> *).
 MonadPlus m =>
 (forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a))
-> Data (PostOrder a)
PostOrder a -> Constr
PostOrder a -> DataType
(forall b. Data b => b -> b) -> PostOrder a -> PostOrder a
forall a. Data a => Typeable (PostOrder a)
forall a. Data a => PostOrder a -> Constr
forall a. Data a => PostOrder a -> DataType
forall a.
Data a =>
(forall b. Data b => b -> b) -> PostOrder a -> PostOrder a
forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> PostOrder a -> u
forall a u.
Data a =>
(forall d. Data d => d -> u) -> PostOrder a -> [u]
forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PostOrder a -> r
forall a r r'.
Data a =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PostOrder a -> r
forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)
forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)
forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (PostOrder a)
forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PostOrder a -> c (PostOrder a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (PostOrder a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (PostOrder a))
forall a.
Typeable a =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
 (forall b r. Data b => c (b -> r) -> c r)
 -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
 Typeable t =>
 (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
 Typeable t =>
 (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
 (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
 (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
 Monad m =>
 (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
 MonadPlus m =>
 (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
 MonadPlus m =>
 (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> PostOrder a -> u
forall u. (forall d. Data d => d -> u) -> PostOrder a -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PostOrder a -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PostOrder a -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (PostOrder a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PostOrder a -> c (PostOrder a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (PostOrder a))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (PostOrder a))
$cgfoldl :: forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PostOrder a -> c (PostOrder a)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PostOrder a -> c (PostOrder a)
$cgunfold :: forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (PostOrder a)
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (PostOrder a)
$ctoConstr :: forall a. Data a => PostOrder a -> Constr
toConstr :: PostOrder a -> Constr
$cdataTypeOf :: forall a. Data a => PostOrder a -> DataType
dataTypeOf :: PostOrder a -> DataType
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (PostOrder a))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (PostOrder a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (PostOrder a))
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (PostOrder a))
$cgmapT :: forall a.
Data a =>
(forall b. Data b => b -> b) -> PostOrder a -> PostOrder a
gmapT :: (forall b. Data b => b -> b) -> PostOrder a -> PostOrder a
$cgmapQl :: forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PostOrder a -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PostOrder a -> r
$cgmapQr :: forall a r r'.
Data a =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PostOrder a -> r
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PostOrder a -> r
$cgmapQ :: forall a u.
Data a =>
(forall d. Data d => d -> u) -> PostOrder a -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> PostOrder a -> [u]
$cgmapQi :: forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> PostOrder a -> u
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> PostOrder a -> u
$cgmapM :: forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)
Data,(forall x. PostOrder a -> Rep (PostOrder a) x)
-> (forall x. Rep (PostOrder a) x -> PostOrder a)
-> Generic (PostOrder a)
forall x. Rep (PostOrder a) x -> PostOrder a
forall x. PostOrder a -> Rep (PostOrder a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (PostOrder a) x -> PostOrder a
forall a x. PostOrder a -> Rep (PostOrder a) x
$cfrom :: forall a x. PostOrder a -> Rep (PostOrder a) x
from :: forall x. PostOrder a -> Rep (PostOrder a) x
$cto :: forall a x. Rep (PostOrder a) x -> PostOrder a
to :: forall x. Rep (PostOrder a) x -> PostOrder a
Generic,(forall a. PostOrder a -> Rep1 PostOrder a)
-> (forall a. Rep1 PostOrder a -> PostOrder a)
-> Generic1 PostOrder
forall a. Rep1 PostOrder a -> PostOrder a
forall a. PostOrder a -> Rep1 PostOrder a
forall k (f :: k -> *).
(forall (a :: k). f a -> Rep1 f a)
-> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
$cfrom1 :: forall a. PostOrder a -> Rep1 PostOrder a
from1 :: forall a. PostOrder a -> Rep1 PostOrder a
$cto1 :: forall a. Rep1 PostOrder a -> PostOrder a
to1 :: forall a. Rep1 PostOrder a -> PostOrder a
Generic1,(forall (m :: * -> *). Quote m => PostOrder a -> m Exp)
-> (forall (m :: * -> *).
 Quote m =>
 PostOrder a -> Code m (PostOrder a))
-> Lift (PostOrder a)
forall a (m :: * -> *). (Lift a, Quote m) => PostOrder a -> m Exp
forall a (m :: * -> *).
(Lift a, Quote m) =>
PostOrder a -> Code m (PostOrder a)
forall t.
(forall (m :: * -> *). Quote m => t -> m Exp)
-> (forall (m :: * -> *). Quote m => t -> Code m t) -> Lift t
forall (m :: * -> *). Quote m => PostOrder a -> m Exp
forall (m :: * -> *).
Quote m =>
PostOrder a -> Code m (PostOrder a)
$clift :: forall a (m :: * -> *). (Lift a, Quote m) => PostOrder a -> m Exp
lift :: forall (m :: * -> *). Quote m => PostOrder a -> m Exp
$cliftTyped :: forall a (m :: * -> *).
(Lift a, Quote m) =>
PostOrder a -> Code m (PostOrder a)
liftTyped :: forall (m :: * -> *).
Quote m =>
PostOrder a -> Code m (PostOrder a)
Lift)
#else
deriving(Eq,Ord,Read,Show)
#endif
instanceFunctorPostOrder where
#ifdef __GLASGOW_HASKELL__
fmap :: forall a b. (a -> b) -> PostOrder a -> PostOrder b
fmap=(((a -> b) -> Tree a -> Tree b)
-> (a -> b) -> PostOrder a -> PostOrder b
forall {a} {b}.
((a -> b) -> Tree a -> Tree b)
-> (a -> b) -> PostOrder a -> PostOrder b
forall a b. Coercible a b => a -> b
coerce::((a ->b )->Tree a ->Tree b )->(a ->b )->PostOrder a ->PostOrder b )(a -> b) -> Tree a -> Tree b
forall a b. (a -> b) -> Tree a -> Tree b
fmapTree <$ :: forall a b. a -> PostOrder b -> PostOrder a
(<$)=((b -> Tree a -> Tree b) -> b -> PostOrder a -> PostOrder b
forall {b} {a}.
(b -> Tree a -> Tree b) -> b -> PostOrder a -> PostOrder b
forall a b. Coercible a b => a -> b
coerce::(b ->Tree a ->Tree b )->b ->PostOrder a ->PostOrder b )a -> Tree b -> Tree a
forall a b. a -> Tree b -> Tree a
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
(<$)
#else
fmapf=PostOrder.fmapTreef.unPostOrder(<$)x=PostOrder.(x<$).unPostOrder
#endif
-- See Note [Implemented Foldable Tree functions]instanceFoldablePostOrder wherefold :: forall m. Monoid m => PostOrder m -> m
fold=(m -> m) -> PostOrder m -> m
forall m a. Monoid m => (a -> m) -> PostOrder a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMapm -> m
forall a. a -> a
id{-# INLINABLEfold#-}foldMap :: forall m a. Monoid m => (a -> m) -> PostOrder a -> m
foldMap=(a -> m) -> PostOrder a -> m
forall (t :: * -> *) m a.
(Traversable t, Monoid m) =>
(a -> m) -> t a -> m
foldMapDefault{-# INLINEfoldMap#-}foldr :: forall a b. (a -> b -> b) -> b -> PostOrder a -> b
foldra -> b -> b
f b
z0 =\(PostOrder Tree a
t )->Tree a -> b -> b
go Tree a
t b
z0 -- Use a lambda to inline with two argumentswherego :: Tree a -> b -> b
go (Node a
x [Tree a]
ts )b
z =(Tree a -> b -> b) -> b -> [Tree a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldrTree a -> b -> b
go (a -> b -> b
f a
x b
z )[Tree a]
ts {-# INLINEfoldr#-}foldl' :: forall b a. (b -> a -> b) -> b -> PostOrder a -> b
foldl'b -> a -> b
f b
z0 =\(PostOrder Tree a
t )->b -> Tree a -> b
go b
z0 Tree a
t -- Use a lambda to inline with two argumentswherego :: b -> Tree a -> b
go !b
z (Node a
x [Tree a]
ts )=let!z' :: b
z' =(b -> Tree a -> b) -> b -> [Tree a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'b -> Tree a -> b
go b
z [Tree a]
ts inb -> a -> b
f b
z' a
x {-# INLINEfoldl'#-}foldr1 :: forall a. (a -> a -> a) -> PostOrder a -> a
foldr1=(a -> a) -> (a -> a -> a) -> PostOrder a -> a
forall a b. (a -> b) -> (a -> b -> b) -> PostOrder a -> b
foldrMap1PostOrder a -> a
forall a. a -> a
idfoldl1 :: forall a. (a -> a -> a) -> PostOrder a -> a
foldl1=(a -> a) -> (a -> a -> a) -> PostOrder a -> a
forall a b. (a -> b) -> (b -> a -> b) -> PostOrder a -> b
foldlMap1PostOrder a -> a
forall a. a -> a
idnull :: forall a. PostOrder a -> Bool
nullPostOrder a
_=Bool
False{-# INLINEnull#-}elem :: forall a. Eq a => a -> PostOrder a -> Bool
elem=(a -> Bool) -> PostOrder a -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any((a -> Bool) -> PostOrder a -> Bool)
-> (a -> a -> Bool) -> a -> PostOrder a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==){-# INLINABLEelem#-}maximum :: forall a. Ord a => PostOrder a -> a
maximum=(a -> a) -> (a -> a -> a) -> PostOrder a -> a
forall a b. (a -> b) -> (b -> a -> b) -> PostOrder a -> b
foldlMap1'PostOrder a -> a
forall a. a -> a
ida -> a -> a
forall a. Ord a => a -> a -> a
max{-# INLINABLEmaximum#-}minimum :: forall a. Ord a => PostOrder a -> a
minimum=(a -> a) -> (a -> a -> a) -> PostOrder a -> a
forall a b. (a -> b) -> (b -> a -> b) -> PostOrder a -> b
foldlMap1'PostOrder a -> a
forall a. a -> a
ida -> a -> a
forall a. Ord a => a -> a -> a
min{-# INLINABLEminimum#-}sum :: forall a. Num a => PostOrder a -> a
sum=(a -> a) -> (a -> a -> a) -> PostOrder a -> a
forall a b. (a -> b) -> (b -> a -> b) -> PostOrder a -> b
foldlMap1'PostOrder a -> a
forall a. a -> a
ida -> a -> a
forall a. Num a => a -> a -> a
(+){-# INLINABLEsum#-}product :: forall a. Num a => PostOrder a -> a
product=(a -> a) -> (a -> a -> a) -> PostOrder a -> a
forall a b. (a -> b) -> (b -> a -> b) -> PostOrder a -> b
foldlMap1'PostOrder a -> a
forall a. a -> a
ida -> a -> a
forall a. Num a => a -> a -> a
(*){-# INLINABLEproduct#-}instanceTraversablePostOrder wheretraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> PostOrder a -> f (PostOrder b)
traversea -> f b
f =\(PostOrder Tree a
t )->Tree b -> PostOrder b
forall a. Tree a -> PostOrder a
PostOrder (Tree b -> PostOrder b) -> f (Tree b) -> f (PostOrder b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>Tree a -> f (Tree b)
go Tree a
t wherego :: Tree a -> f (Tree b)
go (Node a
x [Tree a]
ts )=([Tree b] -> b -> Tree b) -> f [Tree b] -> f b -> f (Tree b)
forall a b c. (a -> b -> c) -> f a -> f b -> f c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2((b -> [Tree b] -> Tree b) -> [Tree b] -> b -> Tree b
forall a b c. (a -> b -> c) -> b -> a -> c
flipb -> [Tree b] -> Tree b
forall a. a -> [Tree a] -> Tree a
Node )((Tree a -> f (Tree b)) -> [Tree a] -> f [Tree b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverseTree a -> f (Tree b)
go [Tree a]
ts )(a -> f b
f a
x ){-# INLINEtraverse#-}
#if MIN_VERSION_base(4,18,0)
-- See Note [Implemented Foldable1 Tree functions]instanceFoldable1.Foldable1PostOrder wherefoldMap1 :: forall m a. Semigroup m => (a -> m) -> PostOrder a -> m
foldMap1a -> m
f =\(PostOrder Tree a
t )->Tree a -> m
go Tree a
t -- Use a lambda to inline with one argumentwherego :: Tree a -> m
go (Node a
x [])=a -> m
f a
x go (Node a
x (Tree a
t :[Tree a]
ts ))=(Tree a -> m) -> (Tree a -> m -> m) -> NonEmpty (Tree a) -> m
forall a b. (a -> b) -> (a -> b -> b) -> NonEmpty a -> b
forall (t :: * -> *) a b.
Foldable1 t =>
(a -> b) -> (a -> b -> b) -> t a -> b
Foldable1.foldrMap1Tree a -> m
go (\Tree a
t' m
z' ->Tree a -> m
go Tree a
t' m -> m -> m
forall a. Semigroup a => a -> a -> a
<>m
z' )(Tree a
t Tree a -> [Tree a] -> NonEmpty (Tree a)
forall a. a -> [a] -> NonEmpty a
:|[Tree a]
ts )m -> m -> m
forall a. Semigroup a => a -> a -> a
<>a -> m
f a
x {-# INLINEfoldMap1#-}foldMap1' :: forall m a. Semigroup m => (a -> m) -> PostOrder a -> m
foldMap1'a -> m
f =(a -> m) -> (m -> a -> m) -> PostOrder a -> m
forall a b. (a -> b) -> (b -> a -> b) -> PostOrder a -> b
foldlMap1'PostOrder a -> m
f (\m
z a
x ->m
z m -> m -> m
forall a. Semigroup a => a -> a -> a
<>a -> m
f a
x ){-# INLINEfoldMap1'#-}toNonEmpty :: forall a. PostOrder a -> NonEmpty a
toNonEmpty(PostOrder Tree a
t0 )=Tree a -> [a] -> NonEmpty a
forall {a}. Tree a -> [a] -> NonEmpty a
go Tree a
t0 []wherego :: Tree a -> [a] -> NonEmpty a
go (Node a
x [])[a]
z =a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:|[a]
z go (Node a
x (Tree a
t :[Tree a]
ts ))[a]
z =Tree a -> [a] -> NonEmpty a
go Tree a
t ((Tree a -> [a] -> [a]) -> [a] -> [Tree a] -> [a]
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr(\Tree a
t' [a]
z' ->(a -> [a] -> [a]) -> [a] -> PostOrder a -> [a]
forall a b. (a -> b -> b) -> b -> PostOrder a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr(:)[a]
z' (Tree a -> PostOrder a
forall a. Tree a -> PostOrder a
PostOrder Tree a
t' ))(a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
z )[Tree a]
ts )maximum :: forall a. Ord a => PostOrder a -> a
maximum=PostOrder a -> a
forall a. Ord a => PostOrder a -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
Foldable.maximum{-# INLINABLEmaximum#-}minimum :: forall a. Ord a => PostOrder a -> a
minimum=PostOrder a -> a
forall a. Ord a => PostOrder a -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
Foldable.minimum{-# INLINABLEminimum#-}foldrMap1 :: forall a b. (a -> b) -> (a -> b -> b) -> PostOrder a -> b
foldrMap1=(a -> b) -> (a -> b -> b) -> PostOrder a -> b
forall a b. (a -> b) -> (a -> b -> b) -> PostOrder a -> b
foldrMap1PostOrder foldlMap1' :: forall a b. (a -> b) -> (b -> a -> b) -> PostOrder a -> b
foldlMap1'=(a -> b) -> (b -> a -> b) -> PostOrder a -> b
forall a b. (a -> b) -> (b -> a -> b) -> PostOrder a -> b
foldlMap1'PostOrder foldlMap1 :: forall a b. (a -> b) -> (b -> a -> b) -> PostOrder a -> b
foldlMap1=(a -> b) -> (b -> a -> b) -> PostOrder a -> b
forall a b. (a -> b) -> (b -> a -> b) -> PostOrder a -> b
foldlMap1PostOrder 
#endif
foldrMap1PostOrder ::(a ->b )->(a ->b ->b )->PostOrder a ->b foldrMap1PostOrder :: forall a b. (a -> b) -> (a -> b -> b) -> PostOrder a -> b
foldrMap1PostOrder a -> b
f a -> b -> b
g =\(PostOrder (Node a
x [Tree a]
ts ))->(Tree a -> b -> b) -> b -> [Tree a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr(\Tree a
t b
z ->(a -> b -> b) -> b -> PostOrder a -> b
forall a b. (a -> b -> b) -> b -> PostOrder a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldra -> b -> b
g b
z (Tree a -> PostOrder a
forall a. Tree a -> PostOrder a
PostOrder Tree a
t ))(a -> b
f a
x )[Tree a]
ts {-# INLINEfoldrMap1PostOrder #-}foldlMap1PostOrder ::(a ->b )->(b ->a ->b )->PostOrder a ->b foldlMap1PostOrder :: forall a b. (a -> b) -> (b -> a -> b) -> PostOrder a -> b
foldlMap1PostOrder a -> b
f b -> a -> b
g =\(PostOrder Tree a
t )->Tree a -> b
go Tree a
t wherego :: Tree a -> b
go (Node a
x [])=a -> b
f a
x go (Node a
x (Tree a
t :[Tree a]
ts ))=b -> a -> b
g ((b -> Tree a -> b) -> b -> [Tree a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl(\b
z Tree a
t' ->(b -> a -> b) -> b -> PostOrder a -> b
forall b a. (b -> a -> b) -> b -> PostOrder a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldlb -> a -> b
g b
z (Tree a -> PostOrder a
forall a. Tree a -> PostOrder a
PostOrder Tree a
t' ))(Tree a -> b
go Tree a
t )[Tree a]
ts )a
x {-# INLINEfoldlMap1PostOrder #-}foldlMap1'PostOrder ::(a ->b )->(b ->a ->b )->PostOrder a ->b foldlMap1'PostOrder :: forall a b. (a -> b) -> (b -> a -> b) -> PostOrder a -> b
foldlMap1'PostOrder a -> b
f b -> a -> b
g =\(PostOrder Tree a
t )->Tree a -> b
go Tree a
t wherego :: Tree a -> b
go (Node a
x [])=a -> b
f a
x go (Node a
x (Tree a
t :[Tree a]
ts ))=let!z' :: b
z' =(b -> Tree a -> b) -> b -> [Tree a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'(\b
z Tree a
t' ->(b -> a -> b) -> b -> PostOrder a -> b
forall b a. (b -> a -> b) -> b -> PostOrder a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'b -> a -> b
g b
z (Tree a -> PostOrder a
forall a. Tree a -> PostOrder a
PostOrder Tree a
t' ))(Tree a -> b
go Tree a
t )[Tree a]
ts inb -> a -> b
g b
z' a
x {-# INLINEfoldlMap1'PostOrder #-}---------------------------------------------------------------------------------- Note [Implemented Foldable Tree functions]-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~---- Implemented:---- foldMap, foldr, foldl': Basic functions.-- fold, elem: Implemented same as the default definition, but INLINABLE to-- allow specialization.-- foldr1, foldl1, null, maximum, minimum: Implemented more efficiently than-- defaults since trees are non-empty.-- sum, product: Implemented as strict left folds. Defaults use the lazy foldMap-- before base 4.15.1.---- Not implemented:---- foldMap', toList, length: Defaults perform well.-- foldr', foldl: Unlikely to be used.-- Note [Implemented Foldable1 Tree functions]-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~---- Implemented:---- foldMap, foldrMap1, foldlMap1': Basic functions-- foldMap1': Implemented same as the default definition, but INLINABLE to-- allow specialization.-- toNonEmpty, foldlMap1: Implemented more efficiently than default.-- maximum, minimum: Uses Foldable's implementation.---- Not implemented:---- fold1, head: Defaults perform well.-- foldrMap1': Unlikely to be used.-- Note [pathsFromRoot implementation]-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~-- We use Okasaki's banker's queue for pathsFromRoot because it has some-- desirable properties when the result is consumed lazily.---- 1. Fully evaluating a node's NonEmpty takes O(d) time, where d is-- the depth of the node. This is optimal.-- 2. The elements in the NonEmpty are yielded lazily. Note that the worst case-- time to yield an element is not O(1), i.e. it is only amortized O(1).-- More than O(1) work is done when the next element requires forcing (++)-- suspensions or reversing a rear list. For example, yielding the head has-- to force O(log d) (++) and so takes O(log d) time.-- 3. It builds up some beneficial sharing. It is not possible to share the-- results since the lists have different ends, but we can share some-- intermediate structures. Consider m sibling nodes at depth d. The front-- list is shared between them in (front ++ rear1), (front ++ rear2), ...-- (front + rearm). Forcing a prefix of front in one list can take arbitrary-- amounts of time per element (total bounded by O(d)), but once it is-- forced, front is memoized and doing the same for any of the siblings will-- take O(1) per element.---- Alternatives:---- * Implement it like pathsToRoot and reverse the NonEmptys. This does satisfy-- point 1 above. On 2 there's a trade-off, it costs a full O(d) to access the-- head and O(1) per element after that. On 3 it compares poorly because there-- is no sharing. Accessing the heads of m siblings will take O(dm) compared-- to the current O(d + m).-- * Use Okasaki's real-time queues. This would guarantee O(1) per element, but-- has worse constant-factor overall and does not seem worth the trouble.---- GHC base also uses a banker's queue for Data.List.inits. inits is similar-- in nature to pathsFromRoot since a list is a tree where each node has one or-- zero children.