Data.RAVec.Tree

Depth indexed perfect binary tree.

Documentation

data Tree (n :: Nat) a where

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

Functor (Tree n)

Defined in Data.RAVec.Tree

Methods

fmap :: (a -> b) -> Tree n a -> Tree n b

(<$) :: a -> Tree n b -> Tree n a

SNatI n => Applicative (Tree n)

Defined in Data.RAVec.Tree

Methods

pure :: a -> Tree n a

(<*>) :: Tree n (a -> b) -> Tree n a -> Tree n b

liftA2 :: (a -> b -> c) -> Tree n a -> Tree n b -> Tree n c

(*>) :: Tree n a -> Tree n b -> Tree n b

(<*) :: Tree n a -> Tree n b -> Tree n a

Foldable (Tree n)

Defined in Data.RAVec.Tree

Methods

fold :: Monoid m => Tree n m -> m

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

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

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

foldr' :: (a -> b -> b) -> b -> Tree n a -> b

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

foldl' :: (b -> a -> b) -> b -> Tree n a -> b

foldr1 :: (a -> a -> a) -> Tree n a -> a

foldl1 :: (a -> a -> a) -> Tree n a -> a

toList :: Tree n a -> [a]

null :: Tree n a -> Bool

length :: Tree n a -> Int

elem :: Eq a => a -> Tree n a -> Bool

maximum :: Ord a => Tree n a -> a

minimum :: Ord a => Tree n a -> a

sum :: Num a => Tree n a -> a

product :: Num a => Tree n a -> a

Traversable (Tree n)

Defined in Data.RAVec.Tree

Methods

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

sequenceA :: Applicative f => Tree n (f a) -> f (Tree n a)

mapM :: Monad m => (a -> m b) -> Tree n a -> m (Tree n b)

sequence :: Monad m => Tree n (m a) -> m (Tree n a)

SNatI n => Arbitrary1 (Tree n)

Defined in Data.RAVec.Tree

Methods

liftArbitrary :: Gen a -> Gen (Tree n a)

liftShrink :: (a -> [a]) -> Tree n a -> [Tree n a]

SNatI n => Distributive (Tree n)

Defined in Data.RAVec.Tree

Methods

distribute :: Functor f => f (Tree n a) -> Tree n (f a)

collect :: Functor f => (a -> Tree n b) -> f a -> Tree n (f b)

distributeM :: Monad m => m (Tree n a) -> Tree n (m a)

collectM :: Monad m => (a -> Tree n b) -> m a -> Tree n (m b)

SNatI n => Representable (Tree n)

Defined in Data.RAVec.Tree

Associated Types

type Rep (Tree n)

Methods

tabulate :: (Rep (Tree n) -> a) -> Tree n a

index :: Tree n a -> Rep (Tree n) -> a

Traversable1 (Tree n)

Defined in Data.RAVec.Tree

Methods

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

sequence1 :: Apply f => Tree n (f b) -> f (Tree n b)

Foldable1 (Tree n)

Defined in Data.RAVec.Tree

Methods

fold1 :: Semigroup m => Tree n m -> m

foldMap1 :: Semigroup m => (a -> m) -> Tree n a -> m

toNonEmpty :: Tree n a -> NonEmpty a

Apply (Tree n)

Defined in Data.RAVec.Tree

Methods

(<.>) :: Tree n (a -> b) -> Tree n a -> Tree n b

(.>) :: Tree n a -> Tree n b -> Tree n b

(<.) :: Tree n a -> Tree n b -> Tree n a

liftF2 :: (a -> b -> c) -> Tree n a -> Tree n b -> Tree n c

FunctorWithIndex (Wrd n) (Tree n)

Since: 0.2

Defined in Data.RAVec.Tree

Methods

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

FoldableWithIndex (Wrd n) (Tree n)

Since: 0.2

Defined in Data.RAVec.Tree

Methods

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

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

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

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

ifoldr' :: (Wrd n -> a -> b -> b) -> b -> Tree n a -> b

ifoldl' :: (Wrd n -> b -> a -> b) -> b -> Tree n a -> b

TraversableWithIndex (Wrd n) (Tree n)

Since: 0.2

Defined in Data.RAVec.Tree

Methods

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

Eq a => Eq (Tree n a)

Defined in Data.RAVec.Tree

Methods

(==) :: Tree n a -> Tree n a -> Bool

(/=) :: Tree n a -> Tree n a -> Bool

Ord a => Ord (Tree n a)

Defined in Data.RAVec.Tree

Methods

compare :: Tree n a -> Tree n a -> Ordering

(<) :: Tree n a -> Tree n a -> Bool

(<=) :: Tree n a -> Tree n a -> Bool

(>) :: Tree n a -> Tree n a -> Bool

(>=) :: Tree n a -> Tree n a -> Bool

max :: Tree n a -> Tree n a -> Tree n a

min :: Tree n a -> Tree n a -> Tree n a

Show a => Show (Tree n a)

Defined in Data.RAVec.Tree

Methods

showsPrec :: Int -> Tree n a -> ShowS

show :: Tree n a -> String

showList :: [Tree n a] -> ShowS

Semigroup a => Semigroup (Tree n a)

Defined in Data.RAVec.Tree

Methods

(<>) :: Tree n a -> Tree n a -> Tree n a

sconcat :: NonEmpty (Tree n a) -> Tree n a

stimes :: Integral b => b -> Tree n a -> Tree n a

(SNatI n, Function a) => Function (Tree n a)

Defined in Data.RAVec.Tree

Methods

function :: (Tree n a -> b) -> Tree n a :-> b

(SNatI n, Arbitrary a) => Arbitrary (Tree n a)

Defined in Data.RAVec.Tree

Methods

arbitrary :: Gen (Tree n a)

shrink :: Tree n a -> [Tree n a]

CoArbitrary a => CoArbitrary (Tree n a)

Defined in Data.RAVec.Tree

Methods

coarbitrary :: Tree n a -> Gen b -> Gen b

NFData a => NFData (Tree n a)

Defined in Data.RAVec.Tree

Methods

rnf :: Tree n a -> ()

Hashable a => Hashable (Tree n a)

Defined in Data.RAVec.Tree

Methods

hashWithSalt :: Int -> Tree n a -> Int

hash :: Tree n a -> Int

type Rep (Tree n)

Defined in Data.RAVec.Tree

type Rep (Tree n) = Wrd n

Construction

singleton :: a -> Tree 'Z a

Tree of zero depth, with single element.

>>> singleton True
Leaf True

Conversions

toList :: Tree n a -> [a]

Convert Tree to list.

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

reverse :: Tree n a -> Tree n a

Reverse Tree.

>>> let t = Node (Node (Leaf 'a') (Leaf 'b')) (Node (Leaf 'c') (Leaf 'd'))
>>> reverse t
Node (Node (Leaf 'd') (Leaf 'c')) (Node (Leaf 'b') (Leaf 'a'))

Since: 0.1.1

Indexing

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

Indexing.

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

leftmost :: Tree n a -> a

rightmost :: Tree n a -> a

Folds

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

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

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

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

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

Special folds

length :: Tree n a -> Int

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

null :: Tree n a -> Bool

Since: 0.1.1

sum :: Num a => Tree n a -> a

Non-strict sum.

Since: 0.1.1

product :: Num a => Tree n a -> a

Non-strict product.

Since: 0.1.1

Mapping

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

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

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

>>> 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)

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)

itraverse_ :: forall n f a b. Applicative f => (Wrd n -> a -> f b) -> Tree n a -> f ()

Since: 0.1.1

Zipping

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

Zip two Vecs with a function.

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

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

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

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)

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)

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