{-# LANGUAGE RankNTypes, DerivingVia, DeriveTraversable, PatternSynonyms, ViewPatterns #-} {-# LANGUAGE BangPatterns,UndecidableInstances,MultiParamTypeClasses #-} {-# LANGUAGE MonadComprehensions,RoleAnnotations, QuantifiedConstraints #-} {-# LANGUAGE Trustworthy, MagicHash#-} {-# LANGUAGE ScopedTypeVariables #-} module Data.RAList.Co( --module RA RAList(Cons,Nil,RCons,(:|),(:.)) -- * lookups , lookup , lookupM , lookupWithDefault , (!!) , lookupCC -- * function form of constructing and destructing ,cons ,uncons --,traverse --,foldr --,foldl --,foldl' -- * zipping ,zip ,zipWith ,unzip -- -- * Extracting sublists , take , drop , replicate , splitAt -- * from traverse and foldable and ilk ,foldl' ,foldr ,traverse ,mapM ,mapM_ ,unfoldr -- * indexed folds etc ,ifoldMap ,imap ,itraverse ,ifoldl' ,ifoldr ,imapM -- * filter and friends , filter , partition , mapMaybe , catMaybes , wither -- * foldable cousins ,elem ,length ,wLength -- * The \"@generic@\" operations -- | The prefix \`@generic@\' indicates an overloaded function that -- is a generalized version of a "Prelude" function. , genericLength , genericTake , genericDrop , genericSplitAt , genericIndex , genericReplicate -- * Update , update , adjust -- * Append ,(++) -- * list conversion , fromList , toList ) where import Data.Word --import qualified Prelude as P import Prelude hiding ( (++), head, last, tail, init, null, length, map, reverse, foldl, foldl1, foldr, foldr1, concat, concatMap, and, or, any, all, sum, product, maximum, minimum, take, drop, elem, splitAt, notElem, lookup, replicate, (!!), filter, zip, zipWith, unzip ) import Data.Foldable.WithIndex import Data.Functor.WithIndex import Data.Traversable.WithIndex import Control.Applicative.Backwards import Data.RAList.Internal -- provides indexing applicative --import qualfieData.RAList as RA hiding ( -- (!!) -- ,lookupWithDefault -- ,lookupM -- ,lookup -- , lookupCC ) import qualified Data.RAList as QRA import qualified Control.Monad.Fail as MF import Data.Foldable import Data.Traversable() import GHC.Exts (IsList) import Control.Monad.Zip import Data.Coerce import GHC.Generics(Generic,Generic1) import Control.Applicative(Applicative(liftA2)) import Data.Type.Coercion import Unsafe.Coerce infixl 9 !! infixr 5 `cons`, ++ -- | Cons pattern, à la ':' for list, prefix infixr 5 `Cons` pattern Cons :: forall a. a -> RAList a -> RAList a pattern $bCons :: a -> RAList a -> RAList a $mCons :: forall r a. RAList a -> (a -> RAList a -> r) -> (Void# -> r) -> r Cons x xs <- (uncons -> Just (x, xs ) ) where Cons a x RAList a xs = (a -> RAList a -> RAList a forall a. a -> RAList a -> RAList a cons a x RAList a xs) -- | the '[]' analogue pattern Nil :: forall a . RAList a pattern $bNil :: RAList a $mNil :: forall r a. RAList a -> (Void# -> r) -> (Void# -> r) -> r Nil = CoIndex QRA.Nil {-# COMPLETE Cons, Nil #-} -- | just 'Cons' but flipped arguments infixl 5 `RCons` pattern RCons :: forall a. RAList a -> a -> RAList a pattern $bRCons :: RAList a -> a -> RAList a $mRCons :: forall r a. RAList a -> (RAList a -> a -> r) -> (Void# -> r) -> r RCons xs x = Cons x xs {-# COMPLETE RCons, Nil #-} -- | infix 'Cons', aka : , but for RAlist infixr 5 :| pattern (:|) :: forall a. a -> RAList a -> RAList a pattern x $b:| :: a -> RAList a -> RAList a $m:| :: forall r a. RAList a -> (a -> RAList a -> r) -> (Void# -> r) -> r :| xs = Cons x xs {-# COMPLETE (:|), Nil #-} -- | infix 'RCons', aka flipped : infixl 5 :. pattern (:.) :: forall a. RAList a -> a -> RAList a pattern xs $b:. :: RAList a -> a -> RAList a $m:. :: forall r a. RAList a -> (RAList a -> a -> r) -> (Void# -> r) -> r :. x = Cons x xs {-# COMPLETE (:.), Nil #-} -- | friendly list to RAList conversion fromList :: [a] -> RAList a fromList :: [a] -> RAList a fromList = (a -> RAList a -> RAList a) -> RAList a -> [a] -> RAList a forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr a -> RAList a -> RAList a forall a. a -> RAList a -> RAList a Cons RAList a forall a. RAList a Nil -- | This type (@'RAList' a@) indexes back to front, i.e. for nonempty lists @l@ : head of l == (l @'!!' ('genericLength'@ l - 1 ))@ -- and @last l == l '!!' 0 @. RAList also has a logarithmic complexity 'drop' operation, and different semantics for 'zip' and related operations -- -- -- for complete pattern matching, you can use any pair of: -- -- - ':|' , 'Nil' -- -- - ':.' , 'Nil' -- -- - 'Cons' , 'Nil' -- -- - 'RCons' , 'Nil' -- -- The Reversed order pattern synonyms are provided -- to enable certain codes to match pen/paper notation for ordered variable environments newtype RAList a = CoIndex {RAList a -> RAList a reindex :: QRA.RAList a } deriving stock (Functor RAList Foldable RAList Functor RAList -> Foldable RAList -> (forall (f :: * -> *) a b. Applicative f => (a -> f b) -> RAList a -> f (RAList b)) -> (forall (f :: * -> *) a. Applicative f => RAList (f a) -> f (RAList a)) -> (forall (m :: * -> *) a b. Monad m => (a -> m b) -> RAList a -> m (RAList b)) -> (forall (m :: * -> *) a. Monad m => RAList (m a) -> m (RAList a)) -> Traversable RAList (a -> f b) -> RAList a -> f (RAList b) forall (t :: * -> *). Functor t -> Foldable t -> (forall (f :: * -> *) a b. Applicative f => (a -> f b) -> t a -> f (t b)) -> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a)) -> (forall (m :: * -> *) a b. Monad m => (a -> m b) -> t a -> m (t b)) -> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a)) -> Traversable t forall (m :: * -> *) a. Monad m => RAList (m a) -> m (RAList a) forall (f :: * -> *) a. Applicative f => RAList (f a) -> f (RAList a) forall (m :: * -> *) a b. Monad m => (a -> m b) -> RAList a -> m (RAList b) forall (f :: * -> *) a b. Applicative f => (a -> f b) -> RAList a -> f (RAList b) sequence :: RAList (m a) -> m (RAList a) $csequence :: forall (m :: * -> *) a. Monad m => RAList (m a) -> m (RAList a) mapM :: (a -> m b) -> RAList a -> m (RAList b) $cmapM :: forall (m :: * -> *) a b. Monad m => (a -> m b) -> RAList a -> m (RAList b) sequenceA :: RAList (f a) -> f (RAList a) $csequenceA :: forall (f :: * -> *) a. Applicative f => RAList (f a) -> f (RAList a) traverse :: (a -> f b) -> RAList a -> f (RAList b) $ctraverse :: forall (f :: * -> *) a b. Applicative f => (a -> f b) -> RAList a -> f (RAList b) $cp2Traversable :: Foldable RAList $cp1Traversable :: Functor RAList Traversable) deriving (a -> RAList a -> Bool RAList m -> m RAList a -> [a] RAList a -> Bool RAList a -> Int RAList a -> a RAList a -> a RAList a -> a RAList a -> a (a -> m) -> RAList a -> m (a -> m) -> RAList a -> m (a -> b -> b) -> b -> RAList a -> b (a -> b -> b) -> b -> RAList a -> b (b -> a -> b) -> b -> RAList a -> b (b -> a -> b) -> b -> RAList a -> b (a -> a -> a) -> RAList a -> a (a -> a -> a) -> RAList a -> a (forall m. Monoid m => RAList m -> m) -> (forall m a. Monoid m => (a -> m) -> RAList a -> m) -> (forall m a. Monoid m => (a -> m) -> RAList a -> m) -> (forall a b. (a -> b -> b) -> b -> RAList a -> b) -> (forall a b. (a -> b -> b) -> b -> RAList a -> b) -> (forall b a. (b -> a -> b) -> b -> RAList a -> b) -> (forall b a. (b -> a -> b) -> b -> RAList a -> b) -> (forall a. (a -> a -> a) -> RAList a -> a) -> (forall a. (a -> a -> a) -> RAList a -> a) -> (forall a. RAList a -> [a]) -> (forall a. RAList a -> Bool) -> (forall a. RAList a -> Int) -> (forall a. Eq a => a -> RAList a -> Bool) -> (forall a. Ord a => RAList a -> a) -> (forall a. Ord a => RAList a -> a) -> (forall a. Num a => RAList a -> a) -> (forall a. Num a => RAList a -> a) -> Foldable RAList forall a. Eq a => a -> RAList a -> Bool forall a. Num a => RAList a -> a forall a. Ord a => RAList a -> a forall m. Monoid m => RAList m -> m forall a. RAList a -> Bool forall a. RAList a -> Int forall a. RAList a -> [a] forall a. (a -> a -> a) -> RAList a -> a forall m a. Monoid m => (a -> m) -> RAList a -> m forall b a. (b -> a -> b) -> b -> RAList a -> b forall a b. (a -> b -> b) -> b -> RAList a -> b forall (t :: * -> *). (forall m. Monoid m => t m -> m) -> (forall m a. Monoid m => (a -> m) -> t a -> m) -> (forall m a. Monoid m => (a -> m) -> t a -> m) -> (forall a b. (a -> b -> b) -> b -> t a -> b) -> (forall a b. (a -> b -> b) -> b -> t a -> b) -> (forall b a. (b -> a -> b) -> b -> t a -> b) -> (forall b a. (b -> a -> b) -> b -> t a -> b) -> (forall a. (a -> a -> a) -> t a -> a) -> (forall a. (a -> a -> a) -> t a -> a) -> (forall a. t a -> [a]) -> (forall a. t a -> Bool) -> (forall a. t a -> Int) -> (forall a. Eq a => a -> t a -> Bool) -> (forall a. Ord a => t a -> a) -> (forall a. Ord a => t a -> a) -> (forall a. Num a => t a -> a) -> (forall a. Num a => t a -> a) -> Foldable t product :: RAList a -> a $cproduct :: forall a. Num a => RAList a -> a sum :: RAList a -> a $csum :: forall a. Num a => RAList a -> a minimum :: RAList a -> a $cminimum :: forall a. Ord a => RAList a -> a maximum :: RAList a -> a $cmaximum :: forall a. Ord a => RAList a -> a elem :: a -> RAList a -> Bool $celem :: forall a. Eq a => a -> RAList a -> Bool length :: RAList a -> Int $clength :: forall a. RAList a -> Int null :: RAList a -> Bool $cnull :: forall a. RAList a -> Bool toList :: RAList a -> [a] $ctoList :: forall a. RAList a -> [a] foldl1 :: (a -> a -> a) -> RAList a -> a $cfoldl1 :: forall a. (a -> a -> a) -> RAList a -> a foldr1 :: (a -> a -> a) -> RAList a -> a $cfoldr1 :: forall a. (a -> a -> a) -> RAList a -> a foldl' :: (b -> a -> b) -> b -> RAList a -> b $cfoldl' :: forall b a. (b -> a -> b) -> b -> RAList a -> b foldl :: (b -> a -> b) -> b -> RAList a -> b $cfoldl :: forall b a. (b -> a -> b) -> b -> RAList a -> b foldr' :: (a -> b -> b) -> b -> RAList a -> b $cfoldr' :: forall a b. (a -> b -> b) -> b -> RAList a -> b foldr :: (a -> b -> b) -> b -> RAList a -> b $cfoldr :: forall a b. (a -> b -> b) -> b -> RAList a -> b foldMap' :: (a -> m) -> RAList a -> m $cfoldMap' :: forall m a. Monoid m => (a -> m) -> RAList a -> m foldMap :: (a -> m) -> RAList a -> m $cfoldMap :: forall m a. Monoid m => (a -> m) -> RAList a -> m fold :: RAList m -> m $cfold :: forall m. Monoid m => RAList m -> m Foldable,a -> RAList b -> RAList a (a -> b) -> RAList a -> RAList b (forall a b. (a -> b) -> RAList a -> RAList b) -> (forall a b. a -> RAList b -> RAList a) -> Functor RAList forall a b. a -> RAList b -> RAList a forall a b. (a -> b) -> RAList a -> RAList b forall (f :: * -> *). (forall a b. (a -> b) -> f a -> f b) -> (forall a b. a -> f b -> f a) -> Functor f <$ :: a -> RAList b -> RAList a $c<$ :: forall a b. a -> RAList b -> RAList a fmap :: (a -> b) -> RAList a -> RAList b $cfmap :: forall a b. (a -> b) -> RAList a -> RAList b Functor,Rep1 RAList a -> RAList a RAList a -> Rep1 RAList a (forall a. RAList a -> Rep1 RAList a) -> (forall a. Rep1 RAList a -> RAList a) -> Generic1 RAList forall a. Rep1 RAList a -> RAList a forall a. RAList a -> Rep1 RAList a forall k (f :: k -> *). (forall (a :: k). f a -> Rep1 f a) -> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f to1 :: Rep1 RAList a -> RAList a $cto1 :: forall a. Rep1 RAList a -> RAList a from1 :: RAList a -> Rep1 RAList a $cfrom1 :: forall a. RAList a -> Rep1 RAList a Generic1) via QRA.RAList deriving (Semigroup (RAList a) RAList a Semigroup (RAList a) -> RAList a -> (RAList a -> RAList a -> RAList a) -> ([RAList a] -> RAList a) -> Monoid (RAList a) [RAList a] -> RAList a RAList a -> RAList a -> RAList a forall a. Semigroup (RAList a) forall a. RAList a forall a. Semigroup a -> a -> (a -> a -> a) -> ([a] -> a) -> Monoid a forall a. [RAList a] -> RAList a forall a. RAList a -> RAList a -> RAList a mconcat :: [RAList a] -> RAList a $cmconcat :: forall a. [RAList a] -> RAList a mappend :: RAList a -> RAList a -> RAList a $cmappend :: forall a. RAList a -> RAList a -> RAList a mempty :: RAList a $cmempty :: forall a. RAList a $cp1Monoid :: forall a. Semigroup (RAList a) Monoid,b -> RAList a -> RAList a NonEmpty (RAList a) -> RAList a RAList a -> RAList a -> RAList a (RAList a -> RAList a -> RAList a) -> (NonEmpty (RAList a) -> RAList a) -> (forall b. Integral b => b -> RAList a -> RAList a) -> Semigroup (RAList a) forall b. Integral b => b -> RAList a -> RAList a forall a. NonEmpty (RAList a) -> RAList a forall a. RAList a -> RAList a -> RAList a forall a. (a -> a -> a) -> (NonEmpty a -> a) -> (forall b. Integral b => b -> a -> a) -> Semigroup a forall a b. Integral b => b -> RAList a -> RAList a stimes :: b -> RAList a -> RAList a $cstimes :: forall a b. Integral b => b -> RAList a -> RAList a sconcat :: NonEmpty (RAList a) -> RAList a $csconcat :: forall a. NonEmpty (RAList a) -> RAList a <> :: RAList a -> RAList a -> RAList a $c<> :: forall a. RAList a -> RAList a -> RAList a Semigroup,RAList a -> RAList a -> Bool (RAList a -> RAList a -> Bool) -> (RAList a -> RAList a -> Bool) -> Eq (RAList a) forall a. Eq a => RAList a -> RAList a -> Bool forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a /= :: RAList a -> RAList a -> Bool $c/= :: forall a. Eq a => RAList a -> RAList a -> Bool == :: RAList a -> RAList a -> Bool $c== :: forall a. Eq a => RAList a -> RAList a -> Bool Eq,Eq (RAList a) Eq (RAList a) -> (RAList a -> RAList a -> Ordering) -> (RAList a -> RAList a -> Bool) -> (RAList a -> RAList a -> Bool) -> (RAList a -> RAList a -> Bool) -> (RAList a -> RAList a -> Bool) -> (RAList a -> RAList a -> RAList a) -> (RAList a -> RAList a -> RAList a) -> Ord (RAList a) RAList a -> RAList a -> Bool RAList a -> RAList a -> Ordering RAList a -> RAList a -> RAList a forall a. Eq a -> (a -> a -> Ordering) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> a) -> (a -> a -> a) -> Ord a forall a. Ord a => Eq (RAList a) forall a. Ord a => RAList a -> RAList a -> Bool forall a. Ord a => RAList a -> RAList a -> Ordering forall a. Ord a => RAList a -> RAList a -> RAList a min :: RAList a -> RAList a -> RAList a $cmin :: forall a. Ord a => RAList a -> RAList a -> RAList a max :: RAList a -> RAList a -> RAList a $cmax :: forall a. Ord a => RAList a -> RAList a -> RAList a >= :: RAList a -> RAList a -> Bool $c>= :: forall a. Ord a => RAList a -> RAList a -> Bool > :: RAList a -> RAList a -> Bool $c> :: forall a. Ord a => RAList a -> RAList a -> Bool <= :: RAList a -> RAList a -> Bool $c<= :: forall a. Ord a => RAList a -> RAList a -> Bool < :: RAList a -> RAList a -> Bool $c< :: forall a. Ord a => RAList a -> RAList a -> Bool compare :: RAList a -> RAList a -> Ordering $ccompare :: forall a. Ord a => RAList a -> RAList a -> Ordering $cp1Ord :: forall a. Ord a => Eq (RAList a) Ord,Int -> RAList a -> ShowS [RAList a] -> ShowS RAList a -> String (Int -> RAList a -> ShowS) -> (RAList a -> String) -> ([RAList a] -> ShowS) -> Show (RAList a) forall a. Show a => Int -> RAList a -> ShowS forall a. Show a => [RAList a] -> ShowS forall a. Show a => RAList a -> String forall a. (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a showList :: [RAList a] -> ShowS $cshowList :: forall a. Show a => [RAList a] -> ShowS show :: RAList a -> String $cshow :: forall a. Show a => RAList a -> String showsPrec :: Int -> RAList a -> ShowS $cshowsPrec :: forall a. Show a => Int -> RAList a -> ShowS Show,Int -> [Item (RAList a)] -> RAList a [Item (RAList a)] -> RAList a RAList a -> [Item (RAList a)] ([Item (RAList a)] -> RAList a) -> (Int -> [Item (RAList a)] -> RAList a) -> (RAList a -> [Item (RAList a)]) -> IsList (RAList a) forall a. Int -> [Item (RAList a)] -> RAList a forall a. [Item (RAList a)] -> RAList a forall a. RAList a -> [Item (RAList a)] forall l. ([Item l] -> l) -> (Int -> [Item l] -> l) -> (l -> [Item l]) -> IsList l toList :: RAList a -> [Item (RAList a)] $ctoList :: forall a. RAList a -> [Item (RAList a)] fromListN :: Int -> [Item (RAList a)] -> RAList a $cfromListN :: forall a. Int -> [Item (RAList a)] -> RAList a fromList :: [Item (RAList a)] -> RAList a $cfromList :: forall a. [Item (RAList a)] -> RAList a IsList,Rep (RAList a) x -> RAList a RAList a -> Rep (RAList a) x (forall x. RAList a -> Rep (RAList a) x) -> (forall x. Rep (RAList a) x -> RAList a) -> Generic (RAList a) forall x. Rep (RAList a) x -> RAList a forall x. RAList a -> Rep (RAList a) x forall a. (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a forall a x. Rep (RAList a) x -> RAList a forall a x. RAList a -> Rep (RAList a) x to :: Rep (RAList a) x -> RAList a $cto :: forall a x. Rep (RAList a) x -> RAList a from :: RAList a -> Rep (RAList a) x $cfrom :: forall a x. RAList a -> Rep (RAList a) x Generic) via QRA.RAList a type role RAList representational --- > itraverse (\ix _val -> Id.Identity ix) $ ([(),(),(),()]:: Co.RAList ()) --- Identity (fromList [3,2,1,0]) instance TraversableWithIndex Word64 RAList where {-# INLINE itraverse #-} itraverse :: (Word64 -> a -> f b) -> RAList a -> f (RAList b) itraverse = \ Word64 -> a -> f b f RAList a s -> (Word64, f (RAList b)) -> f (RAList b) forall a b. (a, b) -> b snd ((Word64, f (RAList b)) -> f (RAList b)) -> (Word64, f (RAList b)) -> f (RAList b) forall a b. (a -> b) -> a -> b $ Indexing f (RAList b) -> Word64 -> (Word64, f (RAList b)) forall (f :: * -> *) a. Indexing f a -> Word64 -> (Word64, f a) runIndexing ( Backwards (Indexing f) (RAList b) -> Indexing f (RAList b) forall k (f :: k -> *) (a :: k). Backwards f a -> f a forwards (Backwards (Indexing f) (RAList b) -> Indexing f (RAList b)) -> Backwards (Indexing f) (RAList b) -> Indexing f (RAList b) forall a b. (a -> b) -> a -> b $ (a -> Backwards (Indexing f) b) -> RAList a -> Backwards (Indexing f) (RAList b) forall (t :: * -> *) (f :: * -> *) a b. (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) traverse (\a a -> Indexing f b -> Backwards (Indexing f) b forall k (f :: k -> *) (a :: k). f a -> Backwards f a Backwards (Indexing f b -> Backwards (Indexing f) b) -> Indexing f b -> Backwards (Indexing f) b forall a b. (a -> b) -> a -> b $ (Word64 -> (Word64, f b)) -> Indexing f b forall (f :: * -> *) a. (Word64 -> (Word64, f a)) -> Indexing f a Indexing (\Word64 i -> Word64 i Word64 -> (Word64, f b) -> (Word64, f b) `seq` (Word64 i Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a + Word64 1, Word64 -> a -> f b f Word64 i a a))) RAList a s) Word64 0 -- TODO; benchmark this vs counting downn from the start instance FoldableWithIndex Word64 RAList where instance FunctorWithIndex Word64 RAList where instance Applicative RAList where {-# INLINE pure #-} pure :: a -> RAList a pure = \a x -> a -> RAList a -> RAList a forall a. a -> RAList a -> RAList a Cons a x RAList a forall a. RAList a Nil {-# INLINE (<*>) #-} RAList (a -> b) fs <*> :: RAList (a -> b) -> RAList a -> RAList b <*> RAList a xs = [a -> b f a x | a -> b f <- RAList (a -> b) fs, a x <- RAList a xs] {-# INLINE liftA2 #-} liftA2 :: (a -> b -> c) -> RAList a -> RAList b -> RAList c liftA2 a -> b -> c f RAList a xs RAList b ys = [a -> b -> c f a x b y | a x <- RAList a xs, b y <- RAList b ys] {-# INLINE (*>) #-} RAList a xs *> :: RAList a -> RAList b -> RAList b *> RAList b ys = [b y | a _ <- RAList a xs, b y <- RAList b ys] instance Monad RAList where return :: a -> RAList a return = a -> RAList a forall (f :: * -> *) a. Applicative f => a -> f a pure >>= :: RAList a -> (a -> RAList b) -> RAList b (>>=) = (\RAList a ls a -> RAList b f -> RAList b -> RAList b forall a. RAList a -> RAList a CoIndex (RAList b -> RAList b) -> RAList b -> RAList b forall a b. (a -> b) -> a -> b $ (a -> RAList b) -> RAList a -> RAList b forall a b. (a -> RAList b) -> RAList a -> RAList b QRA.concatMap (\ a x -> RAList b -> RAList b coerce (RAList b -> RAList b) -> RAList b -> RAList b forall a b. (a -> b) -> a -> b $ a -> RAList b f a x) (RAList a -> RAList b) -> RAList a -> RAList b forall a b. (a -> b) -> a -> b $ RAList a -> RAList a forall a. RAList a -> RAList a reindex RAList a ls ) --- QUESTION --- am i wrong for using the Ziplist applicative with my monads? {- if we have <*> === zipWith ($) that means we need to have the monad be the DIAGONLIZATION rather than concat map we need ap === <*> ap :: (Monad m) => m (a -> b) -> m a -> m b ap m1 m2 = do { x1 <- m1; x2 <- m2; return (x1 x2) } -- Since many Applicative instances define (<*>) = ap, we -- cannot define ap = (<*>) -} instance MonadZip RAList where mzipWith :: (a -> b -> c) -> RAList a -> RAList b -> RAList c mzipWith = (a -> b -> c) -> RAList a -> RAList b -> RAList c forall a b c. (a -> b -> c) -> RAList a -> RAList b -> RAList c zipWith munzip :: RAList (a, b) -> (RAList a, RAList b) munzip = RAList (a, b) -> (RAList a, RAList b) forall a b. RAList (a, b) -> (RAList a, RAList b) unzip -- | implementation underlying smart constructor used by pattern synonyms cons :: a -> RAList a -> RAList a cons :: a -> RAList a -> RAList a cons a x (CoIndex RAList a xs) = RAList a -> RAList a forall a. RAList a -> RAList a CoIndex (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ a -> RAList a -> RAList a forall a. a -> RAList a -> RAList a QRA.cons a x RAList a xs -- | how matching is implemented uncons :: RAList a -> Maybe (a, RAList a) uncons :: RAList a -> Maybe (a, RAList a) uncons (CoIndex RAList a xs) = case RAList a -> Maybe (a, RAList a) forall a. RAList a -> Maybe (a, RAList a) QRA.uncons RAList a xs of Maybe (a, RAList a) Nothing -> Maybe (a, RAList a) forall a. Maybe a Nothing Just(a h,RAList a rest) -> (a, RAList a) -> Maybe (a, RAList a) forall a. a -> Maybe a Just (a h,RAList a -> RAList a forall a. RAList a -> RAList a CoIndex RAList a rest) -- double check what the complexity is -- | @'drop' i l@ drops the first @i@ elments, @O(log i)@ complexity, drop :: Word64 -> RAList a -> RAList a drop :: Word64 -> RAList a -> RAList a drop = \ Word64 ix (CoIndex RAList a ls)-> RAList a -> RAList a forall a. RAList a -> RAList a CoIndex (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ Word64 -> RAList a -> RAList a forall a. Word64 -> RAList a -> RAList a QRA.drop Word64 ix RAList a ls -- | @'take' i l@, keeps the first @i@ elements, @O(i)@ complexity take :: Word64 -> RAList a -> RAList a take :: Word64 -> RAList a -> RAList a take = \Word64 ix (CoIndex RAList a ls ) -> RAList a -> RAList a forall a. RAList a -> RAList a CoIndex (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ Word64 -> RAList a -> RAList a forall a. Word64 -> RAList a -> RAList a QRA.take Word64 ix RAList a ls --- being lazy? yes :) -- | performs both drop and take splitAt :: Word64 -> RAList a -> (RAList a, RAList a ) splitAt :: Word64 -> RAList a -> (RAList a, RAList a) splitAt = Word64 -> RAList a -> (RAList a, RAList a) forall n a. Integral n => n -> RAList a -> (RAList a, RAList a) genericSplitAt -- | @'replicate' n a @ makes a RAList with n values of a replicate :: Word64 -> a -> RAList a replicate :: Word64 -> a -> RAList a replicate = Word64 -> a -> RAList a forall n a. Integral n => n -> a -> RAList a genericReplicate -- | list zip, zip :: RAList a -> RAList b -> RAList (a, b) zip :: RAList a -> RAList b -> RAList (a, b) zip = (a -> b -> (a, b)) -> RAList a -> RAList b -> RAList (a, b) forall a b c. (a -> b -> c) -> RAList a -> RAList b -> RAList c zipWith (,) {-# INLINE unzip #-} -- adapted from List definition in base -- not perfectly certain about being lazy on the *rest* -- but lets leave it for now... though i think my cons -- algorithm precludes it from actually being properly lazy -- TODO : mess with foldr' vs foldr and ~ vs ! for as and bs from unzip definition unzip :: RAList (a,b) -> (RAList a,RAList b) unzip :: RAList (a, b) -> (RAList a, RAList b) unzip = ((a, b) -> (RAList a, RAList b) -> (RAList a, RAList b)) -> (RAList a, RAList b) -> RAList (a, b) -> (RAList a, RAList b) forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr' (\(a a,b b) (!RAList a as,!RAList b bs) -> (a aa -> RAList a -> RAList a forall a. a -> RAList a -> RAList a :| RAList a as,b bb -> RAList b -> RAList b forall a. a -> RAList a -> RAList a :|RAList b bs)) (RAList a forall a. RAList a Nil,RAList b forall a. RAList a Nil) --unzip = foldr (\(a,b) ~(as,bs) -> (a:| as,b:|bs)) (Nil,Nil) --- this zipWith has better efficiency than the opposite one -- in the case of differing length RALists, because we can drop from the front -- efficiently but not from the back! -- we need to do this flip around --- this semantic arise from counting the indexing from the rear in this module zipWith :: (a -> b -> c ) -> RAList a -> RAList b -> RAList c zipWith :: (a -> b -> c) -> RAList a -> RAList b -> RAList c zipWith = \a -> b -> c f (CoIndex RAList a as) (CoIndex RAList b bs) -> let !alen :: Word64 alen = RAList a -> Word64 forall a. RAList a -> Word64 QRA.wLength RAList a as !blen :: Word64 blen = RAList b -> Word64 forall a. RAList a -> Word64 QRA.wLength RAList b bs in case Word64 -> Word64 -> Ordering forall a. Ord a => a -> a -> Ordering compare Word64 alen Word64 blen of Ordering EQ -> RAList c -> RAList c forall a. RAList a -> RAList a CoIndex (RAList c -> RAList c) -> RAList c -> RAList c forall a b. (a -> b) -> a -> b $ (a -> b -> c) -> RAList a -> RAList b -> RAList c forall a b c. (a -> b -> c) -> RAList a -> RAList b -> RAList c QRA.zipWith a -> b -> c f RAList a as RAList b bs Ordering GT {- alen > blen -}-> RAList c -> RAList c forall a. RAList a -> RAList a CoIndex (RAList c -> RAList c) -> RAList c -> RAList c forall a b. (a -> b) -> a -> b $ (a -> b -> c) -> RAList a -> RAList b -> RAList c forall a b c. (a -> b -> c) -> RAList a -> RAList b -> RAList c QRA.zipWith a -> b -> c f (Word64 -> RAList a -> RAList a forall a. Word64 -> RAList a -> RAList a QRA.drop (Word64 alen Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - Word64 blen) RAList a as) RAList b bs Ordering LT {- alen < blen -} -> RAList c -> RAList c forall a. RAList a -> RAList a CoIndex (RAList c -> RAList c) -> RAList c -> RAList c forall a b. (a -> b) -> a -> b $ (a -> b -> c) -> RAList a -> RAList b -> RAList c forall a b c. (a -> b -> c) -> RAList a -> RAList b -> RAList c QRA.zipWith a -> b -> c f RAList a as (Word64 -> RAList b -> RAList b forall a. Word64 -> RAList a -> RAList a QRA.drop (Word64 blen Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - Word64 alen ) RAList b bs) {-# INLINE (!!) #-} (!!) :: RAList a -> Word64 -> a RAList a rls !! :: RAList a -> Word64 -> a !! Word64 n | Word64 n Word64 -> Word64 -> Bool forall a. Ord a => a -> a -> Bool < Word64 0 = String -> a forall a. HasCallStack => String -> a error String "Data.RAList.Flip.!!: negative index" | Word64 n Word64 -> Word64 -> Bool forall a. Ord a => a -> a -> Bool >= (RAList a -> Word64 forall a. RAList a -> Word64 wLength RAList a rls) = String -> a forall a. HasCallStack => String -> a error String "Data.RAList.Flip.!!: index too large" | Bool otherwise = RAList a -> RAList a forall a. RAList a -> RAList a reindex RAList a rls RAList a -> Word64 -> a forall a. RAList a -> Word64 -> a QRA.!! ((RAList a -> Word64 forall a. RAList a -> Word64 wLength RAList a rls) Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - Word64 n ) {-# INLINE lookupWithDefault #-} lookupWithDefault :: forall t. t -> Word64 -> RAList t -> t lookupWithDefault :: t -> Word64 -> RAList t -> t lookupWithDefault = \ t def Word64 ix RAList t tree -> t -> Word64 -> RAList t -> t forall t. t -> Word64 -> RAList t -> t QRA.lookupWithDefault t def ((RAList t -> Word64 forall a. RAList a -> Word64 wLength RAList t tree) Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - Word64 ix ) (RAList t -> t) -> RAList t -> t forall a b. (a -> b) -> a -> b $ RAList t -> RAList t forall a. RAList a -> RAList a reindex RAList t tree {-# INLINE lookupM #-} lookupM :: forall a m . MF.MonadFail m => Word64 -> RAList a -> m a lookupM :: Word64 -> RAList a -> m a lookupM = \ Word64 ix RAList a tree -> RAList a -> Word64 -> m a forall a (m :: * -> *). MonadFail m => RAList a -> Word64 -> m a QRA.lookupM (RAList a -> RAList a forall a. RAList a -> RAList a reindex RAList a tree) ((RAList a -> Word64 forall a. RAList a -> Word64 wLength RAList a tree) Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - Word64 ix) {-# INLINE lookup #-} lookup :: forall a. Word64 -> RAList a -> Maybe a lookup :: Word64 -> RAList a -> Maybe a lookup = \ Word64 ix RAList a tree -> RAList a -> Word64 -> Maybe a forall a. RAList a -> Word64 -> Maybe a QRA.lookup (RAList a -> RAList a forall a. RAList a -> RAList a reindex RAList a tree) ((RAList a -> Word64 forall a. RAList a -> Word64 wLength RAList a tree) Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - Word64 ix ) {-# INLINE lookupCC #-} lookupCC :: RAList a -> Word64 -> (a -> r) -> (String -> r) -> r lookupCC :: RAList a -> Word64 -> (a -> r) -> (String -> r) -> r lookupCC = \ RAList a tree Word64 ix a -> r f String -> r g -> RAList a -> Word64 -> (a -> r) -> (String -> r) -> r forall a r. RAList a -> Word64 -> (a -> r) -> (String -> r) -> r QRA.lookupCC (RAList a -> RAList a forall a. RAList a -> RAList a reindex RAList a tree) ((RAList a -> Word64 forall a. RAList a -> Word64 wLength RAList a tree) Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - Word64 ix ) a -> r f String -> r g {-# INLINE wLength #-} wLength:: RAList a -> Word64 wLength :: RAList a -> Word64 wLength = \ (CoIndex RAList a ls) -> RAList a -> Word64 forall a. RAList a -> Word64 QRA.wLength RAList a ls (++) :: RAList a -> RAList a -> RAList a ++ :: RAList a -> RAList a -> RAList a (++) = RAList a -> RAList a -> RAList a forall a. Semigroup a => a -> a -> a (<>) partition :: (a->Bool) -> RAList a -> (RAList a, RAList a) partition :: (a -> Bool) -> RAList a -> (RAList a, RAList a) partition = \ a -> Bool f RAList a ls -> (case (a -> Bool) -> RAList a -> (RAList a, RAList a) forall a. (a -> Bool) -> RAList a -> (RAList a, RAList a) QRA.partition a -> Bool f (RAList a -> (RAList a, RAList a)) -> RAList a -> (RAList a, RAList a) forall a b. (a -> b) -> a -> b $ RAList a -> RAList a coerce RAList a ls of (RAList a la, RAList a lb ) -> (RAList a -> RAList a coerce RAList a la , RAList a -> RAList a coerce RAList a lb) ) filter :: forall a . (a -> Bool) -> RAList a -> RAList a filter :: (a -> Bool) -> RAList a -> RAList a filter = \ a -> Bool f RAList a ls -> RAList a -> RAList a coerce (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ (a -> Bool) -> RAList a -> RAList a forall a. (a -> Bool) -> RAList a -> RAList a QRA.filter a -> Bool f (RAList a -> RAList a coerce RAList a ls ) catMaybes :: RAList (Maybe a) -> RAList a catMaybes :: RAList (Maybe a) -> RAList a catMaybes = \RAList (Maybe a) ls -> RAList a -> RAList a coerce (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ (RAList (Maybe a) -> RAList a forall a. RAList (Maybe a) -> RAList a QRA.catMaybes (RAList (Maybe a) -> RAList a) -> RAList (Maybe a) -> RAList a forall a b. (a -> b) -> a -> b $ (forall a. RAList (Maybe a) -> RAList (Maybe a) coerce :: RAList (Maybe a) -> QRA.RAList (Maybe a)) RAList (Maybe a) ls) wither :: forall a b f . (Applicative f) => (a -> f (Maybe b)) -> RAList a -> f (RAList b) wither :: (a -> f (Maybe b)) -> RAList a -> f (RAList b) wither = \a -> f (Maybe b) f RAList a la -> Coercion (f (RAList b)) (f (RAList b)) -> f (RAList b) -> f (RAList b) forall a b. Coercion a b -> a -> b coerceWith Coercion (f (RAList b)) (f (RAList b)) forall a b (f :: * -> *). (Coercible a b, Functor f) => Coercion (f a) (f b) coerceThroughFunctor (f (RAList b) -> f (RAList b)) -> f (RAList b) -> f (RAList b) forall a b. (a -> b) -> a -> b $ (a -> f (Maybe b)) -> RAList a -> f (RAList b) forall a b (f :: * -> *). Applicative f => (a -> f (Maybe b)) -> RAList a -> f (RAList b) QRA.wither a -> f (Maybe b) f (RAList a -> f (RAList b)) -> RAList a -> f (RAList b) forall a b. (a -> b) -> a -> b $ RAList a -> RAList a coerce RAList a la --- -- applicatives / functors can be coerced under, i have spoken {- for context, i otherwise need to do the following : wither :: forall a b f . (Applicative f, (forall c d . Coercible c d => Coercible (f c) (f d)) ) => (a -> f (Maybe b)) -> RAList a -> f (RAList b) wither = \f la -> coerce $ QRA.wither f $ coerce la -} {-#INLINE coerceThroughFunctor #-} coerceThroughFunctor :: forall a b f. (Coercible a b, Functor f) => (Coercion (f a) (f b)) coerceThroughFunctor :: Coercion (f a) (f b) coerceThroughFunctor = (Coercion a b -> Coercion (f a) (f b) forall a b. a -> b unsafeCoerce (Coercion a b forall k (a :: k) (b :: k). Coercible a b => Coercion a b Coercion :: Coercion a b )) :: (Coercion (f a) (f b)) --- mapMaybe :: forall a b . (a -> Maybe b) -> RAList a -> RAList b mapMaybe :: (a -> Maybe b) -> RAList a -> RAList b mapMaybe = \a -> Maybe b f RAList a la -> RAList b -> RAList b coerce (RAList b -> RAList b) -> RAList b -> RAList b forall a b. (a -> b) -> a -> b $ (a -> Maybe b) -> RAList a -> RAList b forall a b. (a -> Maybe b) -> RAList a -> RAList b QRA.mapMaybe a -> Maybe b f (RAList a -> RAList b) -> RAList a -> RAList b forall a b. (a -> b) -> a -> b $ RAList a -> RAList a coerce RAList a la genericLength :: forall a w . Integral w =>RAList a -> w genericLength :: RAList a -> w genericLength RAList a x = RAList a -> w forall w a. Integral w => RAList a -> w QRA.genericLength (RAList a -> w) -> RAList a -> w forall a b. (a -> b) -> a -> b $ RAList a -> RAList a forall a. RAList a -> RAList a reindex RAList a x genericTake :: forall a n . Integral n => n -> RAList a -> RAList a genericTake :: n -> RAList a -> RAList a genericTake n i RAList a x = RAList a -> RAList a coerce (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ n -> RAList a -> RAList a forall n a. Integral n => n -> RAList a -> RAList a QRA.genericTake n i (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ (RAList a -> RAList a coerce :: RAList a -> QRA.RAList a) RAList a x genericDrop :: Integral n => n -> RAList a -> RAList a genericDrop :: n -> RAList a -> RAList a genericDrop n i RAList a x = RAList a -> RAList a coerce (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ n -> RAList a -> RAList a forall n a. Integral n => n -> RAList a -> RAList a QRA.genericDrop n i (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ (forall a. RAList a -> RAList a coerce :: RAList a -> QRA.RAList a) RAList a x genericSplitAt :: Integral n => n -> RAList a -> (RAList a, RAList a) genericSplitAt :: n -> RAList a -> (RAList a, RAList a) genericSplitAt n i RAList a x = case n -> RAList a -> (RAList a, RAList a) forall n a. Integral n => n -> RAList a -> (RAList a, RAList a) QRA.genericSplitAt n i (RAList a -> (RAList a, RAList a)) -> RAList a -> (RAList a, RAList a) forall a b. (a -> b) -> a -> b $ RAList a -> RAList a forall a. RAList a -> RAList a reindex RAList a x of (RAList a a,RAList a b) -> (RAList a -> RAList a coerce RAList a a, RAList a -> RAList a coerce RAList a b) genericIndex :: Integral n => RAList a -> n -> a genericIndex :: RAList a -> n -> a genericIndex RAList a x n i = RAList a -> n -> a forall n a. Integral n => RAList a -> n -> a QRA.genericIndex (RAList a -> RAList a forall a. RAList a -> RAList a reindex RAList a x) n i genericReplicate :: Integral n => n -> a -> RAList a genericReplicate :: n -> a -> RAList a genericReplicate n i a v = RAList a -> RAList a coerce (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ n -> a -> RAList a forall n a. Integral n => n -> a -> RAList a genericReplicate n i a v update :: Word64 -> a -> RAList a -> RAList a update :: Word64 -> a -> RAList a -> RAList a update Word64 i a v RAList a l = (a -> a) -> Word64 -> RAList a -> RAList a forall a. (a -> a) -> Word64 -> RAList a -> RAList a adjust (a -> a -> a forall a b. a -> b -> a const a v) Word64 i RAList a l adjust :: forall a . (a->a) -> Word64 -> RAList a -> RAList a adjust :: (a -> a) -> Word64 -> RAList a -> RAList a adjust a -> a f Word64 i RAList a l = RAList a -> RAList a coerce (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ (a -> a) -> Word64 -> RAList a -> RAList a forall a. (a -> a) -> Word64 -> RAList a -> RAList a adjust a -> a f Word64 i (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ RAList a -> RAList a coerce RAList a l unfoldr :: (b -> Maybe (a, b)) -> b -> RAList a unfoldr :: (b -> Maybe (a, b)) -> b -> RAList a unfoldr b -> Maybe (a, b) f b init = RAList a -> RAList a coerce (RAList a -> RAList a) -> RAList a -> RAList a forall a b. (a -> b) -> a -> b $ (b -> Maybe (a, b)) -> b -> RAList a forall b a. (b -> Maybe (a, b)) -> b -> RAList a QRA.unfoldr b -> Maybe (a, b) f b init