Module Data.Tree

Multi-way trees (aka rose trees) and forests.

Module

Data.Tree

Copyright

(c) The University of Glasgow 2002

License

BSD-style (see the file libraries/base/LICENSE)

This is a port of Haskell library code.

Imports

• import Data.Foldable as Foldable
• import Data.Monoid as Monoid
• import frege.Prelude as Prelude
• import Prelude.PreludeArrays as PreludeArrays
• import Prelude.PreludeBase as PreludeBase
• import Prelude.PreludeDecimal as PreludeDecimal
• import Prelude.PreludeIO as PreludeIO
• import Prelude.PreludeList as PreludeList
• import Prelude.PreludeMonad as PreludeMonad
• import Prelude.PreludeText as PreludeText
• import Java.util.Regex as Regexp
• import Data.Traversable as Traversable

Table of Content

• Definitions

  type Forest a = [Tree a]

  data Tree a

  drawTree ∷ Tree String → String

  drawForest ∷ Forest String → String

  draw ∷ Tree String → [String]

  flatten ∷ Tree a → [a]

  levels ∷ Tree a → [[a]]

  unfoldTree ∷ (b → (a, [b])) → b → Tree a

  unfoldForest ∷ (b → (a, [b])) → [b] → Forest a

  unfoldTreeM ∷ Monad m ⇒ (b → m (a, [b])) → b → m (Tree a)

  unfoldForestM ∷ Monad m ⇒ (b → m (a, [b])) → [b] → m (Forest a)

• Instances

  instance Applicative Tree

  instance Eq a ⇒ Eq (Tree a)

  instance Foldable Tree

  instance Functor Tree

  instance Monad Tree

  instance Show a ⇒ Show (Tree a)

  instance Traversable Tree

• Functions and Values by Type

Definitions

data Tree a

Multi-way trees, also known as rose trees.

Constructors

Node {rootLabel ∷ a, subForest ∷ Forest a}

Member Functions

rootLabel ∷ Tree 𝖆 → 𝖆

access field rootLabel

subForest ∷ Tree 𝖆 → Forest 𝖆

label value zero or more child trees

type Forest a = [Tree a]

drawTree ∷ Tree String → String

Neat 2-dimensional drawing of a tree.

drawForest ∷ Forest String → String

Neat 2-dimensional drawing of a forest.

draw ∷ Tree String → [String]

flatten ∷ Tree a → [a]

The elements of a tree in pre-order.

levels ∷ Tree a → [[a]]

Lists of nodes at each level of the tree.

unfoldTree ∷ (b → (a, [b])) → b → Tree a

Build a tree from a seed value

unfoldForest ∷ (b → (a, [b])) → [b] → Forest a

Build a forest from a list of seed values

unfoldTreeM ∷ Monad m ⇒ (b → m (a, [b])) → b → m (Tree a)

Monadic tree builder, in depth-first order

unfoldForestM ∷ Monad m ⇒ (b → m (a, [b])) → [b] → m (Forest a)

Monadic forest builder, in depth-first order

Instances

instance Applicative Tree

Member Functions

*> ∷ Tree 𝖆 → Tree 𝖇 → Tree 𝖇
infixl  4

inherited from Applicative.*>

<* ∷ Tree 𝖆 → Tree 𝖇 → Tree 𝖆
infixl  4

inherited from Applicative.<*

<*> ∷ Tree (𝖆→𝖇) → Tree 𝖆 → Tree 𝖇
infixl  4

pure ∷ 𝖆 → Tree 𝖆

instance Eq a ⇒ Eq (Tree a)

Member Functions

!= ∷ Eq 𝖆 ⇒ Tree 𝖆 → Tree 𝖆 → Bool
infix  7

inherited from Eq.!=

== ∷ Eq 𝖆 ⇒ Tree 𝖆 → Tree 𝖆 → Bool
infix  7

Function generated for derived instance.

