Safe Haskell	Safe
Language	Haskell2010

Data.RAVec

Contents

Random access list
Construction
Conversion
Indexing
Folds
Special 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)
reifyList :: [a] -> (forall b. SBinI b => RAVec b a -> r) -> r
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
null :: RAVec n a -> Bool
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

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

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

>>> reifyList "foo" print
NonEmpty (NE (Cons1 (Leaf 'f') (Last (Node (Leaf 'o') (Leaf 'o')))))

>>> reifyList "xyzzy" toList
"xyzzy"

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 #

Special folds

null :: RAVec n a -> Bool 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 RAVecs with a function.

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

Zip two RAVecs 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 #