Safe Haskell	Safe
Language	Haskell2010

Data.RAVec.Tree.DF

Contents

Construction
Conversions
Indexing
Folds
Special folds
Mapping
Zipping
Universe
QuickCheck
Ensure spine

Description

Depth indexed perfect tree as data family.

Synopsis

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

Documentation

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

Instances

Instances details

SNatI n => Arbitrary1 (Tree n) Source #
Instance details Defined in Data.RAVec.Tree.DF Methods liftArbitrary :: Gen a -> Gen (Tree n a) # liftShrink :: (a -> [a]) -> Tree n a -> [Tree n a] #
SNatI n => Representable (Tree n) Source #
Instance details Defined in Data.RAVec.Tree.DF Associated Types type Rep (Tree n) # Methods tabulate :: (Rep (Tree n) -> a) -> Tree n a # index :: Tree n a -> Rep (Tree n) -> a #
SNatI n => Foldable (Tree n) Source #
Instance details Defined in Data.RAVec.Tree.DF 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 #
SNatI n => Foldable1 (Tree n) Source #
Instance details Defined in Data.RAVec.Tree.DF Methods fold1 :: Semigroup m => Tree n m -> m # foldMap1 :: Semigroup m => (a -> m) -> Tree n a -> m # foldMap1' :: Semigroup m => (a -> m) -> Tree n a -> m # toNonEmpty :: Tree n a -> NonEmpty a # maximum :: Ord a => Tree n a -> a # minimum :: Ord a => Tree n a -> a # head :: Tree n a -> a # last :: Tree n a -> a # foldrMap1 :: (a -> b) -> (a -> b -> b) -> Tree n a -> b # foldlMap1' :: (a -> b) -> (b -> a -> b) -> Tree n a -> b # foldlMap1 :: (a -> b) -> (b -> a -> b) -> Tree n a -> b # foldrMap1' :: (a -> b) -> (a -> b -> b) -> Tree n a -> b #
SNatI n => Traversable (Tree n) Source #
Instance details Defined in Data.RAVec.Tree.DF 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 => Applicative (Tree n) Source #
Instance details Defined in Data.RAVec.Tree.DF 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 #
SNatI n => Functor (Tree n) Source #
Instance details Defined in Data.RAVec.Tree.DF Methods fmap :: (a -> b) -> Tree n a -> Tree n b # (<$) :: a -> Tree n b -> Tree n a #
SNatI n => Distributive (Tree n) Source #
Instance details Defined in Data.RAVec.Tree.DF 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 => Apply (Tree n) Source #
Instance details Defined in Data.RAVec.Tree.DF 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 #
SNatI n => Traversable1 (Tree n) Source #
Instance details Defined in Data.RAVec.Tree.DF 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) #
SNatI n => FoldableWithIndex (Wrd n) (Tree n) Source #	Since: 0.2
Instance details Defined in Data.RAVec.Tree.DF 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 #
SNatI n => FunctorWithIndex (Wrd n) (Tree n) Source #	Since: 0.2
Instance details Defined in Data.RAVec.Tree.DF Methods imap :: (Wrd n -> a -> b) -> Tree n a -> Tree n b #
SNatI n => TraversableWithIndex (Wrd n) (Tree n) Source #	Since: 0.2
Instance details Defined in Data.RAVec.Tree.DF Methods itraverse :: Applicative f => (Wrd n -> a -> f b) -> Tree n a -> f (Tree n b) #
(SNatI n, Arbitrary a) => Arbitrary (Tree n a) Source #
Instance details Defined in Data.RAVec.Tree.DF Methods arbitrary :: Gen (Tree n a) # shrink :: Tree n a -> [Tree n a] #
(SNatI n, CoArbitrary a) => CoArbitrary (Tree n a) Source #
Instance details Defined in Data.RAVec.Tree.DF Methods coarbitrary :: Tree n a -> Gen b -> Gen b #
(SNatI n, Function a) => Function (Tree n a) Source #
Instance details Defined in Data.RAVec.Tree.DF Methods function :: (Tree n a -> b) -> Tree n a :-> b #
(Monoid a, SNatI n) => Monoid (Tree n a) Source #
Instance details Defined in Data.RAVec.Tree.DF Methods mempty :: Tree n a # mappend :: Tree n a -> Tree n a -> Tree n a # mconcat :: [Tree n a] -> Tree n a #
(Semigroup a, SNatI n) => Semigroup (Tree n a) Source #
Instance details Defined in Data.RAVec.Tree.DF 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 #
(Show a, SNatI n) => Show (Tree n a) Source #
Instance details Defined in Data.RAVec.Tree.DF Methods showsPrec :: Int -> Tree n a -> ShowS # show :: Tree n a -> String # showList :: [Tree n a] -> ShowS #
(NFData a, SNatI n) => NFData (Tree n a) Source #
Instance details Defined in Data.RAVec.Tree.DF Methods rnf :: Tree n a -> () #
(Eq a, SNatI n) => Eq (Tree n a) Source #
Instance details Defined in Data.RAVec.Tree.DF Methods (==) :: Tree n a -> Tree n a -> Bool # (/=) :: Tree n a -> Tree n a -> Bool #
(Ord a, SNatI n) => Ord (Tree n a) Source #
Instance details Defined in Data.RAVec.Tree.DF 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 #
(Hashable a, SNatI n) => Hashable (Tree n a) Source #
Instance details Defined in Data.RAVec.Tree.DF Methods hashWithSalt :: Int -> Tree n a -> Int # hash :: Tree n a -> Int #
newtype Tree 'Z a Source #
Instance details Defined in Data.RAVec.Tree.DF newtype Tree 'Z a = Leaf a
type Rep (Tree n) Source #
Instance details Defined in Data.RAVec.Tree.DF type Rep (Tree n) = Wrd n
data Tree ('S n) a Source #
Instance details Defined in Data.RAVec.Tree.DF data Tree ('S n) a = Node (Tree n a) (Tree n a)

Construction

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

Tree with exactly one element.

>>> singleton True
Leaf True

Conversions

toList :: forall n a. SNatI n => Tree n a -> [a] Source #

Convert Tree to list.

>>> toList $ Node (Node (Leaf 'f') (Leaf 'o')) (Node (Leaf 'o') (Leaf 'd'))
"food"

reverse :: forall n a. SNatI n => Tree n a -> Tree n a Source #

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

Indexing

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

Indexing.

>>> let t = Node (Node (Leaf 'a') (Leaf 'b')) (Node (Leaf 'c') (Leaf 'd'))
>>> t ! W1 (W0 WE)
'c'

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

Tabulating, inverse of !.

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

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

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

Folds

foldMap :: forall a n m. (Monoid m, SNatI n) => (a -> m) -> Tree n a -> m Source #

See Foldable.

foldMap1 :: forall s a n. (Semigroup s, SNatI n) => (a -> s) -> Tree n a -> s Source #

See Foldable1.

ifoldMap :: forall a n m. (Monoid m, SNatI n) => (Wrd n -> a -> m) -> Tree n a -> m Source #

See FoldableWithIndex.

ifoldMap1 :: forall a n s. (Semigroup s, SNatI n) => (Wrd ('S n) -> a -> s) -> Tree ('S n) a -> s Source #

There is no type-class for this :(

foldr :: forall a b n. SNatI n => (a -> b -> b) -> b -> Tree n a -> b Source #

Right fold.

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

Right fold with an index.

foldr1Map :: forall a b n. SNatI n => (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 :: forall a b n. SNatI n => (b -> a -> b) -> b -> Tree n a -> b Source #

Left fold.

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

Left fold with an index.

Special folds

length :: forall n a. SNatI n => Tree n a -> Int Source #

Yield the length of a Tree. O(n)

null :: Tree n a -> Bool Source #

Test whether a Tree is empty. It never is. O(1)

sum :: (Num a, SNatI n) => Tree n a -> a Source #

Non-strict sum.

product :: (Num a, SNatI n) => Tree n a -> a Source #

Non-strict product.

Mapping

map :: forall a b n. SNatI n => (a -> b) -> Tree n a -> Tree n b Source #

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

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

>>> let t = Node (Node (Leaf 'a') (Leaf 'b')) (Node (Leaf 'c') (Leaf 'd'))
>>> imap (,) t
Node (Node (Leaf (0b00,'a')) (Leaf (0b01,'b'))) (Node (Leaf (0b10,'c')) (Leaf (0b11,'d')))

traverse :: forall n f a b. (Applicative f, SNatI n) => (a -> f b) -> Tree n a -> f (Tree n b) Source #

Apply an action to every element of a Tree, yielding a Tree of results.

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

Apply an action to every element of a Tree and its index, yielding a Tree of results.

traverse1 :: forall n f a b. (Apply f, SNatI n) => (a -> f b) -> Tree n a -> f (Tree n b) Source #

Apply an action to non-empty Tree, yielding a Tree of results.

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

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

Apply an action to every element of a Tree and its index, ignoring the results.

Zipping

zipWith :: forall a b c n. SNatI n => (a -> b -> c) -> Tree n a -> Tree n b -> Tree n c Source #

Zip two Trees with a function.

izipWith :: SNatI n => (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.

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

Repeat 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 Wrd n in a 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. SNatI n => (a -> [a]) -> Tree n a -> [Tree n a] Source #

Ensure spine

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

Ensure spine.

If we have an undefined Tree,

>>> let v = error "err" :: Tree N.Nat2 Char

And insert data into it later:

>>> let setHead :: a -> Tree N.Nat2 a -> Tree N.Nat2 a; setHead x (Node (Node _ u) v) = Node (Node (Leaf x) u) v

Then without a spine, it will fail:

>>> leftmost $ setHead 'x' v
*** Exception: err
...

But with the spine, it won't:

>>> leftmost $ setHead 'x' $ ensureSpine v
'x'