module Foundation.List.DList
( DList
) where
import Basement.Compat.Base
import Basement.Compat.Semigroup
import Basement.Compat.Bifunctor
import Foundation.Collection
newtype DList a = DList { forall a. DList a -> [a] -> [a]
unDList :: [a] -> [a] }
deriving (Typeable)
instance Eq a => Eq (DList a) where
== :: DList a -> DList a -> Bool
(==) DList a
dl1 DList a
dl2 = forall a. Eq a => a -> a -> Bool
(==) (forall l. IsList l => l -> [Item l]
toList DList a
dl1) (forall l. IsList l => l -> [Item l]
toList DList a
dl2)
instance Ord a => Ord (DList a) where
compare :: DList a -> DList a -> Ordering
compare DList a
dl1 DList a
dl2 = forall a. Ord a => a -> a -> Ordering
compare (forall l. IsList l => l -> [Item l]
toList DList a
dl1) (forall l. IsList l => l -> [Item l]
toList DList a
dl2)
instance Show a => Show (DList a) where
show :: DList 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 IsList (DList a) where
type Item (DList a) = a
fromList :: [Item (DList a)] -> DList a
fromList = forall a. ([a] -> [a]) -> DList a
DList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall a. Semigroup a => a -> a -> a
(Basement.Compat.Semigroup.<>)
toList :: DList a -> [Item (DList a)]
toList = forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a. DList a -> [a] -> [a]
unDList []
instance Semigroup (DList a) where
<> :: DList a -> DList a -> DList a
(<>) DList a
dl1 DList a
dl2 = forall a. ([a] -> [a]) -> DList a
DList forall a b. (a -> b) -> a -> b
$ forall a. DList a -> [a] -> [a]
unDList DList a
dl1 forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall a. DList a -> [a] -> [a]
unDList DList a
dl2
instance Monoid (DList a) where
mempty :: DList a
mempty = forall a. ([a] -> [a]) -> DList a
DList forall {k} (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id
instance Functor DList where
fmap :: forall a b. (a -> b) -> DList a -> DList b
fmap a -> b
f = forall collection a.
Foldable collection =>
(Element collection -> a -> a) -> a -> collection -> a
foldr (forall c. Sequential c => Element c -> c -> c
cons forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. a -> b
f) forall a. Monoid a => a
mempty
instance Applicative DList where
pure :: forall a. a -> DList a
pure = forall c. Sequential c => Element c -> c
singleton
<*> :: forall a b. DList (a -> b) -> DList a -> DList b
(<*>) DList (a -> b)
m1 DList a
m2 = DList (a -> b)
m1 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \a -> b
x1 -> DList a
m2 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \a
x2 -> forall (m :: * -> *) a. Monad m => a -> m a
return (a -> b
x1 a
x2)
instance Monad DList where
>>= :: forall a b. DList a -> (a -> DList b) -> DList b
(>>=) DList a
m a -> DList b
k = forall collection a.
Foldable collection =>
(Element collection -> a -> a) -> a -> collection -> a
foldr (forall a. Monoid a => a -> a -> a
mappend forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. a -> DList b
k) forall a. Monoid a => a
mempty DList a
m
return :: forall a. a -> DList a
return = forall (f :: * -> *) a. Applicative f => a -> f a
pure
type instance Element (DList a) = a
instance Foldable (DList a) where
foldr :: forall a. (Element (DList a) -> a -> a) -> a -> DList a -> a
foldr Element (DList a) -> a -> a
f a
b = forall collection a.
Foldable collection =>
(Element collection -> a -> a) -> a -> collection -> a
foldr Element (DList a) -> a -> a
f a
b 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
foldl' :: forall a. (a -> Element (DList a) -> a) -> a -> DList a -> a
foldl' a -> Element (DList a) -> a
f a
b = forall collection a.
Foldable collection =>
(a -> Element collection -> a) -> a -> collection -> a
foldl' a -> Element (DList a) -> a
f a
b 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 Collection (DList a) where
null :: DList a -> Bool
null = forall c. Collection c => c -> Bool
null 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
length :: DList a -> CountOf (Element (DList a))
length = forall c. Collection c => c -> CountOf (Element c)
length 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
elem :: forall a.
(Eq a, a ~ Element (DList a)) =>
Element (DList a) -> DList a -> Bool
elem Element (DList a)
a = forall c a.
(Collection c, Eq a, a ~ Element c) =>
Element c -> c -> Bool
elem Element (DList a)
a 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
maximum :: forall a.
(Ord a, a ~ Element (DList a)) =>
NonEmpty (DList a) -> Element (DList a)
maximum = forall c a.
(Collection c, Ord a, a ~ Element c) =>
NonEmpty c -> Element c
maximum forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Collection c => c -> NonEmpty c
nonEmpty_ 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
minimum :: forall a.
(Ord a, a ~ Element (DList a)) =>
NonEmpty (DList a) -> Element (DList a)
minimum = forall c a.
(Collection c, Ord a, a ~ Element c) =>
NonEmpty c -> Element c
minimum forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Collection c => c -> NonEmpty c
nonEmpty_ 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
all :: (Element (DList a) -> Bool) -> DList a -> Bool
all Element (DList a) -> Bool
f = forall c. Collection c => (Element c -> Bool) -> c -> Bool
all Element (DList a) -> Bool
f 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
any :: (Element (DList a) -> Bool) -> DList a -> Bool
any Element (DList a) -> Bool
f = forall c. Collection c => (Element c -> Bool) -> c -> Bool
any Element (DList a) -> Bool
f 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 Sequential (DList a) where
take :: CountOf (Element (DList a)) -> DList a -> DList a
take CountOf (Element (DList a))
n = forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => CountOf (Element c) -> c -> c
take CountOf (Element (DList a))
n 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
revTake :: CountOf (Element (DList a)) -> DList a -> DList a
revTake CountOf (Element (DList a))
n = forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => CountOf (Element c) -> c -> c
revTake CountOf (Element (DList a))
n 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
drop :: CountOf (Element (DList a)) -> DList a -> DList a
drop CountOf (Element (DList a))
n = forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => CountOf (Element c) -> c -> c
drop CountOf (Element (DList a))
n 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
revDrop :: CountOf (Element (DList a)) -> DList a -> DList a
revDrop CountOf (Element (DList a))
n = forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => CountOf (Element c) -> c -> c
revDrop CountOf (Element (DList a))
n 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
splitAt :: CountOf (Element (DList a)) -> DList a -> (DList a, DList a)
splitAt CountOf (Element (DList a))
n = forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap forall l. IsList l => [Item l] -> l
fromList forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => CountOf (Element c) -> c -> (c, c)
splitAt CountOf (Element (DList a))
n 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
splitOn :: (Element (DList a) -> Bool) -> DList a -> [DList a]
splitOn Element (DList a) -> Bool
f = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => (Element c -> Bool) -> c -> [c]
splitOn Element (DList a) -> Bool
f 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
break :: (Element (DList a) -> Bool) -> DList a -> (DList a, DList a)
break Element (DList a) -> Bool
f = forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap forall l. IsList l => [Item l] -> l
fromList forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => (Element c -> Bool) -> c -> (c, c)
break Element (DList a) -> Bool
f 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
breakEnd :: (Element (DList a) -> Bool) -> DList a -> (DList a, DList a)
breakEnd Element (DList a) -> Bool
f = forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap forall l. IsList l => [Item l] -> l
fromList forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => (Element c -> Bool) -> c -> (c, c)
breakEnd Element (DList a) -> Bool
f 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
breakElem :: Eq (Element (DList a)) =>
Element (DList a) -> DList a -> (DList a, DList a)
breakElem Element (DList a)
e = forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap forall l. IsList l => [Item l] -> l
fromList forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c.
(Sequential c, Eq (Element c)) =>
Element c -> c -> (c, c)
breakElem Element (DList a)
e 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
intersperse :: Element (DList a) -> DList a -> DList a
intersperse Element (DList a)
e = forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => Element c -> c -> c
intersperse Element (DList a)
e 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
intercalate :: Monoid (Item (DList a)) =>
Element (DList a) -> DList a -> Element (DList a)
intercalate Element (DList a)
e = forall c.
(Sequential c, Monoid (Item c)) =>
Element c -> c -> Element c
intercalate Element (DList a)
e 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
span :: (Element (DList a) -> Bool) -> DList a -> (DList a, DList a)
span Element (DList a) -> Bool
f = forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap forall l. IsList l => [Item l] -> l
fromList forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => (Element c -> Bool) -> c -> (c, c)
span Element (DList a) -> Bool
f 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
spanEnd :: (Element (DList a) -> Bool) -> DList a -> (DList a, DList a)
spanEnd Element (DList a) -> Bool
f = forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap forall l. IsList l => [Item l] -> l
fromList forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => (Element c -> Bool) -> c -> (c, c)
spanEnd Element (DList a) -> Bool
f 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
filter :: (Element (DList a) -> Bool) -> DList a -> DList a
filter Element (DList a) -> Bool
f = forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => (Element c -> Bool) -> c -> c
filter Element (DList a) -> Bool
f 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
partition :: (Element (DList a) -> Bool) -> DList a -> (DList a, DList a)
partition Element (DList a) -> Bool
f = forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap forall l. IsList l => [Item l] -> l
fromList forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => (Element c -> Bool) -> c -> (c, c)
partition Element (DList a) -> Bool
f 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
reverse :: DList a -> DList a
reverse = forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => c -> c
reverse 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
uncons :: DList a -> Maybe (Element (DList a), DList a)
uncons DList a
dl = forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second forall l. IsList l => [Item l] -> l
fromList forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall c. Sequential c => c -> Maybe (Element c, c)
uncons (forall l. IsList l => l -> [Item l]
toList DList a
dl)
unsnoc :: DList a -> Maybe (DList a, Element (DList a))
unsnoc DList a
dl = forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first forall l. IsList l => [Item l] -> l
fromList forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall c. Sequential c => c -> Maybe (c, Element c)
unsnoc (forall l. IsList l => l -> [Item l]
toList DList a
dl)
cons :: Element (DList a) -> DList a -> DList a
cons Element (DList a)
e DList a
dl = forall a. ([a] -> [a]) -> DList a
DList forall a b. (a -> b) -> a -> b
$ (:) Element (DList a)
e forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall a. DList a -> [a] -> [a]
unDList DList a
dl
snoc :: DList a -> Element (DList a) -> DList a
snoc DList a
dl Element (DList a)
e = forall a. ([a] -> [a]) -> DList a
DList forall a b. (a -> b) -> a -> b
$ forall a. DList a -> [a] -> [a]
unDList DList a
dl forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (:) Element (DList a)
e
find :: (Element (DList a) -> Bool) -> DList a -> Maybe (Element (DList a))
find Element (DList a) -> Bool
f = forall c.
Sequential c =>
(Element c -> Bool) -> c -> Maybe (Element c)
find Element (DList a) -> Bool
f 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
sortBy :: (Element (DList a) -> Element (DList a) -> Ordering)
-> DList a -> DList a
sortBy Element (DList a) -> Element (DList a) -> Ordering
comp = forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c.
Sequential c =>
(Element c -> Element c -> Ordering) -> c -> c
sortBy Element (DList a) -> Element (DList a) -> Ordering
comp 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
singleton :: Element (DList a) -> DList a
singleton = forall a. ([a] -> [a]) -> DList a
DList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (:)
replicate :: CountOf (Element (DList a)) -> Element (DList a) -> DList a
replicate CountOf (Element (DList a))
n Element (DList a)
e = forall l. IsList l => [Item l] -> l
fromList forall a b. (a -> b) -> a -> b
$ forall c. Sequential c => CountOf (Element c) -> Element c -> c
replicate CountOf (Element (DList a))
n Element (DList a)
e