Moduleral-0.2.2Haskell2010

Data.RAVec.Tree.DF

Depth indexed perfect tree as data family.

35 values

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

1 declaration

valuesingleton :: a -> Tree 'Z a

Tree with exactly one element.

Example1 expression

>>> singleton TrueLeaf True

Conversions

2 declarations

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

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

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

4 declarations

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

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

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

10 declarations

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

See Foldable.

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

See Foldable1.

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

See I.FoldableWithIndex.

valueifoldMap1

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

There is no type-class for this :(

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

Right fold.

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

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

Left fold.

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

Left fold with an index.

Special folds

4 declarations

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

Yield the length of a Tree. O(n)

valuenull :: Tree n a -> Bool

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

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

Non-strict sum.

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

Non-strict product.

Mapping

7 declarations

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

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

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)

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)

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)

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

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

Zipping

3 declarations

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

Zip two Trees with a function.

valueizipWith

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

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

Repeat value

Example1 expression

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

Universe

1 declaration

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

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

2 declarations

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

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

Ensure spine

1 declaration

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

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'