hashCode ∷ Eq 𝖆 ⇒ Tree 𝖆 → Int

Function generated for derived instance.

instance Foldable Tree

Member Functions

fold ∷ Monoid 𝖆 ⇒ Tree 𝖆 → 𝖆

inherited from Foldable.fold

fold1 ∷ Semigroup 𝖆 ⇒ Tree 𝖆 → 𝖆

inherited from Foldable.fold1

foldMap ∷ Monoid 𝖇 ⇒ (𝖆 → 𝖇) → Tree 𝖆 → 𝖇

foldMap1 ∷ Semigroup 𝖇 ⇒ (𝖆 → 𝖇) → Tree 𝖆 → 𝖇

inherited from Foldable.foldMap1

foldl ∷ (𝖆 → 𝖇 → 𝖆) → 𝖆 → Tree 𝖇 → 𝖆

inherited from Foldable.foldl

foldl1 ∷ (𝖆 → 𝖆 → 𝖆) → Tree 𝖆 → 𝖆

inherited from Foldable.foldl1

foldr ∷ (𝖆 → 𝖇 → 𝖇) → 𝖇 → Tree 𝖆 → 𝖇

inherited from Foldable.foldr

foldr1 ∷ (𝖆 → 𝖆 → 𝖆) → Tree 𝖆 → 𝖆

inherited from Foldable.foldr1

instance Functor Tree

Member Functions

fmap ∷ (𝖆 → 𝖇) → Tree 𝖆 → Tree 𝖇
infixl  4

instance Monad Tree

Member Functions

>> ∷ Tree 𝖆 → Tree 𝖇 → Tree 𝖇
infixl  3

inherited from Monad.>>

>>= ∷ Tree 𝖆 → (𝖆 → Tree 𝖇) → Tree 𝖇
infixl  3

join ∷ Tree (Tree 𝖆) → Tree 𝖆

inherited from Monad.join

pure ∷ 𝖆 → Tree 𝖆

instance Show a ⇒ Show (Tree a)

Member Functions

display ∷ Show 𝖆 ⇒ Tree 𝖆 → String

inherited from Show.display

show ∷ Show 𝖆 ⇒ Tree 𝖆 → String

Function generated for derived instance.

showChars ∷ Show 𝖆 ⇒ Tree 𝖆 → [Char]

inherited from Show.showChars

showList ∷ Show 𝖆 ⇒ Forest 𝖆 → String → String

inherited from Show.showList

showsPrec ∷ Show 𝖆 ⇒ Int → Tree 𝖆 → String → String

inherited from Show.showsPrec

showsub ∷ Show 𝖆 ⇒ Tree 𝖆 → String

Function generated for derived instance.

instance Traversable Tree

Member Functions

mapM ∷ Monad 𝖈 ⇒ (𝖆 → 𝖈 𝖇) → Tree 𝖆 → 𝖈 (Tree 𝖇)

inherited from Traversable.mapM

sequence ∷ Monad 𝖇 ⇒ Tree (𝖇 𝖆) → 𝖇 (Tree 𝖆)

inherited from Traversable.sequence

sequenceA ∷ Applicative 𝖇 ⇒ Tree (𝖇 𝖆) → 𝖇 (Tree 𝖆)

inherited from Traversable.sequenceA

traverse ∷ Applicative 𝖈 ⇒ (𝖆 → 𝖈 𝖇) → Tree 𝖆 → 𝖈 (Tree 𝖇)

Functions and Values by Type

Tree String → String

drawTree

Tree String → [String]

draw

Forest String → String

drawForest

(𝖆 → 𝖆 → 𝖆) → Tree 𝖆 → 𝖆

Foldable_Tree.foldr1, Foldable_Tree.foldl1

Tree (Tree 𝖆) → Tree 𝖆

Monad_Tree.join

Tree a → [[a]]

levels

Tree a → [a]

flatten

