{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE ViewPatterns #-}
module Data.List.Snoc
( RList
, Tsil
, nil
, snoc
, singleton
, unsnoc
, pattern Nil
, pattern Snoc
, null
, init
, last
, catMaybes
, toList
, fromList
, reverseIn
, reverseOut
, toArrayN
, toSet
) where
import Prelude hiding (null,init,last,reverse)
import Control.Applicative(Alternative(..))
import Control.DeepSeq (NFData)
import Data.Bifunctor (first)
import Data.Primitive.Contiguous (Contiguous, Element, SmallArray)
import Data.Set (Set)
import GHC.Generics (Generic)
import qualified Data.List as List
import qualified Data.Maybe as Maybe
import qualified Data.Primitive.Contiguous as Arr
import qualified Data.Set as Set
import qualified Prelude
newtype RList a = RList { RList a -> [a]
unRList :: [a] }
deriving stock ((forall x. RList a -> Rep (RList a) x)
-> (forall x. Rep (RList a) x -> RList a) -> Generic (RList a)
forall x. Rep (RList a) x -> RList a
forall x. RList a -> Rep (RList a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (RList a) x -> RList a
forall a x. RList a -> Rep (RList a) x
$cto :: forall a x. Rep (RList a) x -> RList a
$cfrom :: forall a x. RList a -> Rep (RList a) x
Generic)
deriving newtype (a -> RList b -> RList a
(a -> b) -> RList a -> RList b
(forall a b. (a -> b) -> RList a -> RList b)
-> (forall a b. a -> RList b -> RList a) -> Functor RList
forall a b. a -> RList b -> RList a
forall a b. (a -> b) -> RList a -> RList b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> RList b -> RList a
$c<$ :: forall a b. a -> RList b -> RList a
fmap :: (a -> b) -> RList a -> RList b
$cfmap :: forall a b. (a -> b) -> RList a -> RList b
Functor,Functor RList
a -> RList a
Functor RList
-> (forall a. a -> RList a)
-> (forall a b. RList (a -> b) -> RList a -> RList b)
-> (forall a b c. (a -> b -> c) -> RList a -> RList b -> RList c)
-> (forall a b. RList a -> RList b -> RList b)
-> (forall a b. RList a -> RList b -> RList a)
-> Applicative RList
RList a -> RList b -> RList b
RList a -> RList b -> RList a
RList (a -> b) -> RList a -> RList b
(a -> b -> c) -> RList a -> RList b -> RList c
forall a. a -> RList a
forall a b. RList a -> RList b -> RList a
forall a b. RList a -> RList b -> RList b
forall a b. RList (a -> b) -> RList a -> RList b
forall a b c. (a -> b -> c) -> RList a -> RList b -> RList c
forall (f :: * -> *).
Functor f
-> (forall a. a -> f a)
-> (forall a b. f (a -> b) -> f a -> f b)
-> (forall a b c. (a -> b -> c) -> f a -> f b -> f c)
-> (forall a b. f a -> f b -> f b)
-> (forall a b. f a -> f b -> f a)
-> Applicative f
<* :: RList a -> RList b -> RList a
$c<* :: forall a b. RList a -> RList b -> RList a
*> :: RList a -> RList b -> RList b
$c*> :: forall a b. RList a -> RList b -> RList b
liftA2 :: (a -> b -> c) -> RList a -> RList b -> RList c
$cliftA2 :: forall a b c. (a -> b -> c) -> RList a -> RList b -> RList c
<*> :: RList (a -> b) -> RList a -> RList b
$c<*> :: forall a b. RList (a -> b) -> RList a -> RList b
pure :: a -> RList a
$cpure :: forall a. a -> RList a
$cp1Applicative :: Functor RList
Applicative)
instance (NFData a) => NFData (RList a)
instance (Show a) => Show (RList a) where
show :: RList a -> String
show = [a] -> String
forall a. Show a => a -> String
show ([a] -> String) -> (RList a -> [a]) -> RList a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RList a -> [a]
forall a. RList a -> [a]
toList
instance (Read a) => Read (RList a) where
readsPrec :: Int -> ReadS (RList a)
readsPrec Int
i = ((([a], String) -> (RList a, String))
-> [([a], String)] -> [(RList a, String)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((([a], String) -> (RList a, String))
-> [([a], String)] -> [(RList a, String)])
-> (([a] -> RList a) -> ([a], String) -> (RList a, String))
-> ([a] -> RList a)
-> [([a], String)]
-> [(RList a, String)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> RList a) -> ([a], String) -> (RList a, String)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first) [a] -> RList a
forall a. [a] -> RList a
fromList ([([a], String)] -> [(RList a, String)])
-> (String -> [([a], String)]) -> ReadS (RList a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> String -> [([a], String)]
forall a. Read a => Int -> ReadS a
readsPrec Int
i
instance Semigroup (RList a) where
(RList [a]
a) <> :: RList a -> RList a -> RList a
<> (RList [a]
b) = [a] -> RList a
forall a. [a] -> RList a
RList ([a]
b [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> [a]
a)
instance Monoid (RList a) where
mempty :: RList a
mempty = RList a
forall a. RList a
Nil
instance Alternative RList where
empty :: RList a
empty = RList a
forall a. Monoid a => a
mempty
(RList [a]
a) <|> :: RList a -> RList a -> RList a
<|> (RList [a]
b) = [a] -> RList a
forall a. [a] -> RList a
RList ([a]
b [a] -> [a] -> [a]
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> [a]
a)
type Tsil = RList
{-# COMPLETE Nil, Snoc #-}
pattern Nil :: RList a
pattern $bNil :: RList a
$mNil :: forall r a. RList a -> (Void# -> r) -> (Void# -> r) -> r
Nil = RList []
pattern Snoc :: RList a -> a -> RList a
pattern $bSnoc :: RList a -> a -> RList a
$mSnoc :: forall r a. RList a -> (RList a -> a -> r) -> (Void# -> r) -> r
Snoc xs x <- (unsnoc -> Just (xs, x))
where Snoc = RList a -> a -> RList a
forall a. RList a -> a -> RList a
snoc
nil :: RList a
{-# INLINABLE nil #-}
nil :: RList a
nil = [a] -> RList a
forall a. [a] -> RList a
RList []
snoc :: RList a -> a -> RList a
{-# INLINABLE snoc #-}
snoc :: RList a -> a -> RList a
snoc (RList [a]
xs) a
x = [a] -> RList a
forall a. [a] -> RList a
RList (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)
unsnoc :: RList a -> Maybe (RList a, a)
{-# INLINABLE unsnoc #-}
unsnoc :: RList a -> Maybe (RList a, a)
unsnoc (RList []) = Maybe (RList a, a)
forall a. Maybe a
Nothing
unsnoc (RList (a
x:[a]
xs)) = (RList a, a) -> Maybe (RList a, a)
forall a. a -> Maybe a
Just ([a] -> RList a
forall a. [a] -> RList a
RList [a]
xs, a
x)
singleton :: a -> RList a
{-# INLINE singleton #-}
singleton :: a -> RList a
singleton = [a] -> RList a
forall a. [a] -> RList a
RList ([a] -> RList a) -> (a -> [a]) -> a -> RList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> [a] -> [a]
forall a. a -> [a] -> [a]
:[])
null :: RList a -> Bool
{-# INLINE null #-}
null :: RList a -> Bool
null (RList [a]
xs) = [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
List.null [a]
xs
last :: RList a -> Maybe a
last :: RList a -> Maybe a
last RList a
Nil = Maybe a
forall a. Maybe a
Nothing
last (Snoc RList a
_ a
x) = a -> Maybe a
forall a. a -> Maybe a
Just a
x
init :: RList a -> Maybe (RList a)
init :: RList a -> Maybe (RList a)
init RList a
Nil = Maybe (RList a)
forall a. Maybe a
Nothing
init (Snoc RList a
xs a
_) = RList a -> Maybe (RList a)
forall a. a -> Maybe a
Just RList a
xs
catMaybes :: RList (Maybe a) -> RList a
{-# INLINE catMaybes #-}
catMaybes :: RList (Maybe a) -> RList a
catMaybes = [a] -> RList a
forall a. [a] -> RList a
RList ([a] -> RList a)
-> (RList (Maybe a) -> [a]) -> RList (Maybe a) -> RList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Maybe a] -> [a]
forall a. [Maybe a] -> [a]
Maybe.catMaybes ([Maybe a] -> [a])
-> (RList (Maybe a) -> [Maybe a]) -> RList (Maybe a) -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RList (Maybe a) -> [Maybe a]
forall a. RList a -> [a]
unRList
toList :: RList a -> [a]
{-# INLINE toList #-}
toList :: RList a -> [a]
toList (RList [a]
xs) = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse [a]
xs
fromList :: [a] -> RList a
{-# INLINE fromList #-}
fromList :: [a] -> RList a
fromList = [a] -> RList a
forall a. [a] -> RList a
RList ([a] -> RList a) -> ([a] -> [a]) -> [a] -> RList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse
reverseOut :: RList a -> [a]
{-# INLINE reverseOut #-}
reverseOut :: RList a -> [a]
reverseOut = RList a -> [a]
forall a. RList a -> [a]
unRList
reverseIn :: [a] -> RList a
{-# INLINE reverseIn #-}
reverseIn :: [a] -> RList a
reverseIn = [a] -> RList a
forall a. [a] -> RList a
RList
toArrayN :: (Contiguous arr, Element arr a) => Int -> RList a -> arr a
{-# INLINE toArrayN #-}
{-# SPECIALIZE toArrayN :: Int -> RList a -> SmallArray a #-}
toArrayN :: Int -> RList a -> arr a
toArrayN Int
n (RList [a]
xs0) = (forall s. ST s (Mutable arr s a)) -> arr a
forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
(forall s. ST s (Mutable arr s a)) -> arr a
Arr.create ((forall s. ST s (Mutable arr s a)) -> arr a)
-> (forall s. ST s (Mutable arr s a)) -> arr a
forall a b. (a -> b) -> a -> b
$ do
Mutable arr s a
mut <- Int -> ST s (Mutable arr (PrimState (ST s)) a)
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
Arr.new Int
n
Mutable arr (PrimState (ST s)) a -> Int -> [a] -> ST s ()
forall (arr :: * -> *) b (f :: * -> *).
(Element arr b, Contiguous arr, PrimMonad f) =>
Mutable arr (PrimState f) b -> Int -> [b] -> f ()
loop Mutable arr s a
Mutable arr (PrimState (ST s)) a
mut (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) [a]
xs0
Mutable arr s a -> ST s (Mutable arr s a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Mutable arr s a
mut
where
loop :: Mutable arr (PrimState f) b -> Int -> [b] -> f ()
loop Mutable arr (PrimState f) b
_ (-1) [b]
_ = () -> f ()
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
loop Mutable arr (PrimState f) b
_ Int
_ [] = () -> f ()
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
loop Mutable arr (PrimState f) b
arr Int
i (b
x:[b]
xs) = do
Mutable arr (PrimState f) b -> Int -> b -> f ()
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
Arr.write Mutable arr (PrimState f) b
arr Int
i b
x
Mutable arr (PrimState f) b -> Int -> [b] -> f ()
loop Mutable arr (PrimState f) b
arr (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) [b]
xs
toSet :: (Ord a) => RList a -> Set a
{-# INLINABLE toSet #-}
toSet :: RList a -> Set a
toSet (RList [a]
xs) = [a] -> Set a
forall a. Ord a => [a] -> Set a
Set.fromList [a]
xs