Copyright	(c) Alexandre Moine 2019
Maintainer	alexandre@moine.me
Stability	experimental
Safe Haskell	None
Language	Haskell2010

Tungsten.Structure.Tree

Contents

Binary trees as fixed-points
Operations on trees
Conversions

Description

This module defines a type isomorphic to binary trees, in terms of Fix from Tungsten.Fix.

A good consumer is a function that can be fused with a good producer. A good producer is a function that can be fused with a good consumer.

Synopsis

data TreeF a b
- = EmptyF
- | LeafF a
- | NodeF b b
newtype Tree a = Tree (Fix (TreeF a))
empty :: Tree a
leaf :: a -> Tree a
node :: Tree a -> Tree a -> Tree a
hasLeaf :: Eq a => a -> Tree a -> Bool
treeFromList :: [Tree a] -> Tree a
leftTreeN :: Int -> Tree Int

Binary trees as fixed-points

data TreeF a b Source #

The "factored-out" recursive type for binary trees.

Constructors

EmptyF
LeafF a
NodeF b b

Instances

Eq2 TreeF Source #
Instance details Defined in Tungsten.Structure.Tree Methods liftEq2 :: (a -> b -> Bool) -> (c -> d -> Bool) -> TreeF a c -> TreeF b d -> Bool #
Show2 TreeF Source #
Instance details Defined in Tungsten.Structure.Tree Methods liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> TreeF a b -> ShowS # liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [TreeF a b] -> ShowS #
Functor (TreeF a) Source #
Instance details Defined in Tungsten.Structure.Tree Methods fmap :: (a0 -> b) -> TreeF a a0 -> TreeF a b # (<$) :: a0 -> TreeF a b -> TreeF a a0 #
Eq a => Eq1 (TreeF a) Source #
Instance details Defined in Tungsten.Structure.Tree Methods liftEq :: (a0 -> b -> Bool) -> TreeF a a0 -> TreeF a b -> Bool #
Show a => Show1 (TreeF a) Source #
Instance details Defined in Tungsten.Structure.Tree Methods liftShowsPrec :: (Int -> a0 -> ShowS) -> ([a0] -> ShowS) -> Int -> TreeF a a0 -> ShowS # liftShowList :: (Int -> a0 -> ShowS) -> ([a0] -> ShowS) -> [TreeF a a0] -> ShowS #
(Eq a, Eq b) => Eq (TreeF a b) Source #
Instance details Defined in Tungsten.Structure.Tree Methods (==) :: TreeF a b -> TreeF a b -> Bool # (/=) :: TreeF a b -> TreeF a b -> Bool #
(Ord a, Ord b) => Ord (TreeF a b) Source #
Instance details Defined in Tungsten.Structure.Tree Methods compare :: TreeF a b -> TreeF a b -> Ordering # (<) :: TreeF a b -> TreeF a b -> Bool # (<=) :: TreeF a b -> TreeF a b -> Bool # (>) :: TreeF a b -> TreeF a b -> Bool # (>=) :: TreeF a b -> TreeF a b -> Bool # max :: TreeF a b -> TreeF a b -> TreeF a b # min :: TreeF a b -> TreeF a b -> TreeF a b #
(Read a, Read b) => Read (TreeF a b) Source #
Instance details Defined in Tungsten.Structure.Tree Methods readsPrec :: Int -> ReadS (TreeF a b) # readList :: ReadS [TreeF a b] # readPrec :: ReadPrec (TreeF a b) # readListPrec :: ReadPrec [TreeF a b] #
(Show a, Show b) => Show (TreeF a b) Source #
Instance details Defined in Tungsten.Structure.Tree Methods showsPrec :: Int -> TreeF a b -> ShowS # show :: TreeF a b -> String # showList :: [TreeF a b] -> ShowS #

newtype Tree a Source #

Binary trees expressed as a fixed-point.

Constructors

Tree (Fix (TreeF a))

Instances

Monad Tree Source #	`>>=` is a good consumer and good producer.
Instance details Defined in Tungsten.Structure.Tree Methods (>>=) :: Tree a -> (a -> Tree b) -> Tree b # (>>) :: Tree a -> Tree b -> Tree b # return :: a -> Tree a # fail :: String -> Tree a #
Functor Tree Source #	`fmap` is a good consumer and good producer.
Instance details Defined in Tungsten.Structure.Tree Methods fmap :: (a -> b) -> Tree a -> Tree b # (<$) :: a -> Tree b -> Tree a #
Applicative Tree Source #
Instance details Defined in Tungsten.Structure.Tree Methods pure :: a -> Tree a # (<>) :: Tree (a -> b) -> Tree a -> Tree b # liftA2 :: (a -> b -> c) -> Tree a -> Tree b -> Tree c # (>) :: Tree a -> Tree b -> Tree b # (<*) :: Tree a -> Tree b -> Tree a #
Eq a => Eq (Tree a) Source #
Instance details Defined in Tungsten.Structure.Tree Methods (==) :: Tree a -> Tree a -> Bool # (/=) :: Tree a -> Tree a -> Bool #
Show a => Show (Tree a) Source #
Instance details Defined in Tungsten.Structure.Tree Methods showsPrec :: Int -> Tree a -> ShowS # show :: Tree a -> String # showList :: [Tree a] -> ShowS #

empty :: Tree a Source #

The empty tree.

leaf :: a -> Tree a Source #

A leaf.

node :: Tree a -> Tree a -> Tree a Source #

A node.

Operations on trees

hasLeaf :: Eq a => a -> Tree a -> Bool Source #

hasLeaf s t tests if the leaf s is present in the tree t. Good consumer.

Conversions

treeFromList :: [Tree a] -> Tree a Source #

Construct a binary tree from a list. Good consumer (of Prelude lists) and good producer (of trees).

leftTreeN :: Int -> Tree Int Source #

leftTree n construct a tree with n leaves from 1 to n. Good producer.