module Acc.NeAcc.Def
( NeAcc (..),
foldM,
prependReverseList,
uncons,
unconsTo,
unsnoc,
unsnocTo,
appendEnumFromTo,
)
where
import Acc.Prelude hiding (foldM, unsnoc)
data NeAcc a
= Leaf a
| Branch !(NeAcc a) !(NeAcc a)
instance (Show a) => Show (NeAcc a) where
show :: NeAcc a -> String
show =
forall a. Show a => a -> String
show forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall l. IsList l => l -> [Item l]
toList
instance (NFData a) => NFData (NeAcc a) where
rnf :: NeAcc a -> ()
rnf = \case
Leaf a
a -> forall a. NFData a => a -> ()
rnf a
a
Branch NeAcc a
l NeAcc a
r -> seq :: forall a b. a -> b -> b
seq (forall a. NFData a => a -> ()
rnf NeAcc a
l) (forall a. NFData a => a -> ()
rnf NeAcc a
r)
instance NFData1 NeAcc where
liftRnf :: forall a. (a -> ()) -> NeAcc a -> ()
liftRnf a -> ()
rnfLeaf = NeAcc a -> ()
rnfTree
where
rnfTree :: NeAcc a -> ()
rnfTree = \case
Leaf a
a -> a -> ()
rnfLeaf a
a
Branch NeAcc a
l NeAcc a
r -> seq :: forall a b. a -> b -> b
seq (NeAcc a -> ()
rnfTree NeAcc a
l) (NeAcc a -> ()
rnfTree NeAcc a
r)
instance IsList (NeAcc a) where
type Item (NeAcc a) = a
{-# INLINE [0] fromList #-}
fromList :: [Item (NeAcc a)] -> NeAcc a
fromList [Item (NeAcc a)]
list =
case forall a. [a] -> [a]
reverse [Item (NeAcc a)]
list of
a
a : [a]
b -> forall a. [a] -> NeAcc a -> NeAcc a
prependReverseList [a]
b (forall a. a -> NeAcc a
Leaf a
a)
[a]
_ -> forall a. HasCallStack => String -> a
error String
"Empty input list"
{-# INLINE [0] toList #-}
toList :: NeAcc a -> [Item (NeAcc a)]
toList =
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) []
deriving instance Functor NeAcc
instance Applicative NeAcc where
pure :: forall a. a -> NeAcc a
pure =
forall a. a -> NeAcc a
Leaf
{-# INLINE [1] (<*>) #-}
<*> :: forall a b. NeAcc (a -> b) -> NeAcc a -> NeAcc b
(<*>) =
\case
Branch NeAcc (a -> b)
a NeAcc (a -> b)
b ->
\NeAcc a
c ->
forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch (NeAcc (a -> b)
a forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> NeAcc a
c) (NeAcc (a -> b)
b forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> NeAcc a
c)
Leaf a -> b
a ->
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
a
instance Foldable NeAcc where
{-# INLINEABLE [0] foldr #-}
foldr :: (a -> b -> b) -> b -> NeAcc a -> b
foldr :: forall a b. (a -> b -> b) -> b -> NeAcc a -> b
foldr a -> b -> b
step =
[NeAcc a] -> b -> NeAcc a -> b
go []
where
go :: [NeAcc a] -> b -> NeAcc a -> b
go [NeAcc a]
stack b
next = \case
Branch NeAcc a
l NeAcc a
r -> [NeAcc a] -> b -> NeAcc a -> b
go (NeAcc a
r forall a. a -> [a] -> [a]
: [NeAcc a]
stack) b
next NeAcc a
l
Leaf a
a -> a -> b -> b
step a
a forall a b. (a -> b) -> a -> b
$ case [NeAcc a]
stack of
NeAcc a
tree : [NeAcc a]
stack -> [NeAcc a] -> b -> NeAcc a -> b
go [NeAcc a]
stack b
next NeAcc a
tree
[] -> b
next
{-# INLINE [0] foldr' #-}
foldr' :: (a -> b -> b) -> b -> NeAcc a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> NeAcc a -> b
foldr' a -> b -> b
step =
[NeAcc a] -> b -> NeAcc a -> b
peel []
where
peel :: [NeAcc a] -> b -> NeAcc a -> b
peel [NeAcc a]
layers b
acc =
\case
Leaf a
a ->
b -> [NeAcc a] -> b
unpeel (a -> b -> b
step a
a b
acc) [NeAcc a]
layers
Branch NeAcc a
l NeAcc a
r ->
[NeAcc a] -> b -> NeAcc a -> b
peel (NeAcc a
l forall a. a -> [a] -> [a]
: [NeAcc a]
layers) b
acc NeAcc a
r
unpeel :: b -> [NeAcc a] -> b
unpeel !b
acc =
\case
NeAcc a
h : [NeAcc a]
t ->
[NeAcc a] -> b -> NeAcc a -> b
peel [NeAcc a]
t b
acc NeAcc a
h
[NeAcc a]
_ ->
b
acc
{-# INLINE [0] foldl #-}
foldl :: (b -> a -> b) -> b -> NeAcc a -> b
foldl :: forall b a. (b -> a -> b) -> b -> NeAcc a -> b
foldl b -> a -> b
step b
acc =
\case
Branch NeAcc a
a NeAcc a
b ->
forall b a. (b -> a -> b) -> b -> NeAcc a -> NeAcc a -> b
foldlOnBranch b -> a -> b
step b
acc NeAcc a
a NeAcc a
b
Leaf a
a ->
b -> a -> b
step b
acc a
a
where
foldlOnBranch :: (b -> a -> b) -> b -> NeAcc a -> NeAcc a -> b
foldlOnBranch :: forall b a. (b -> a -> b) -> b -> NeAcc a -> NeAcc a -> b
foldlOnBranch b -> a -> b
step b
acc NeAcc a
a NeAcc a
b =
case NeAcc a
b of
Leaf a
c ->
b -> a -> b
step (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl b -> a -> b
step b
acc NeAcc a
a) a
c
Branch NeAcc a
c NeAcc a
d ->
forall b a. (b -> a -> b) -> b -> NeAcc a -> NeAcc a -> b
foldlOnBranch b -> a -> b
step b
acc (forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch NeAcc a
a NeAcc a
c) NeAcc a
d
{-# INLINE [0] foldl' #-}
foldl' :: (b -> a -> b) -> b -> NeAcc a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> NeAcc a -> b
foldl' b -> a -> b
step = [NeAcc a] -> b -> NeAcc a -> b
build []
where
build :: [NeAcc a] -> b -> NeAcc a -> b
build [NeAcc a]
stack !b
acc = \case
Branch NeAcc a
l NeAcc a
r -> [NeAcc a] -> b -> NeAcc a -> b
build (NeAcc a
r forall a. a -> [a] -> [a]
: [NeAcc a]
stack) b
acc NeAcc a
l
Leaf a
leaf -> case [NeAcc a]
stack of
NeAcc a
tree : [NeAcc a]
stack -> [NeAcc a] -> b -> NeAcc a -> b
build [NeAcc a]
stack (b -> a -> b
step b
acc a
leaf) NeAcc a
tree
[NeAcc a]
_ -> b -> a -> b
step b
acc a
leaf
{-# INLINE [0] foldMap #-}
foldMap :: (Monoid m) => (a -> m) -> NeAcc a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> NeAcc a -> m
foldMap a -> m
map =
NeAcc a -> m
peel
where
peel :: NeAcc a -> m
peel =
\case
Branch NeAcc a
a NeAcc a
b ->
NeAcc a -> NeAcc a -> m
peelLeftStacking NeAcc a
b NeAcc a
a
Leaf a
a ->
a -> m
map a
a
peelLeftStacking :: NeAcc a -> NeAcc a -> m
peelLeftStacking NeAcc a
buff =
\case
Branch NeAcc a
a NeAcc a
b ->
NeAcc a -> NeAcc a -> m
peelLeftStacking (forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch NeAcc a
b NeAcc a
buff) NeAcc a
a
Leaf a
a ->
a -> m
map a
a forall a. Semigroup a => a -> a -> a
<> NeAcc a -> m
peel NeAcc a
buff
{-# INLINE [0] foldMap' #-}
foldMap' :: (Monoid m) => (a -> m) -> NeAcc a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> NeAcc a -> m
foldMap' =
forall m a. Monoid m => m -> (a -> m) -> NeAcc a -> m
foldMapTo' forall a. Monoid a => a
mempty
where
foldMapTo' :: (Monoid m) => m -> (a -> m) -> NeAcc a -> m
foldMapTo' :: forall m a. Monoid m => m -> (a -> m) -> NeAcc a -> m
foldMapTo' !m
acc a -> m
map =
\case
Branch NeAcc a
a NeAcc a
b -> forall m a. Monoid m => m -> (a -> m) -> NeAcc a -> NeAcc a -> m
foldMapToOnBranch' m
acc a -> m
map NeAcc a
a NeAcc a
b
Leaf a
a -> m
acc forall a. Semigroup a => a -> a -> a
<> a -> m
map a
a
foldMapToOnBranch' :: (Monoid m) => m -> (a -> m) -> NeAcc a -> NeAcc a -> m
foldMapToOnBranch' :: forall m a. Monoid m => m -> (a -> m) -> NeAcc a -> NeAcc a -> m
foldMapToOnBranch' m
acc a -> m
map NeAcc a
a NeAcc a
b =
case NeAcc a
a of
Leaf a
c -> forall m a. Monoid m => m -> (a -> m) -> NeAcc a -> m
foldMapTo' (m
acc forall a. Semigroup a => a -> a -> a
<> a -> m
map a
c) a -> m
map NeAcc a
b
Branch NeAcc a
c NeAcc a
d -> forall m a. Monoid m => m -> (a -> m) -> NeAcc a -> NeAcc a -> m
foldMapToOnBranch' m
acc a -> m
map NeAcc a
c (forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch NeAcc a
d NeAcc a
b)
instance Traversable NeAcc where
{-# INLINE [0] traverse #-}
traverse :: (Applicative f) => (a -> f b) -> NeAcc a -> f (NeAcc b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NeAcc a -> f (NeAcc b)
traverse a -> f b
map =
\case
Branch NeAcc a
a NeAcc a
b ->
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NeAcc a -> NeAcc a -> f (NeAcc b)
traverseOnBranch a -> f b
map NeAcc a
a NeAcc a
b
Leaf a
a ->
forall a. a -> NeAcc a
Leaf forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
map a
a
where
traverseOnBranch :: (Applicative f) => (a -> f b) -> NeAcc a -> NeAcc a -> f (NeAcc b)
traverseOnBranch :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NeAcc a -> NeAcc a -> f (NeAcc b)
traverseOnBranch a -> f b
map NeAcc a
a NeAcc a
b =
case NeAcc a
a of
Leaf a
c ->
forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall a. a -> NeAcc a
Leaf forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
map a
c forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
map NeAcc a
b
Branch NeAcc a
c NeAcc a
d ->
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NeAcc a -> NeAcc a -> f (NeAcc b)
traverseOnBranch a -> f b
map NeAcc a
a (forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch NeAcc a
d NeAcc a
b)
instance Foldable1 NeAcc where
{-# INLINE [0] fold1 #-}
fold1 :: (Semigroup m) => NeAcc m -> m
fold1 :: forall m. Semigroup m => NeAcc m -> m
fold1 =
\case
Branch NeAcc m
l NeAcc m
r ->
forall a b. NeAcc a -> NeAcc a -> (a -> NeAcc a -> b) -> b
rebalancingLeft NeAcc m
l NeAcc m
r (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall a. Semigroup a => a -> a -> a
(<>))
Leaf m
a ->
m
a
{-# INLINE [0] foldMap1 #-}
foldMap1 :: (Semigroup m) => (a -> m) -> NeAcc a -> m
foldMap1 :: forall m a. Semigroup m => (a -> m) -> NeAcc a -> m
foldMap1 a -> m
f =
\case
Branch NeAcc a
l NeAcc a
r ->
forall a b. NeAcc a -> NeAcc a -> (a -> NeAcc a -> b) -> b
rebalancingLeft NeAcc a
l NeAcc a
r (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\m
m a
a -> m
m forall a. Semigroup a => a -> a -> a
<> a -> m
f a
a) forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. a -> m
f)
Leaf a
a ->
a -> m
f a
a
{-# INLINE [0] toNonEmpty #-}
toNonEmpty :: NeAcc a -> NonEmpty a
toNonEmpty :: forall a. NeAcc a -> NonEmpty a
toNonEmpty =
forall a. NeAcc a -> NonEmpty a
findFirst
where
findFirst :: NeAcc a -> NonEmpty a
findFirst =
\case
Branch NeAcc a
l NeAcc a
r ->
forall {a}. NeAcc a -> NeAcc a -> NonEmpty a
findFirstOnBranch NeAcc a
l NeAcc a
r
Leaf a
a ->
a
a forall a. a -> [a] -> NonEmpty a
:| []
findFirstOnBranch :: NeAcc a -> NeAcc a -> NonEmpty a
findFirstOnBranch NeAcc a
l NeAcc a
r =
case NeAcc a
l of
Branch NeAcc a
ll NeAcc a
lr ->
NeAcc a -> NeAcc a -> NonEmpty a
findFirstOnBranch NeAcc a
ll (forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch NeAcc a
lr NeAcc a
r)
Leaf a
a ->
a
a forall a. a -> [a] -> NonEmpty a
:| forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) [] NeAcc a
r
instance Traversable1 NeAcc where
{-# INLINE [0] traverse1 #-}
traverse1 :: forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> NeAcc a -> f (NeAcc b)
traverse1 a -> f b
map =
\case
Branch NeAcc a
a NeAcc a
b ->
forall {f :: * -> *} {a} {b}.
Apply f =>
(a -> f b) -> NeAcc a -> NeAcc a -> f (NeAcc b)
traverseOnBranch a -> f b
map NeAcc a
a NeAcc a
b
Leaf a
a ->
forall a. a -> NeAcc a
Leaf forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
map a
a
where
traverseOnBranch :: (a -> f b) -> NeAcc a -> NeAcc a -> f (NeAcc b)
traverseOnBranch a -> f b
map NeAcc a
a NeAcc a
b =
case NeAcc a
a of
Leaf a
c ->
forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall a. a -> NeAcc a
Leaf forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
map a
c forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
traverse1 a -> f b
map NeAcc a
b
Branch NeAcc a
c NeAcc a
d ->
(a -> f b) -> NeAcc a -> NeAcc a -> f (NeAcc b)
traverseOnBranch a -> f b
map NeAcc a
a (forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch NeAcc a
d NeAcc a
b)
instance Alt NeAcc where
{-# INLINE [1] (<!>) #-}
<!> :: forall a. NeAcc a -> NeAcc a -> NeAcc a
(<!>) =
forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch
instance Semigroup (NeAcc a) where
{-# INLINE [1] (<>) #-}
<> :: NeAcc a -> NeAcc a -> NeAcc a
(<>) =
forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch
{-# INLINE rebalancingLeft #-}
rebalancingLeft :: NeAcc a -> NeAcc a -> (a -> NeAcc a -> b) -> b
rebalancingLeft :: forall a b. NeAcc a -> NeAcc a -> (a -> NeAcc a -> b) -> b
rebalancingLeft NeAcc a
l NeAcc a
r a -> NeAcc a -> b
cont =
case NeAcc a
l of
Branch NeAcc a
ll NeAcc a
lr ->
forall a b. NeAcc a -> NeAcc a -> (a -> NeAcc a -> b) -> b
rebalancingLeft NeAcc a
ll (forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch NeAcc a
lr NeAcc a
r) a -> NeAcc a -> b
cont
Leaf a
a ->
a -> NeAcc a -> b
cont a
a NeAcc a
r
foldM :: (Monad m) => (a -> b -> m a) -> a -> NeAcc b -> m a
foldM :: forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> NeAcc b -> m a
foldM a -> b -> m a
step !a
acc =
\case
Branch NeAcc b
a NeAcc b
b -> forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> NeAcc b -> NeAcc b -> m a
foldMOnBranch a -> b -> m a
step a
acc NeAcc b
a NeAcc b
b
Leaf b
a -> a -> b -> m a
step a
acc b
a
where
foldMOnBranch :: (Monad m) => (a -> b -> m a) -> a -> NeAcc b -> NeAcc b -> m a
foldMOnBranch :: forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> NeAcc b -> NeAcc b -> m a
foldMOnBranch a -> b -> m a
step a
acc NeAcc b
a NeAcc b
b =
case NeAcc b
a of
Leaf b
c -> a -> b -> m a
step a
acc b
c forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \a
acc' -> forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> NeAcc b -> m a
foldM a -> b -> m a
step a
acc' NeAcc b
b
Branch NeAcc b
c NeAcc b
d -> forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> NeAcc b -> NeAcc b -> m a
foldMOnBranch a -> b -> m a
step a
acc NeAcc b
c (forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch NeAcc b
d NeAcc b
b)
prependReverseList :: [a] -> NeAcc a -> NeAcc a
prependReverseList :: forall a. [a] -> NeAcc a -> NeAcc a
prependReverseList [a]
list NeAcc a
tree =
case [a]
list of
a
head : [a]
tail -> forall a. [a] -> NeAcc a -> NeAcc a
prependReverseList [a]
tail (forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch (forall a. a -> NeAcc a
Leaf a
head) NeAcc a
tree)
[a]
_ -> NeAcc a
tree
{-# INLINE uncons #-}
uncons :: NeAcc a -> (a, Maybe (NeAcc a))
uncons :: forall a. NeAcc a -> (a, Maybe (NeAcc a))
uncons =
\case
Branch NeAcc a
l NeAcc a
r ->
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Maybe a
Just (forall a. NeAcc a -> NeAcc a -> (a, NeAcc a)
unconsTo NeAcc a
r NeAcc a
l)
Leaf a
a ->
(a
a, forall a. Maybe a
Nothing)
{-# INLINE unconsTo #-}
unconsTo :: NeAcc a -> NeAcc a -> (a, NeAcc a)
unconsTo :: forall a. NeAcc a -> NeAcc a -> (a, NeAcc a)
unconsTo NeAcc a
buff =
\case
Branch NeAcc a
l NeAcc a
r ->
forall a. NeAcc a -> NeAcc a -> (a, NeAcc a)
unconsTo (forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch NeAcc a
r NeAcc a
buff) NeAcc a
l
Leaf a
a ->
(a
a, NeAcc a
buff)
unsnoc :: NeAcc a -> (a, Maybe (NeAcc a))
unsnoc :: forall a. NeAcc a -> (a, Maybe (NeAcc a))
unsnoc =
\case
Branch NeAcc a
l NeAcc a
r ->
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Maybe a
Just (forall a. NeAcc a -> NeAcc a -> (a, NeAcc a)
unsnocTo NeAcc a
l NeAcc a
r)
Leaf a
a ->
(a
a, forall a. Maybe a
Nothing)
unsnocTo :: NeAcc a -> NeAcc a -> (a, NeAcc a)
unsnocTo :: forall a. NeAcc a -> NeAcc a -> (a, NeAcc a)
unsnocTo NeAcc a
buff =
\case
Branch NeAcc a
l NeAcc a
r ->
forall a. NeAcc a -> NeAcc a -> (a, NeAcc a)
unsnocTo (forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch NeAcc a
buff NeAcc a
l) NeAcc a
r
Leaf a
a ->
(a
a, NeAcc a
buff)
appendEnumFromTo :: (Enum a, Ord a) => a -> a -> NeAcc a -> NeAcc a
appendEnumFromTo :: forall a. (Enum a, Ord a) => a -> a -> NeAcc a -> NeAcc a
appendEnumFromTo a
from a
to =
if a
from forall a. Ord a => a -> a -> Bool
<= a
to
then forall a. (Enum a, Ord a) => a -> a -> NeAcc a -> NeAcc a
appendEnumFromTo (forall a. Enum a => a -> a
succ a
from) a
to forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a. NeAcc a -> NeAcc a -> NeAcc a
Branch (forall a. a -> NeAcc a
Leaf a
from)
else forall {k} (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id