Moduleral-0.2.2Haskell2010

Data.RAVec.Tree.DF

Depth indexed perfect tree as data family.

Contents

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

Synopsis

data family Tree
constructor Leaf
constructor Node
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
value ensureSpine

Packageral-0.2.2
Exports38
LanguageHaskell2010
LicenceGPL-2.0-or-later
SourceDF.hs

data familydata family Tree (n :: Nat) a

Instances26Functor, Applicative, Foldable, Traversable, Foldable1, Arbitrary1, …

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

constructorLeaf a

constructorNode (Tree n a) (Tree n a)

Construction

valuesingleton :: a -> Tree 'Z a

Source#

Tree with exactly one element.

Example1 expression

>>> singleton TrueLeaf True

Conversions

valuetoList :: SNatI n => Tree n a -> [a]

Source#

Convert Tree to list.

Example1 expression

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

valuereverse :: SNatI n => 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(!) :: SNatI n => Tree n a -> Wrd n -> a

Source#

Indexing.

Example2 expressions

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

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

Source#

Tabulating, inverse of !.

Example1 expression

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

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

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

Folds

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

Source#

See Foldable.

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

Source#

See Foldable1.

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

Source#

See I.FoldableWithIndex.

valueifoldMap1

:: (Semigroup s, SNatI n)
=> Wrd ('S n) -> a -> s
-> Tree ('S n) a
-> s

Source#

There is no type-class for this :(

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

Source#

Right fold.

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

Source#

Right fold with an index.

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

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

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

Source#

Left fold.

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

Source#

Left fold with an index.

Special folds

valuelength :: SNatI n => Tree n a -> Int

Source#

Yield the length of a Tree. O(n)

valuenull :: Tree n a -> Bool

Source#

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

valuesum :: (Num a, SNatI n) => Tree n a -> a

Source#

Non-strict sum.

valueproduct :: (Num a, SNatI n) => Tree n a -> a

Source#

Non-strict product.

Mapping

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

Source#

Example1 expression

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

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

Source#

Example2 expressions

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

valuetraverse

:: (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.

valueitraverse

:: (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.

valuetraverse1 :: (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.

valueitraverse1

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

valueitraverse_

:: (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

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

Source#

Zip two Trees with a function.

valueizipWith

:: 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.

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

Source#

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

Ensure spine

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

Source#

Ensure spine.

If we have an undefined Tree,

Example1 expression

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

And insert data into it later:

Example1 expression

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

Example1 expression

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

But with the spine, it won't:

Example1 expression

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