Moduleral-0.2.2Haskell2010

Data.RAVec.Tree

Depth indexed perfect binary tree.

Contents

Construction
Conversions
Indexing
Folds
Special folds
Mapping
Zipping
Universe
QuickCheck

Synopsis

data Tree
value singleton
value toList
value reverse
value !
value tabulate
value leftmost
value rightmost
value foldMap
value foldMap1
value ifoldMap
value ifoldMap1
value foldr
value ifoldr
value foldr1Map
value ifoldr1Map
value foldl
value ifoldl
value length
value null
value sum
value product
value map
value imap
value traverse
value itraverse
value traverse1
value itraverse1
value itraverse_
value zipWith
value izipWith
value repeat
value universe
value liftArbitrary
value liftShrink

Packageral-0.2.2
Exports35
LanguageHaskell2010
LicenceGPL-2.0-or-later
SourceTree.hs

datadata 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 n1 a -> Tree n1 a -> Tree ('S n1) a

Instances23Functor, Applicative, Foldable, Traversable, Foldable1, Arbitrary1, …

Functor (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
SNatI n => Applicative (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
Foldable (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
Traversable (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
Foldable1 (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
SNatI n => Arbitrary1 (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
SNatI n => Distributive (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
Apply (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
Traversable1 (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
SNatI n => Representable (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
FoldableWithIndex (Wrd n) (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
FunctorWithIndex (Wrd n) (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
TraversableWithIndex (Wrd n) (Tree n)Defined in ral-0.2.2 · Data.RAVec.Tree
Eq a => Eq (Tree n a)Defined in ral-0.2.2 · Data.RAVec.Tree
Ord a => Ord (Tree n a)Defined in ral-0.2.2 · Data.RAVec.Tree
Show a => Show (Tree n a)Defined in ral-0.2.2 · Data.RAVec.Tree
Semigroup a => Semigroup (Tree n a)Defined in ral-0.2.2 · Data.RAVec.Tree
NFData a => NFData (Tree n a)Defined in ral-0.2.2 · Data.RAVec.Tree
(SNatI n, Arbitrary a) => Arbitrary (Tree n a)Defined in ral-0.2.2 · Data.RAVec.Tree
CoArbitrary a => CoArbitrary (Tree n a)Defined in ral-0.2.2 · Data.RAVec.Tree
(SNatI n, Function a) => Function (Tree n a)Defined in ral-0.2.2 · Data.RAVec.Tree
Hashable a => Hashable (Tree n a)Defined in ral-0.2.2 · Data.RAVec.Tree
type Rep (Tree n) = Wrd nDefined in ral-0.2.2 · Data.RAVec.Tree

Construction

valuesingleton :: a -> Tree 'Z a

Source#

Tree of zero depth, with single element.

Example1 expression

>>> singleton TrueLeaf True

Conversions

valuetoList :: Tree n a -> [a]

Source#

Convert Tree to list.

Example1 expression

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

valuereverse :: Tree n a -> Tree n a

Source#

Reverse Tree.

Example2 expressions

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

Indexing

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

Source#

Indexing.

valuetabulate :: SNatI n => (Wrd n -> a) -> Tree n a

valueleftmost :: Tree n a -> a

valuerightmost :: Tree n a -> a

Folds

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

valuefoldMap1 :: Semigroup s => (a -> s) -> Tree n a -> s

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

valueifoldMap1 :: Semigroup s => (Wrd n -> a -> s) -> Tree n a -> s

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

Source#

Example1 expression

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

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

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

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

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

Source#

Example1 expression

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

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

Special folds

valuelength :: Tree n a -> Int

Source#

Example1 expression

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

valuenull :: Tree n a -> Bool

Source#

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

Source#

Non-strict sum.

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

Source#

Non-strict product.

Mapping

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

Source#

Example1 expression

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

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

Source#

Example1 expression

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

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

valueitraverse

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

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

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

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

Source#

Zipping

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

Source#

Zip two Vecs with a function.

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

Source#

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

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

Source#

Repeat a value.

Example1 expression

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

Universe

valueuniverse :: SNatI n => Tree n (Wrd n)

Source#

Get all Vec n Bool indices in Tree n.

Example1 expression

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

QuickCheck

valueliftArbitrary :: SNatI n => Gen a -> Gen (Tree n a)

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