ral-0.2.2: Random access lists
Safe HaskellSafe
LanguageHaskell2010

Data.RAVec.Tree.DF

Description

Depth indexed perfect tree as data family.

Synopsis

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 #

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

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

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'