module Acc
( Acc,
fromReverseList,
cons,
snoc,
uncons,
toNonEmpty,
toNeAcc,
enumFromTo,
)
where
import qualified Acc.NeAcc as NeAcc
import qualified Acc.NeAcc.Def as NeAcc
import Acc.Prelude hiding (enumFromTo, toNonEmpty)
import qualified Data.Foldable as Foldable
import qualified Data.Semigroup.Foldable as Foldable1
data Acc a
= EmptyAcc
| TreeAcc !(NeAcc.NeAcc a)
instance NFData a => NFData (Acc a) where
rnf :: Acc a -> ()
rnf = \case
TreeAcc NeAcc a
tree -> NeAcc a -> ()
forall a. NFData a => a -> ()
rnf NeAcc a
tree
Acc a
EmptyAcc -> ()
instance NFData1 Acc where
liftRnf :: (a -> ()) -> Acc a -> ()
liftRnf a -> ()
rnfLeaf = \case
TreeAcc NeAcc a
tree -> (a -> ()) -> NeAcc a -> ()
forall (f :: * -> *) a. NFData1 f => (a -> ()) -> f a -> ()
liftRnf a -> ()
rnfLeaf NeAcc a
tree
Acc a
EmptyAcc -> ()
deriving instance Functor Acc
instance Foldable Acc where
{-# INLINE [0] foldMap #-}
foldMap :: (a -> m) -> Acc a -> m
foldMap a -> m
f =
\case
TreeAcc NeAcc a
a ->
(a -> m) -> NeAcc a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f NeAcc a
a
Acc a
EmptyAcc ->
m
forall a. Monoid a => a
mempty
{-# INLINE [0] foldMap' #-}
foldMap' :: (a -> m) -> Acc a -> m
foldMap' a -> m
f =
\case
TreeAcc NeAcc a
a ->
(a -> m) -> NeAcc a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap' a -> m
f NeAcc a
a
Acc a
EmptyAcc ->
m
forall a. Monoid a => a
mempty
{-# INLINE [0] foldr #-}
foldr :: (a -> b -> b) -> b -> Acc a -> b
foldr a -> b -> b
step b
acc =
\case
TreeAcc NeAcc a
a ->
(a -> b -> b) -> b -> NeAcc a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
step b
acc NeAcc a
a
Acc a
EmptyAcc ->
b
acc
{-# INLINE [0] foldr' #-}
foldr' :: (a -> b -> b) -> b -> Acc a -> b
foldr' a -> b -> b
step b
acc =
\case
TreeAcc NeAcc a
a ->
(a -> b -> b) -> b -> NeAcc a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' a -> b -> b
step b
acc NeAcc a
a
Acc a
EmptyAcc ->
b
acc
{-# INLINE [0] foldl #-}
foldl :: (b -> a -> b) -> b -> Acc a -> b
foldl b -> a -> b
step b
acc =
\case
TreeAcc NeAcc a
a ->
(b -> a -> b) -> b -> NeAcc a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl b -> a -> b
step b
acc NeAcc a
a
Acc a
EmptyAcc ->
b
acc
{-# INLINE [0] foldl' #-}
foldl' :: (b -> a -> b) -> b -> Acc a -> b
foldl' b -> a -> b
step b
acc =
\case
TreeAcc NeAcc a
a ->
(b -> a -> b) -> b -> NeAcc a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
step b
acc NeAcc a
a
Acc a
EmptyAcc ->
b
acc
{-# INLINE [0] sum #-}
sum :: Acc a -> a
sum =
(a -> a -> a) -> a -> Acc a -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' a -> a -> a
forall a. Num a => a -> a -> a
(+) a
0
instance Traversable Acc where
{-# INLINE [0] traverse #-}
traverse :: (a -> f b) -> Acc a -> f (Acc b)
traverse a -> f b
f =
\case
TreeAcc NeAcc a
a ->
NeAcc b -> Acc b
forall a. NeAcc a -> Acc a
TreeAcc (NeAcc b -> Acc b) -> f (NeAcc b) -> f (Acc b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> NeAcc a -> f (NeAcc b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f NeAcc a
a
Acc a
EmptyAcc ->
Acc b -> f (Acc b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Acc b
forall a. Acc a
EmptyAcc
instance Applicative Acc where
{-# INLINE [1] pure #-}
pure :: a -> Acc a
pure =
NeAcc a -> Acc a
forall a. NeAcc a -> Acc a
TreeAcc (NeAcc a -> Acc a) -> (a -> NeAcc a) -> a -> Acc a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. a -> NeAcc a
forall a. a -> NeAcc a
NeAcc.Leaf
{-# INLINE [1] (<*>) #-}
<*> :: Acc (a -> b) -> Acc a -> Acc b
(<*>) =
\case
TreeAcc NeAcc (a -> b)
a ->
\case
TreeAcc NeAcc a
b ->
NeAcc b -> Acc b
forall a. NeAcc a -> Acc a
TreeAcc (NeAcc (a -> b)
a NeAcc (a -> b) -> NeAcc a -> NeAcc b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> NeAcc a
b)
Acc a
EmptyAcc ->
Acc b
forall a. Acc a
EmptyAcc
Acc (a -> b)
EmptyAcc ->
Acc b -> Acc a -> Acc b
forall a b. a -> b -> a
const Acc b
forall a. Acc a
EmptyAcc
instance Alternative Acc where
{-# INLINE [1] empty #-}
empty :: Acc a
empty =
Acc a
forall a. Acc a
EmptyAcc
{-# INLINE [1] (<|>) #-}
<|> :: Acc a -> Acc a -> Acc a
(<|>) =
\case
TreeAcc NeAcc a
a ->
\case
TreeAcc NeAcc a
b ->
NeAcc a -> Acc a
forall a. NeAcc a -> Acc a
TreeAcc (NeAcc a -> NeAcc a -> NeAcc a
forall a. NeAcc a -> NeAcc a -> NeAcc a
NeAcc.Branch NeAcc a
a NeAcc a
b)
Acc a
EmptyAcc ->
NeAcc a -> Acc a
forall a. NeAcc a -> Acc a
TreeAcc NeAcc a
a
Acc a
EmptyAcc ->
Acc a -> Acc a
forall k (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id
instance Semigroup (Acc a) where
{-# INLINE [1] (<>) #-}
<> :: Acc a -> Acc a -> Acc a
(<>) =
Acc a -> Acc a -> Acc a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>)
instance Monoid (Acc a) where
{-# INLINE [1] mempty #-}
mempty :: Acc a
mempty =
Acc a
forall (f :: * -> *) a. Alternative f => f a
empty
instance IsList (Acc a) where
type Item (Acc a) = a
{-# INLINE [0] fromList #-}
fromList :: [Item (Acc a)] -> Acc a
fromList = [a] -> Acc a
forall a. [a] -> Acc a
fromReverseList ([a] -> Acc a) -> ([a] -> [a]) -> [a] -> Acc a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. [a] -> [a]
forall a. [a] -> [a]
reverse
{-# INLINE [0] toList #-}
toList :: Acc a -> [Item (Acc a)]
toList =
\case
TreeAcc NeAcc a
a ->
(a -> [a] -> [a]) -> [a] -> NeAcc a -> [a]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [] NeAcc a
a
Acc a
_ ->
[]
instance Show a => Show (Acc a) where
show :: Acc a -> String
show =
[a] -> String
forall a. Show a => a -> String
show ([a] -> String) -> (Acc a -> [a]) -> Acc a -> String
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Acc a -> [a]
forall l. IsList l => l -> [Item l]
toList
{-# INLINE [1] cons #-}
cons :: a -> Acc a -> Acc a
cons :: a -> Acc a -> Acc a
cons a
a =
\case
TreeAcc NeAcc a
tree ->
NeAcc a -> Acc a
forall a. NeAcc a -> Acc a
TreeAcc (NeAcc a -> NeAcc a -> NeAcc a
forall a. NeAcc a -> NeAcc a -> NeAcc a
NeAcc.Branch (a -> NeAcc a
forall a. a -> NeAcc a
NeAcc.Leaf a
a) NeAcc a
tree)
Acc a
EmptyAcc ->
NeAcc a -> Acc a
forall a. NeAcc a -> Acc a
TreeAcc (a -> NeAcc a
forall a. a -> NeAcc a
NeAcc.Leaf a
a)
{-# INLINE uncons #-}
uncons :: Acc a -> Maybe (a, Acc a)
uncons :: Acc a -> Maybe (a, Acc a)
uncons =
\case
TreeAcc NeAcc a
tree ->
case NeAcc a
tree of
NeAcc.Branch NeAcc a
l NeAcc a
r ->
case NeAcc a -> NeAcc a -> (a, NeAcc a)
forall a. NeAcc a -> NeAcc a -> (a, NeAcc a)
NeAcc.unconsTo NeAcc a
r NeAcc a
l of
(a
res, NeAcc a
newTree) ->
(a, Acc a) -> Maybe (a, Acc a)
forall a. a -> Maybe a
Just (a
res, NeAcc a -> Acc a
forall a. NeAcc a -> Acc a
TreeAcc NeAcc a
newTree)
NeAcc.Leaf a
res ->
(a, Acc a) -> Maybe (a, Acc a)
forall a. a -> Maybe a
Just (a
res, Acc a
forall a. Acc a
EmptyAcc)
Acc a
EmptyAcc ->
Maybe (a, Acc a)
forall a. Maybe a
Nothing
{-# INLINE [1] snoc #-}
snoc :: a -> Acc a -> Acc a
snoc :: a -> Acc a -> Acc a
snoc a
a =
\case
TreeAcc NeAcc a
tree ->
NeAcc a -> Acc a
forall a. NeAcc a -> Acc a
TreeAcc (NeAcc a -> NeAcc a -> NeAcc a
forall a. NeAcc a -> NeAcc a -> NeAcc a
NeAcc.Branch NeAcc a
tree (a -> NeAcc a
forall a. a -> NeAcc a
NeAcc.Leaf a
a))
Acc a
EmptyAcc ->
NeAcc a -> Acc a
forall a. NeAcc a -> Acc a
TreeAcc (a -> NeAcc a
forall a. a -> NeAcc a
NeAcc.Leaf a
a)
{-# INLINE unsnoc #-}
unsnoc :: Acc a -> Maybe (a, Acc a)
unsnoc :: Acc a -> Maybe (a, Acc a)
unsnoc =
\case
TreeAcc NeAcc a
tree ->
case NeAcc a
tree of
NeAcc.Branch NeAcc a
l NeAcc a
r ->
case NeAcc a -> NeAcc a -> (a, NeAcc a)
forall a. NeAcc a -> NeAcc a -> (a, NeAcc a)
NeAcc.unsnocTo NeAcc a
l NeAcc a
r of
(a
res, NeAcc a
newTree) ->
(a, Acc a) -> Maybe (a, Acc a)
forall a. a -> Maybe a
Just (a
res, NeAcc a -> Acc a
forall a. NeAcc a -> Acc a
TreeAcc NeAcc a
newTree)
NeAcc.Leaf a
res ->
(a, Acc a) -> Maybe (a, Acc a)
forall a. a -> Maybe a
Just (a
res, Acc a
forall a. Acc a
EmptyAcc)
Acc a
EmptyAcc ->
Maybe (a, Acc a)
forall a. Maybe a
Nothing
{-# INLINE toNonEmpty #-}
toNonEmpty :: Acc a -> Maybe (NonEmpty a)
toNonEmpty :: Acc a -> Maybe (NonEmpty a)
toNonEmpty =
(NeAcc a -> NonEmpty a) -> Maybe (NeAcc a) -> Maybe (NonEmpty a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap NeAcc a -> NonEmpty a
forall (t :: * -> *) a. Foldable1 t => t a -> NonEmpty a
Foldable1.toNonEmpty (Maybe (NeAcc a) -> Maybe (NonEmpty a))
-> (Acc a -> Maybe (NeAcc a)) -> Acc a -> Maybe (NonEmpty a)
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Acc a -> Maybe (NeAcc a)
forall a. Acc a -> Maybe (NeAcc a)
toNeAcc
{-# INLINE toNeAcc #-}
toNeAcc :: Acc a -> Maybe (NeAcc.NeAcc a)
toNeAcc :: Acc a -> Maybe (NeAcc a)
toNeAcc =
\case
TreeAcc NeAcc a
tree ->
NeAcc a -> Maybe (NeAcc a)
forall a. a -> Maybe a
Just NeAcc a
tree
Acc a
EmptyAcc ->
Maybe (NeAcc a)
forall a. Maybe a
Nothing
{-# INLINE [1] enumFromTo #-}
enumFromTo :: (Enum a, Ord a) => a -> a -> Acc a
enumFromTo :: a -> a -> Acc a
enumFromTo a
from a
to =
if a
from a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
to
then NeAcc a -> Acc a
forall a. NeAcc a -> Acc a
TreeAcc (a -> a -> NeAcc a -> NeAcc a
forall a. (Enum a, Ord a) => a -> a -> NeAcc a -> NeAcc a
NeAcc.appendEnumFromTo (a -> a
forall a. Enum a => a -> a
succ a
from) a
to (a -> NeAcc a
forall a. a -> NeAcc a
NeAcc.Leaf a
from))
else Acc a
forall a. Acc a
EmptyAcc
{-# INLINE fromReverseList #-}
fromReverseList :: [a] -> Acc a
fromReverseList :: [a] -> Acc a
fromReverseList = \case
a
a : [a]
b -> NeAcc a -> Acc a
forall a. NeAcc a -> Acc a
TreeAcc ([a] -> NeAcc a -> NeAcc a
forall a. [a] -> NeAcc a -> NeAcc a
NeAcc.prependReverseList [a]
b (a -> NeAcc a
forall a. a -> NeAcc a
NeAcc.Leaf a
a))
[a]
_ -> Acc a
forall a. Acc a
EmptyAcc