Data.RAVec

Length-indexed random access list.

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

Random access list

data RAVec (b :: Bin) a where

Length indexed random access lists.

Constructors

Empty :: RAVec 'BZ a

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

Instances

Functor (RAVec b)

Defined in Data.RAVec

Methods

fmap :: (a -> b0) -> RAVec b a -> RAVec b b0

(<$) :: a -> RAVec b b0 -> RAVec b a

SBinI b => Applicative (RAVec b)

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

Foldable (RAVec b)

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

Traversable (RAVec b)

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 => Arbitrary1 (RAVec b)

Defined in Data.RAVec

Methods

liftArbitrary :: Gen a -> Gen (RAVec b a)

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

SBinI b => Distributive (RAVec b)

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)

SBinI b => Representable (RAVec b)

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

b ~ 'BP n => Traversable1 (RAVec b)

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)

b ~ 'BP n => Foldable1 (RAVec b)

Defined in Data.RAVec

Methods

fold1 :: Semigroup m => RAVec b m -> m

foldMap1 :: Semigroup m => (a -> m) -> RAVec b a -> m

toNonEmpty :: RAVec b a -> NonEmpty a

Apply (RAVec b)

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

FunctorWithIndex (Pos n) (RAVec n)

Since: 0.2

Defined in Data.RAVec

Methods

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

FoldableWithIndex (Pos n) (RAVec n)

Since: 0.2

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

TraversableWithIndex (Pos n) (RAVec n)

Since: 0.2

Defined in Data.RAVec

Methods

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

Eq a => Eq (RAVec b a)

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)

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

Show a => Show (RAVec b a)

Defined in Data.RAVec

Methods

showsPrec :: Int -> RAVec b a -> ShowS

show :: RAVec b a -> String

showList :: [RAVec b a] -> ShowS

Semigroup a => Semigroup (RAVec b a)

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

(Monoid a, SBinI b) => Monoid (RAVec b a)

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

(SBinI b, Function a) => Function (RAVec b a)

Defined in Data.RAVec

Methods

function :: (RAVec b a -> b0) -> RAVec b a :-> b0

(SBinI b, Arbitrary a) => Arbitrary (RAVec b a)

Defined in Data.RAVec

Methods

arbitrary :: Gen (RAVec b a)

shrink :: RAVec b a -> [RAVec b a]

CoArbitrary a => CoArbitrary (RAVec b a)

Defined in Data.RAVec

Methods

coarbitrary :: RAVec b a -> Gen b0 -> Gen b0

NFData a => NFData (RAVec b a)

Defined in Data.RAVec

Methods

rnf :: RAVec b a -> ()

Hashable a => Hashable (RAVec b a)

Defined in Data.RAVec

Methods

hashWithSalt :: Int -> RAVec b a -> Int

hash :: RAVec b a -> Int

type Rep (RAVec b)

Defined in Data.RAVec

type Rep (RAVec b) = Pos b

Construction

empty :: RAVec Bin0 a

singleton :: a -> RAVec Bin1 a

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

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

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

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

The first element of a non-empty RAVec.

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

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

The last element of a non-empty RAVec.

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

Conversion

toList :: RAVec b a -> [a]

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

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

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

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

Indexing

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

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

Folds

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

Special folds

null :: RAVec n a -> Bool

Mapping

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)

Zipping

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

Zip two RAVecs with a function.

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

Zip two RAVecs with a function which also takes Pos index.

Universe

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

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

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)

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