Tree 𝖆 → (Forest 𝖆→Forest 𝖆) → Tree 𝖆

Tree.chg$subForest

Tree 𝖆 → (𝖆→𝖆) → Tree 𝖆

Tree.chg$rootLabel

Tree 𝖆 → Forest 𝖆 → Tree 𝖆

Tree.upd$subForest

Tree 𝖆 → 𝖆 → Tree 𝖆

Tree.upd$rootLabel

Tree 𝖆 → Forest 𝖆

Tree.subForest

Tree 𝖆 → 𝖆

Tree.rootLabel

a → Forest a → Tree a

Tree.Node

𝖆 → Tree 𝖆

Applicative_Tree.pure, Monad_Tree.pure

𝖆 → Bool

Tree.has$rootLabel, Tree.has$subForest

Monoid 𝖆 ⇒ Tree 𝖆 → 𝖆

Foldable_Tree.fold

Semigroup 𝖆 ⇒ Tree 𝖆 → 𝖆

Foldable_Tree.fold1

Eq 𝖆 ⇒ Tree 𝖆 → Tree 𝖆 → Bool

Eq_Tree.!=, Eq_Tree.==

Eq 𝖆 ⇒ Tree 𝖆 → Int

Eq_Tree.hashCode

Show 𝖆 ⇒ Tree 𝖆 → String

Show_Tree.showsub, Show_Tree.display, Show_Tree.show

Show 𝖆 ⇒ Tree 𝖆 → [Char]

Show_Tree.showChars

Show 𝖆 ⇒ Forest 𝖆 → String → String

Show_Tree.showList

Show 𝖆 ⇒ Int → Tree 𝖆 → String → String

Show_Tree.showsPrec

(b → (a, [b])) → [b] → Forest a

unfoldForest

(b → (a, [b])) → b → Tree a

unfoldTree

(𝖆 → 𝖇 → 𝖆) → 𝖆 → Tree 𝖇 → 𝖆

Foldable_Tree.foldl

(𝖆 → 𝖇 → 𝖇) → 𝖇 → Tree 𝖆 → 𝖇

Foldable_Tree.foldr

(𝖆 → 𝖇) → Tree 𝖆 → Tree 𝖇

Functor_Tree.fmap

Tree (𝖆→𝖇) → Tree 𝖆 → Tree 𝖇

Applicative_Tree.<*>

Tree 𝖆 → (𝖆 → Tree 𝖇) → Tree 𝖇

Monad_Tree.>>=

Tree 𝖆 → Tree 𝖇 → Tree 𝖆

Applicative_Tree.<*

Tree 𝖆 → Tree 𝖇 → Tree 𝖇

Applicative_Tree.*>, Monad_Tree.>>

Monoid 𝖇 ⇒ (𝖆 → 𝖇) → Tree 𝖆 → 𝖇

Foldable_Tree.foldMap

Semigroup 𝖇 ⇒ (𝖆 → 𝖇) → Tree 𝖆 → 𝖇

Foldable_Tree.foldMap1

Applicative 𝖇 ⇒ Tree (𝖇 𝖆) → 𝖇 (Tree 𝖆)

Traversable_Tree.sequenceA

Monad 𝖇 ⇒ Tree (𝖇 𝖆) → 𝖇 (Tree 𝖆)

Traversable_Tree.sequence

Applicative 𝖈 ⇒ (𝖆 → 𝖈 𝖇) → Tree 𝖆 → 𝖈 (Tree 𝖇)

Traversable_Tree.traverse

Monad m ⇒ (b → m (a, [b])) → [b] → m (Forest a)

unfoldForestM

Monad m ⇒ (b → m (a, [b])) → b → m (Tree a)

unfoldTreeM

Monad 𝖈 ⇒ (𝖆 → 𝖈 𝖇) → Tree 𝖆 → 𝖈 (Tree 𝖇)

Traversable_Tree.mapM