-- |
-- Module      : Foundation.List.DList
-- License     : BSD-style
-- Maintainer  : Nicolas Di Prima <nicolas@primetype.co.uk>
-- Stability   : statble
-- Portability : portable
--
-- Data structure for optimised operations (append, cons, snoc) on list
--
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