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