Safe Haskell	None
Language	Haskell2010

Data.RAVec.Tree

Contents

Construction
Conversions
Indexing
Folds
Mapping
Zipping
Universe
QuickCheck

Description

Depth indexed perfect binary tree.

Synopsis

data Tree (n :: Nat ) a where
- Leaf :: a -> Tree ' Z a
- Node :: Tree n a -> Tree n a -> Tree (' S n) a
singleton :: a -> Tree ' Z a
toList :: Tree n a -> [a]
(!) :: Tree n a -> Wrd n -> a
tabulate :: forall n a. SNatI n => ( Wrd n -> a) -> Tree n a
leftmost :: Tree n a -> a
rightmost :: Tree n a -> a
foldMap :: Monoid m => (a -> m) -> Tree n a -> m
foldMap1 :: Semigroup s => (a -> s) -> Tree n a -> s
ifoldMap :: Monoid m => ( Wrd n -> a -> m) -> Tree n a -> m
ifoldMap1 :: Semigroup s => ( Wrd n -> a -> s) -> Tree n a -> s
foldr :: (a -> b -> b) -> b -> Tree n a -> b
ifoldr :: ( Wrd n -> a -> b -> b) -> b -> Tree n a -> b
foldr1Map :: (a -> b -> b) -> (a -> b) -> Tree n a -> b
ifoldr1Map :: ( Wrd n -> a -> b -> b) -> ( Wrd n -> a -> b) -> Tree n a -> b
foldl :: (b -> a -> b) -> b -> Tree n a -> b
ifoldl :: ( Wrd n -> b -> a -> b) -> b -> Tree n a -> b
length :: Tree n a -> Int
map :: (a -> b) -> Tree n a -> Tree n b
imap :: ( Wrd n -> a -> b) -> Tree n a -> Tree n b
traverse :: Applicative f => (a -> f b) -> Tree n a -> f ( Tree n b)
itraverse :: Applicative f => ( Wrd n -> a -> f b) -> Tree n a -> f ( Tree n b)
traverse1 :: Apply f => (a -> f b) -> Tree n a -> f ( Tree n b)
itraverse1 :: Apply f => ( Wrd n -> a -> f b) -> Tree n a -> f ( Tree n b)
zipWith :: (a -> b -> c) -> Tree n a -> Tree n b -> Tree n c
izipWith :: ( Wrd n -> a -> b -> c) -> Tree n a -> Tree n b -> Tree n c
repeat :: SNatI n => a -> Tree n a
universe :: SNatI n => Tree n ( Wrd n)
liftArbitrary :: forall n a. SNatI n => Gen a -> Gen ( Tree n a)
liftShrink :: forall n a. (a -> [a]) -> Tree n a -> [ Tree n a]

Documentation

data Tree (n :: Nat ) a where Source #

Perfectly balanced binary tree of depth n , with 2 ^ n elements.

Constructors

Leaf :: a -> Tree ' Z a
Node :: Tree n a -> Tree n a -> Tree (' S n) a

Instances

Instances details

Functor ( Tree n) Source #
Instance details Defined in Data.RAVec.Tree Methods fmap :: (a -> b) -> Tree n a -> Tree n b Source # (<$) :: a -> Tree n b -> Tree n a Source #
SNatI n => Applicative ( Tree n) Source #
Instance details Defined in Data.RAVec.Tree Methods pure :: a -> Tree n a Source # (<>) :: Tree n (a -> b) -> Tree n a -> Tree n b Source # liftA2 :: (a -> b -> c) -> Tree n a -> Tree n b -> Tree n c Source # (>) :: Tree n a -> Tree n b -> Tree n b Source # (<*) :: Tree n a -> Tree n b -> Tree n a Source #
Foldable ( Tree n) Source #
Instance details Defined in Data.RAVec.Tree Methods fold :: Monoid m => Tree n m -> m Source # foldMap :: Monoid m => (a -> m) -> Tree n a -> m Source # foldMap' :: Monoid m => (a -> m) -> Tree n a -> m Source # foldr :: (a -> b -> b) -> b -> Tree n a -> b Source # foldr' :: (a -> b -> b) -> b -> Tree n a -> b Source # foldl :: (b -> a -> b) -> b -> Tree n a -> b Source # foldl' :: (b -> a -> b) -> b -> Tree n a -> b Source # foldr1 :: (a -> a -> a) -> Tree n a -> a Source # foldl1 :: (a -> a -> a) -> Tree n a -> a Source # toList :: Tree n a -> [a] Source # null :: Tree n a -> Bool Source # length :: Tree n a -> Int Source # elem :: Eq a => a -> Tree n a -> Bool Source # maximum :: Ord a => Tree n a -> a Source # minimum :: Ord a => Tree n a -> a Source # sum :: Num a => Tree n a -> a Source # product :: Num a => Tree n a -> a Source #
Traversable ( Tree n) Source #
Instance details Defined in Data.RAVec.Tree Methods traverse :: Applicative f => (a -> f b) -> Tree n a -> f ( Tree n b) Source # sequenceA :: Applicative f => Tree n (f a) -> f ( Tree n a) Source # mapM :: Monad m => (a -> m b) -> Tree n a -> m ( Tree n b) Source # sequence :: Monad m => Tree n (m a) -> m ( Tree n a) Source #
SNatI n => Arbitrary1 ( Tree n) Source #
Instance details Defined in Data.RAVec.Tree Methods liftArbitrary :: Gen a -> Gen ( Tree n a) Source # liftShrink :: (a -> [a]) -> Tree n a -> [ Tree n a] Source #
SNatI n => Distributive ( Tree n) Source #
Instance details Defined in Data.RAVec.Tree Methods distribute :: Functor f => f ( Tree n a) -> Tree n (f a) Source # collect :: Functor f => (a -> Tree n b) -> f a -> Tree n (f b) Source # distributeM :: Monad m => m ( Tree n a) -> Tree n (m a) Source # collectM :: Monad m => (a -> Tree n b) -> m a -> Tree n (m b) Source #
SNatI n => Representable ( Tree n) Source #
Instance details Defined in Data.RAVec.Tree Associated Types type Rep ( Tree n) Source # Methods tabulate :: ( Rep ( Tree n) -> a) -> Tree n a Source # index :: Tree n a -> Rep ( Tree n) -> a Source #
Traversable1 ( Tree n) Source #
Instance details Defined in Data.RAVec.Tree Methods traverse1 :: Apply f => (a -> f b) -> Tree n a -> f ( Tree n b) Source # sequence1 :: Apply f => Tree n (f b) -> f ( Tree n b) Source #
Apply ( Tree n) Source #
Instance details Defined in Data.RAVec.Tree Methods (<.>) :: Tree n (a -> b) -> Tree n a -> Tree n b Source # (.>) :: Tree n a -> Tree n b -> Tree n b Source # (<.) :: Tree n a -> Tree n b -> Tree n a Source # liftF2 :: (a -> b -> c) -> Tree n a -> Tree n b -> Tree n c Source #
Foldable1 ( Tree n) Source #
Instance details Defined in Data.RAVec.Tree Methods fold1 :: Semigroup m => Tree n m -> m Source # foldMap1 :: Semigroup m => (a -> m) -> Tree n a -> m Source # toNonEmpty :: Tree n a -> NonEmpty a Source #
Eq a => Eq ( Tree n a) Source #
Instance details Defined in Data.RAVec.Tree Methods (==) :: Tree n a -> Tree n a -> Bool Source # (/=) :: Tree n a -> Tree n a -> Bool Source #
Ord a => Ord ( Tree n a) Source #
Instance details Defined in Data.RAVec.Tree Methods compare :: Tree n a -> Tree n a -> Ordering Source # (<) :: Tree n a -> Tree n a -> Bool Source # (<=) :: Tree n a -> Tree n a -> Bool Source # (>) :: Tree n a -> Tree n a -> Bool Source # (>=) :: Tree n a -> Tree n a -> Bool Source # max :: Tree n a -> Tree n a -> Tree n a Source # min :: Tree n a -> Tree n a -> Tree n a Source #
Show a => Show ( Tree n a) Source #
Instance details Defined in Data.RAVec.Tree Methods showsPrec :: Int -> Tree n a -> ShowS Source # show :: Tree n a -> String Source # showList :: [ Tree n a] -> ShowS Source #
Semigroup a => Semigroup ( Tree n a) Source #
Instance details Defined in Data.RAVec.Tree Methods (<>) :: Tree n a -> Tree n a -> Tree n a Source # sconcat :: NonEmpty ( Tree n a) -> Tree n a Source # stimes :: Integral b => b -> Tree n a -> Tree n a Source #
( SNatI n, Function a) => Function ( Tree n a) Source #
Instance details Defined in Data.RAVec.Tree Methods function :: ( Tree n a -> b) -> Tree n a :-> b Source #
( SNatI n, Arbitrary a) => Arbitrary ( Tree n a) Source #
Instance details Defined in Data.RAVec.Tree Methods arbitrary :: Gen ( Tree n a) Source # shrink :: Tree n a -> [ Tree n a] Source #
CoArbitrary a => CoArbitrary ( Tree n a) Source #
Instance details Defined in Data.RAVec.Tree Methods coarbitrary :: Tree n a -> Gen b -> Gen b Source #
NFData a => NFData ( Tree n a) Source #
Instance details Defined in Data.RAVec.Tree Methods rnf :: Tree n a -> () Source #
Hashable a => Hashable ( Tree n a) Source #
Instance details Defined in Data.RAVec.Tree Methods hashWithSalt :: Int -> Tree n a -> Int Source # hash :: Tree n a -> Int Source #
type Rep ( Tree n) Source #
Instance details Defined in Data.RAVec.Tree type Rep ( Tree n) = Wrd n

Construction

singleton :: a -> Tree ' Z a Source #

Tree of zero depth, with single element.

>>> singleton True
Leaf True

Conversions

toList :: Tree n a -> [a] Source #

Convert Tree to list.

>>> toList $ Node (Node (Leaf 'a') (Leaf 'b')) (Node (Leaf 'c') (Leaf 'd'))
"abcd"

Indexing

(!) :: Tree n a -> Wrd n -> a Source #

Indexing.

tabulate :: forall n a. SNatI n => ( Wrd n -> a) -> Tree n a Source #

leftmost :: Tree n a -> a Source #

rightmost :: Tree n a -> a Source #

Folds

foldMap :: Monoid m => (a -> m) -> Tree n a -> m Source #

foldMap1 :: Semigroup s => (a -> s) -> Tree n a -> s Source #

ifoldMap :: Monoid m => ( Wrd n -> a -> m) -> Tree n a -> m Source #

ifoldMap1 :: Semigroup s => ( Wrd n -> a -> s) -> Tree n a -> s Source #

foldr :: (a -> b -> b) -> b -> Tree n a -> b Source #

>>> foldr (:) [] $ Node (Leaf True) (Leaf False)
[True,False]

ifoldr :: ( Wrd n -> a -> b -> b) -> b -> Tree n a -> b Source #

foldr1Map :: (a -> b -> b) -> (a -> b) -> Tree n a -> b Source #

ifoldr1Map :: ( Wrd n -> a -> b -> b) -> ( Wrd n -> a -> b) -> Tree n a -> b Source #

foldl :: (b -> a -> b) -> b -> Tree n a -> b Source #

>>> foldl (flip (:)) [] $ Node (Leaf True) (Leaf False)
[False,True]

ifoldl :: ( Wrd n -> b -> a -> b) -> b -> Tree n a -> b Source #

length :: Tree n a -> Int Source #

>>> length (universe :: Tree N.Nat3 (Wrd N.Nat3))
8

Mapping

map :: (a -> b) -> Tree n a -> Tree n b Source #

>>> map not $ Node (Leaf True) (Leaf False)
Node (Leaf False) (Leaf True)

imap :: ( Wrd n -> a -> b) -> Tree n a -> Tree n b Source #

>>> imap (,) $ Node (Leaf True) (Leaf False)
Node (Leaf (0b0,True)) (Leaf (0b1,False))

traverse :: Applicative f => (a -> f b) -> Tree n a -> f ( Tree n b) Source #

itraverse :: Applicative f => ( Wrd n -> a -> f b) -> Tree n a -> f ( Tree n b) Source #

traverse1 :: Apply f => (a -> f b) -> Tree n a -> f ( Tree n b) Source #

itraverse1 :: Apply f => ( Wrd n -> a -> f b) -> Tree n a -> f ( Tree n b) Source #

Zipping

zipWith :: (a -> b -> c) -> Tree n a -> Tree n b -> Tree n c Source #

Zip two Vec s with a function.

izipWith :: ( Wrd n -> a -> b -> c) -> Tree n a -> Tree n b -> Tree n c Source #

Zip two Tree s. with a function that also takes the elements' indices.

repeat :: SNatI n => a -> Tree n a Source #

Repeat a value.

>>> repeat 'x' :: Tree N.Nat2 Char
Node (Node (Leaf 'x') (Leaf 'x')) (Node (Leaf 'x') (Leaf 'x'))

Universe

universe :: SNatI n => Tree n ( Wrd n) Source #

Get all Vec n Bool indices in Tree n .

>>> universe :: Tree N.Nat2 (Wrd N.Nat2)
Node (Node (Leaf 0b00) (Leaf 0b01)) (Node (Leaf 0b10) (Leaf 0b11))

QuickCheck

liftArbitrary :: forall n a. SNatI n => Gen a -> Gen ( Tree n a) Source #

liftShrink :: forall n a. (a -> [a]) -> Tree n a -> [ Tree n a] Source #