Safe Haskell	None
Language	Haskell2010

Data.RAVec

Contents

Random access list
Construction
Conversion
Indexing
Folds
Mapping
Zipping
Universe
QuickCheck

Description

Length-indexed random access list.

See http://www.staff.science.uu.nl/~swier004/publications/2019-jfp-submission.pdf

Synopsis

data RAVec (b :: Bin ) a where
- Empty :: RAVec ' BZ a
- NonEmpty :: NERAVec b a -> RAVec (' BP b) a
empty :: RAVec Bin0 a
singleton :: a -> RAVec Bin1 a
cons :: a -> RAVec b a -> RAVec ( Succ b) a
withCons :: SBinI b => a -> RAVec b a -> ( SBinPI ( Succ' b) => RAVec ( Succ b) a -> r) -> r
head :: RAVec (' BP b) a -> a
last :: RAVec (' BP b) a -> a
toList :: RAVec b a -> [a]
toNonEmpty :: RAVec (' BP b) a -> NonEmpty a
fromList :: forall b a. SBinI b => [a] -> Maybe ( RAVec b a)
reifyNonEmpty :: NonEmpty a -> ( forall b. SBinPI b => RAVec (' BP b) a -> r) -> r
(!) :: RAVec b a -> Pos b -> a
tabulate :: forall b a. SBinI b => ( Pos b -> a) -> RAVec b a
foldMap :: Monoid m => (a -> m) -> RAVec n a -> m
foldMap1 :: Semigroup m => (a -> m) -> RAVec (' BP b) a -> m
ifoldMap :: Monoid m => ( Pos b -> a -> m) -> RAVec b a -> m
ifoldMap1 :: Semigroup m => ( Pos (' BP b) -> a -> m) -> RAVec (' BP b) a -> m
foldr :: (a -> b -> b) -> b -> RAVec n a -> b
ifoldr :: ( Pos n -> a -> b -> b) -> b -> RAVec n a -> b
map :: (a -> b) -> RAVec n a -> RAVec n b
imap :: ( Pos n -> a -> b) -> RAVec n a -> RAVec n b
traverse :: Applicative f => (a -> f b) -> RAVec n a -> f ( RAVec n b)
itraverse :: Applicative f => ( Pos n -> a -> f b) -> RAVec n a -> f ( RAVec n b)
traverse1 :: Apply f => (a -> f b) -> RAVec (' BP n) a -> f ( RAVec (' BP n) b)
itraverse1 :: Apply f => ( Pos (' BP n) -> a -> f b) -> RAVec (' BP n) a -> f ( RAVec (' BP n) b)
zipWith :: (a -> b -> c) -> RAVec n a -> RAVec n b -> RAVec n c
izipWith :: ( Pos n -> a -> b -> c) -> RAVec n a -> RAVec n b -> RAVec n c
universe :: forall b. SBinI b => RAVec b ( Pos b)
repeat :: forall b a. SBinI b => a -> RAVec b a
liftArbitrary :: SBinI b => Gen a -> Gen ( RAVec b a)
liftShrink :: (a -> [a]) -> RAVec b a -> [ RAVec b a]

Random access list

data RAVec (b :: Bin ) a where Source #

Length indexed random access lists.

Constructors

Empty :: RAVec ' BZ a
NonEmpty :: NERAVec b a -> RAVec (' BP b) a

Instances

Instances details

Functor ( RAVec b) Source #
Instance details Defined in Data.RAVec Methods fmap :: (a -> b0) -> RAVec b a -> RAVec b b0 Source # (<$) :: a -> RAVec b b0 -> RAVec b a Source #
SBinI b => Applicative ( RAVec b) Source #
Instance details Defined in Data.RAVec Methods pure :: a -> RAVec b a Source # (<>) :: RAVec b (a -> b0) -> RAVec b a -> RAVec b b0 Source # liftA2 :: (a -> b0 -> c) -> RAVec b a -> RAVec b b0 -> RAVec b c Source # (>) :: RAVec b a -> RAVec b b0 -> RAVec b b0 Source # (<*) :: RAVec b a -> RAVec b b0 -> RAVec b a Source #
Foldable ( RAVec b) Source #
Instance details Defined in Data.RAVec Methods fold :: Monoid m => RAVec b m -> m Source # foldMap :: Monoid m => (a -> m) -> RAVec b a -> m Source # foldMap' :: Monoid m => (a -> m) -> RAVec b a -> m Source # foldr :: (a -> b0 -> b0) -> b0 -> RAVec b a -> b0 Source # foldr' :: (a -> b0 -> b0) -> b0 -> RAVec b a -> b0 Source # foldl :: (b0 -> a -> b0) -> b0 -> RAVec b a -> b0 Source # foldl' :: (b0 -> a -> b0) -> b0 -> RAVec b a -> b0 Source # foldr1 :: (a -> a -> a) -> RAVec b a -> a Source # foldl1 :: (a -> a -> a) -> RAVec b a -> a Source # toList :: RAVec b a -> [a] Source # null :: RAVec b a -> Bool Source # length :: RAVec b a -> Int Source # elem :: Eq a => a -> RAVec b a -> Bool Source # maximum :: Ord a => RAVec b a -> a Source # minimum :: Ord a => RAVec b a -> a Source # sum :: Num a => RAVec b a -> a Source # product :: Num a => RAVec b a -> a Source #
Traversable ( RAVec b) Source #
Instance details Defined in Data.RAVec Methods traverse :: Applicative f => (a -> f b0) -> RAVec b a -> f ( RAVec b b0) Source # sequenceA :: Applicative f => RAVec b (f a) -> f ( RAVec b a) Source # mapM :: Monad m => (a -> m b0) -> RAVec b a -> m ( RAVec b b0) Source # sequence :: Monad m => RAVec b (m a) -> m ( RAVec b a) Source #
SBinI b => Arbitrary1 ( RAVec b) Source #
Instance details Defined in Data.RAVec Methods liftArbitrary :: Gen a -> Gen ( RAVec b a) Source # liftShrink :: (a -> [a]) -> RAVec b a -> [ RAVec b a] Source #
SBinI b => Distributive ( RAVec b) Source #
Instance details Defined in Data.RAVec Methods distribute :: Functor f => f ( RAVec b a) -> RAVec b (f a) Source # collect :: Functor f => (a -> RAVec b b0) -> f a -> RAVec b (f b0) Source # distributeM :: Monad m => m ( RAVec b a) -> RAVec b (m a) Source # collectM :: Monad m => (a -> RAVec b b0) -> m a -> RAVec b (m b0) Source #
SBinI b => Representable ( RAVec b) Source #
Instance details Defined in Data.RAVec Associated Types type Rep ( RAVec b) Source # Methods tabulate :: ( Rep ( RAVec b) -> a) -> RAVec b a Source # index :: RAVec b a -> Rep ( RAVec b) -> a Source #
b ~ ' BP n => Traversable1 ( RAVec b) Source #
Instance details Defined in Data.RAVec Methods traverse1 :: Apply f => (a -> f b0) -> RAVec b a -> f ( RAVec b b0) Source # sequence1 :: Apply f => RAVec b (f b0) -> f ( RAVec b b0) Source #
Apply ( RAVec b) Source #
Instance details Defined in Data.RAVec Methods (<.>) :: RAVec b (a -> b0) -> RAVec b a -> RAVec b b0 Source # (.>) :: RAVec b a -> RAVec b b0 -> RAVec b b0 Source # (<.) :: RAVec b a -> RAVec b b0 -> RAVec b a Source # liftF2 :: (a -> b0 -> c) -> RAVec b a -> RAVec b b0 -> RAVec b c Source #
b ~ ' BP n => Foldable1 ( RAVec b) Source #
Instance details Defined in Data.RAVec Methods fold1 :: Semigroup m => RAVec b m -> m Source # foldMap1 :: Semigroup m => (a -> m) -> RAVec b a -> m Source # toNonEmpty :: RAVec b a -> NonEmpty a Source #
Eq a => Eq ( RAVec b a) Source #
Instance details Defined in Data.RAVec Methods (==) :: RAVec b a -> RAVec b a -> Bool Source # (/=) :: RAVec b a -> RAVec b a -> Bool Source #
Ord a => Ord ( RAVec b a) Source #
Instance details Defined in Data.RAVec Methods compare :: RAVec b a -> RAVec b a -> Ordering Source # (<) :: RAVec b a -> RAVec b a -> Bool Source # (<=) :: RAVec b a -> RAVec b a -> Bool Source # (>) :: RAVec b a -> RAVec b a -> Bool Source # (>=) :: RAVec b a -> RAVec b a -> Bool Source # max :: RAVec b a -> RAVec b a -> RAVec b a Source # min :: RAVec b a -> RAVec b a -> RAVec b a Source #
Show a => Show ( RAVec b a) Source #
Instance details Defined in Data.RAVec Methods showsPrec :: Int -> RAVec b a -> ShowS Source # show :: RAVec b a -> String Source # showList :: [ RAVec b a] -> ShowS Source #
Semigroup a => Semigroup ( RAVec b a) Source #
Instance details Defined in Data.RAVec Methods (<>) :: RAVec b a -> RAVec b a -> RAVec b a Source # sconcat :: NonEmpty ( RAVec b a) -> RAVec b a Source # stimes :: Integral b0 => b0 -> RAVec b a -> RAVec b a Source #
( Monoid a, SBinI b) => Monoid ( RAVec b a) Source #
Instance details Defined in Data.RAVec Methods mempty :: RAVec b a Source # mappend :: RAVec b a -> RAVec b a -> RAVec b a Source # mconcat :: [ RAVec b a] -> RAVec b a Source #
( SBinI b, Function a) => Function ( RAVec b a) Source #
Instance details Defined in Data.RAVec Methods function :: ( RAVec b a -> b0) -> RAVec b a :-> b0 Source #
( SBinI b, Arbitrary a) => Arbitrary ( RAVec b a) Source #
Instance details Defined in Data.RAVec Methods arbitrary :: Gen ( RAVec b a) Source # shrink :: RAVec b a -> [ RAVec b a] Source #
CoArbitrary a => CoArbitrary ( RAVec b a) Source #
Instance details Defined in Data.RAVec Methods coarbitrary :: RAVec b a -> Gen b0 -> Gen b0 Source #
NFData a => NFData ( RAVec b a) Source #
Instance details Defined in Data.RAVec Methods rnf :: RAVec b a -> () Source #
Hashable a => Hashable ( RAVec b a) Source #
Instance details Defined in Data.RAVec Methods hashWithSalt :: Int -> RAVec b a -> Int Source # hash :: RAVec b a -> Int Source #
type Rep ( RAVec b) Source #
Instance details Defined in Data.RAVec type Rep ( RAVec b) = Pos b

Construction

empty :: RAVec Bin0 a Source #

singleton :: a -> RAVec Bin1 a Source #

cons :: a -> RAVec b a -> RAVec ( Succ b) a Source #

Cons an element in front of RAVec .

>>> reifyList "xyz" (print . toList . cons 'a')
"axyz"

withCons :: SBinI b => a -> RAVec b a -> ( SBinPI ( Succ' b) => RAVec ( Succ b) a -> r) -> r Source #

Variant of cons which computes the SBinI dictionary at the same time.

head :: RAVec (' BP b) a -> a Source #

The first element of a non-empty RAVec .

>>> reifyNonEmpty ('x' :| "yz") head
'x'

last :: RAVec (' BP b) a -> a Source #

The last element of a non-empty RAVec .

>>> reifyNonEmpty ('x' :| "yz") last
'z'

Conversion

toList :: RAVec b a -> [a] Source #

toNonEmpty :: RAVec (' BP b) a -> NonEmpty a Source #

fromList :: forall b a. SBinI b => [a] -> Maybe ( RAVec b a) Source #

Convert a list [a] to RAVec b a . Returns Nothing if lengths don't match.

>>> fromList "foo" :: Maybe (RAVec B.Bin3 Char)
Just (NonEmpty (NE (Cons1 (Leaf 'f') (Last (Node (Leaf 'o') (Leaf 'o'))))))

>>> fromList "quux" :: Maybe (RAVec B.Bin3 Char)
Nothing

>>> fromList "xy" :: Maybe (RAVec B.Bin3 Char)
Nothing

reifyNonEmpty :: NonEmpty a -> ( forall b. SBinPI b => RAVec (' BP b) a -> r) -> r Source #

Indexing

(!) :: RAVec b a -> Pos b -> a Source #

Indexing.

>>> let ral :: RAVec B.Bin4 Char; Just ral = fromList "abcd"

>>> ral ! minBound
'a'

>>> ral ! maxBound
'd'

>>> ral ! pop top
'b'

tabulate :: forall b a. SBinI b => ( Pos b -> a) -> RAVec b a Source #

Folds

foldMap :: Monoid m => (a -> m) -> RAVec n a -> m Source #

foldMap1 :: Semigroup m => (a -> m) -> RAVec (' BP b) a -> m Source #

ifoldMap :: Monoid m => ( Pos b -> a -> m) -> RAVec b a -> m Source #

ifoldMap1 :: Semigroup m => ( Pos (' BP b) -> a -> m) -> RAVec (' BP b) a -> m Source #

foldr :: (a -> b -> b) -> b -> RAVec n a -> b Source #

ifoldr :: ( Pos n -> a -> b -> b) -> b -> RAVec n a -> b Source #

Mapping

map :: (a -> b) -> RAVec n a -> RAVec n b Source #

imap :: ( Pos n -> a -> b) -> RAVec n a -> RAVec n b Source #

traverse :: Applicative f => (a -> f b) -> RAVec n a -> f ( RAVec n b) Source #

itraverse :: Applicative f => ( Pos n -> a -> f b) -> RAVec n a -> f ( RAVec n b) Source #

traverse1 :: Apply f => (a -> f b) -> RAVec (' BP n) a -> f ( RAVec (' BP n) b) Source #

itraverse1 :: Apply f => ( Pos (' BP n) -> a -> f b) -> RAVec (' BP n) a -> f ( RAVec (' BP n) b) Source #

Zipping

zipWith :: (a -> b -> c) -> RAVec n a -> RAVec n b -> RAVec n c Source #

Zip two RAVec s with a function.

izipWith :: ( Pos n -> a -> b -> c) -> RAVec n a -> RAVec n b -> RAVec n c Source #

Zip two RAVec s with a function which also takes Pos index.

Universe

universe :: forall b. SBinI b => RAVec b ( Pos b) Source #

>>> universe :: RAVec B.Bin2 (Pos B.Bin2)
NonEmpty (NE (Cons0 (Last (Node (Leaf 0) (Leaf 1)))))

>>> let u = universe :: RAVec B.Bin3 (Pos B.Bin3)
>>> u
NonEmpty (NE (Cons1 (Leaf 0) (Last (Node (Leaf 1) (Leaf 2)))))

>>> P.explicitShow $ u ! Pos (PosP (Here WE))
"Pos (PosP (Here WE))"

>>> let u' = universe :: RAVec B.Bin5 (Pos B.Bin5)

>>> toList u' == sort (toList u')
True

repeat :: forall b a. SBinI b => a -> RAVec b a Source #

Repeat a value.

>>> repeat 'x' :: RAVec B.Bin5 Char
NonEmpty (NE (Cons1 (Leaf 'x') (Cons0 (Last (Node (Node (Leaf 'x') (Leaf 'x')) (Node (Leaf 'x') (Leaf 'x')))))))

QuickCheck

liftArbitrary :: SBinI b => Gen a -> Gen ( RAVec b a) Source #

liftShrink :: (a -> [a]) -> RAVec b a -> [ RAVec b a] Source #