-- |
-- 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 { 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 = [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
(==) (DList a -> [Item (DList a)]
forall l. IsList l => l -> [Item l]
toList DList a
dl1) (DList a -> [Item (DList a)]
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 = [a] -> [a] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (DList a -> [Item (DList a)]
forall l. IsList l => l -> [Item l]
toList DList a
dl1) (DList a -> [Item (DList a)]
forall l. IsList l => l -> [Item l]
toList DList a
dl2)

instance Show a => Show (DList a) where
    show :: DList a -> String
show = [a] -> String
forall a. Show a => a -> String
show ([a] -> String) -> (DList a -> [a]) -> DList a -> String
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
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 = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DList (([a] -> [a]) -> DList a) -> ([a] -> [a] -> [a]) -> [a] -> DList 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] -> [a]
forall a. Semigroup a => a -> a -> a
(Basement.Compat.Semigroup.<>)
    toList :: DList a -> [Item (DList a)]
toList = (DList a -> [a] -> [a]) -> [a] -> DList a -> [a]
forall a b c. (a -> b -> c) -> b -> a -> c
flip DList a -> [a] -> [a]
forall a. DList a -> [a] -> [a]
unDList []

instance Semigroup (DList a) where
    <> :: DList a -> DList a -> DList a
(<>) DList a
dl1 DList a
dl2 = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DList (([a] -> [a]) -> DList a) -> ([a] -> [a]) -> DList a
forall a b. (a -> b) -> a -> b
$ DList a -> [a] -> [a]
forall a. DList a -> [a] -> [a]
unDList DList a
dl1 ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a] -> [a]
forall a. DList a -> [a] -> [a]
unDList DList a
dl2
instance Monoid (DList a) where
    mempty :: DList a
mempty = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DList [a] -> [a]
forall k (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id

instance Functor DList where
    fmap :: (a -> b) -> DList a -> DList b
fmap a -> b
f = (Element (DList a) -> DList b -> DList b)
-> DList b -> DList a -> DList b
forall collection a.
Foldable collection =>
(Element collection -> a -> a) -> a -> collection -> a
foldr (b -> DList b -> DList b
forall c. Sequential c => Element c -> c -> c
cons (b -> DList b -> DList b) -> (a -> b) -> a -> DList b -> DList b
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) DList b
forall a. Monoid a => a
mempty

instance Applicative DList where
    pure :: a -> DList a
pure = a -> DList a
forall c. Sequential c => Element c -> c
singleton
    <*> :: DList (a -> b) -> DList a -> DList b
(<*>) DList (a -> b)
m1 DList a
m2 = DList (a -> b)
m1 DList (a -> b) -> ((a -> b) -> DList b) -> DList b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \a -> b
x1 -> DList a
m2 DList a -> (a -> DList b) -> DList b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \a
x2 -> b -> DList b
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> b
x1 a
x2)

instance Monad DList where
    >>= :: DList a -> (a -> DList b) -> DList b
(>>=) DList a
m a -> DList b
k = (Element (DList a) -> DList b -> DList b)
-> DList b -> DList a -> DList b
forall collection a.
Foldable collection =>
(Element collection -> a -> a) -> a -> collection -> a
foldr (DList b -> DList b -> DList b
forall a. Monoid a => a -> a -> a
mappend (DList b -> DList b -> DList b)
-> (a -> DList b) -> a -> DList b -> DList b
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) DList b
forall a. Monoid a => a
mempty DList a
m
    return :: a -> DList a
return = a -> DList a
forall (f :: * -> *) a. Applicative f => a -> f a
pure

type instance Element (DList a) = a

instance Foldable (DList a) where
    foldr :: (Element (DList a) -> a -> a) -> a -> DList a -> a
foldr Element (DList a) -> a -> a
f a
b = (Element [a] -> a -> a) -> a -> [a] -> a
forall collection a.
Foldable collection =>
(Element collection -> a -> a) -> a -> collection -> a
foldr Element [a] -> a -> a
Element (DList a) -> a -> a
f a
b ([a] -> a) -> (DList a -> [a]) -> 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
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    foldl' :: (a -> Element (DList a) -> a) -> a -> DList a -> a
foldl' a -> Element (DList a) -> a
f a
b = (a -> Element [a] -> a) -> a -> [a] -> a
forall collection a.
Foldable collection =>
(a -> Element collection -> a) -> a -> collection -> a
foldl' a -> Element [a] -> a
a -> Element (DList a) -> a
f a
b ([a] -> a) -> (DList a -> [a]) -> 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
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList

instance Collection (DList a) where
    null :: DList a -> Bool
null = [a] -> Bool
forall c. Collection c => c -> Bool
null ([a] -> Bool) -> (DList a -> [a]) -> DList a -> Bool
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    length :: DList a -> CountOf (Element (DList a))
length = [a] -> CountOf a
forall c. Collection c => c -> CountOf (Element c)
length ([a] -> CountOf a) -> (DList a -> [a]) -> DList a -> CountOf a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    elem :: Element (DList a) -> DList a -> Bool
elem Element (DList a)
a = Element [a] -> [a] -> Bool
forall c a.
(Collection c, Eq a, a ~ Element c) =>
Element c -> c -> Bool
elem Element [a]
Element (DList a)
a ([a] -> Bool) -> (DList a -> [a]) -> DList a -> Bool
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    maximum :: NonEmpty (DList a) -> Element (DList a)
maximum = NonEmpty [a] -> a
forall c a.
(Collection c, Ord a, a ~ Element c) =>
NonEmpty c -> Element c
maximum (NonEmpty [a] -> a)
-> (NonEmpty (DList a) -> NonEmpty [a]) -> NonEmpty (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
. [a] -> NonEmpty [a]
forall c. Collection c => c -> NonEmpty c
nonEmpty_ ([a] -> NonEmpty [a])
-> (NonEmpty (DList a) -> [a])
-> NonEmpty (DList a)
-> NonEmpty [a]
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. NonEmpty (DList a) -> [a]
forall l. IsList l => l -> [Item l]
toList
    minimum :: NonEmpty (DList a) -> Element (DList a)
minimum = NonEmpty [a] -> a
forall c a.
(Collection c, Ord a, a ~ Element c) =>
NonEmpty c -> Element c
minimum (NonEmpty [a] -> a)
-> (NonEmpty (DList a) -> NonEmpty [a]) -> NonEmpty (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
. [a] -> NonEmpty [a]
forall c. Collection c => c -> NonEmpty c
nonEmpty_ ([a] -> NonEmpty [a])
-> (NonEmpty (DList a) -> [a])
-> NonEmpty (DList a)
-> NonEmpty [a]
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. NonEmpty (DList a) -> [a]
forall l. IsList l => l -> [Item l]
toList
    all :: (Element (DList a) -> Bool) -> DList a -> Bool
all Element (DList a) -> Bool
f = (Element [a] -> Bool) -> [a] -> Bool
forall c. Collection c => (Element c -> Bool) -> c -> Bool
all Element [a] -> Bool
Element (DList a) -> Bool
f ([a] -> Bool) -> (DList a -> [a]) -> DList a -> Bool
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    any :: (Element (DList a) -> Bool) -> DList a -> Bool
any Element (DList a) -> Bool
f = (Element [a] -> Bool) -> [a] -> Bool
forall c. Collection c => (Element c -> Bool) -> c -> Bool
any Element [a] -> Bool
Element (DList a) -> Bool
f ([a] -> Bool) -> (DList a -> [a]) -> DList a -> Bool
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
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 = [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. CountOf (Element [a]) -> [a] -> [a]
forall c. Sequential c => CountOf (Element c) -> c -> c
take CountOf (Element [a])
CountOf (Element (DList a))
n ([a] -> [a]) -> (DList a -> [a]) -> 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
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    revTake :: CountOf (Element (DList a)) -> DList a -> DList a
revTake CountOf (Element (DList a))
n = [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. CountOf (Element [a]) -> [a] -> [a]
forall c. Sequential c => CountOf (Element c) -> c -> c
revTake CountOf (Element [a])
CountOf (Element (DList a))
n ([a] -> [a]) -> (DList a -> [a]) -> 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
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    drop :: CountOf (Element (DList a)) -> DList a -> DList a
drop CountOf (Element (DList a))
n = [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. CountOf (Element [a]) -> [a] -> [a]
forall c. Sequential c => CountOf (Element c) -> c -> c
drop CountOf (Element [a])
CountOf (Element (DList a))
n ([a] -> [a]) -> (DList a -> [a]) -> 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
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    revDrop :: CountOf (Element (DList a)) -> DList a -> DList a
revDrop CountOf (Element (DList a))
n = [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. CountOf (Element [a]) -> [a] -> [a]
forall c. Sequential c => CountOf (Element c) -> c -> c
revDrop CountOf (Element [a])
CountOf (Element (DList a))
n ([a] -> [a]) -> (DList a -> [a]) -> 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
. DList a -> [a]
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 = ([a] -> DList a)
-> ([a] -> DList a) -> ([a], [a]) -> (DList a, DList a)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList (([a], [a]) -> (DList a, DList a))
-> (DList a -> ([a], [a])) -> DList a -> (DList a, DList a)
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. CountOf (Element [a]) -> [a] -> ([a], [a])
forall c. Sequential c => CountOf (Element c) -> c -> (c, c)
splitAt CountOf (Element [a])
CountOf (Element (DList a))
n ([a] -> ([a], [a])) -> (DList a -> [a]) -> DList a -> ([a], [a])
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    splitOn :: (Element (DList a) -> Bool) -> DList a -> [DList a]
splitOn Element (DList a) -> Bool
f = ([a] -> DList a) -> [[a]] -> [DList a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([[a]] -> [DList a]) -> (DList a -> [[a]]) -> DList a -> [DList a]
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element [a] -> Bool) -> [a] -> [[a]]
forall c. Sequential c => (Element c -> Bool) -> c -> [c]
splitOn Element [a] -> Bool
Element (DList a) -> Bool
f ([a] -> [[a]]) -> (DList a -> [a]) -> 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
. DList a -> [a]
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 = ([a] -> DList a)
-> ([a] -> DList a) -> ([a], [a]) -> (DList a, DList a)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList (([a], [a]) -> (DList a, DList a))
-> (DList a -> ([a], [a])) -> DList a -> (DList a, DList a)
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element [a] -> Bool) -> [a] -> ([a], [a])
forall c. Sequential c => (Element c -> Bool) -> c -> (c, c)
break Element [a] -> Bool
Element (DList a) -> Bool
f ([a] -> ([a], [a])) -> (DList a -> [a]) -> DList a -> ([a], [a])
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
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 = ([a] -> DList a)
-> ([a] -> DList a) -> ([a], [a]) -> (DList a, DList a)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList (([a], [a]) -> (DList a, DList a))
-> (DList a -> ([a], [a])) -> DList a -> (DList a, DList a)
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element [a] -> Bool) -> [a] -> ([a], [a])
forall c. Sequential c => (Element c -> Bool) -> c -> (c, c)
breakEnd Element [a] -> Bool
Element (DList a) -> Bool
f ([a] -> ([a], [a])) -> (DList a -> [a]) -> DList a -> ([a], [a])
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    breakElem :: Element (DList a) -> DList a -> (DList a, DList a)
breakElem Element (DList a)
e = ([a] -> DList a)
-> ([a] -> DList a) -> ([a], [a]) -> (DList a, DList a)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList (([a], [a]) -> (DList a, DList a))
-> (DList a -> ([a], [a])) -> DList a -> (DList a, DList a)
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Element [a] -> [a] -> ([a], [a])
forall c.
(Sequential c, Eq (Element c)) =>
Element c -> c -> (c, c)
breakElem Element [a]
Element (DList a)
e ([a] -> ([a], [a])) -> (DList a -> [a]) -> DList a -> ([a], [a])
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    intersperse :: Element (DList a) -> DList a -> DList a
intersperse Element (DList a)
e = [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Element [a] -> [a] -> [a]
forall c. Sequential c => Element c -> c -> c
intersperse Element [a]
Element (DList a)
e ([a] -> [a]) -> (DList a -> [a]) -> 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
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    intercalate :: Element (DList a) -> DList a -> Element (DList a)
intercalate Element (DList a)
e = Element [a] -> [a] -> Element [a]
forall c.
(Sequential c, Monoid (Item c)) =>
Element c -> c -> Element c
intercalate Element [a]
Element (DList a)
e ([a] -> a) -> (DList a -> [a]) -> 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
. DList a -> [a]
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 = ([a] -> DList a)
-> ([a] -> DList a) -> ([a], [a]) -> (DList a, DList a)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList (([a], [a]) -> (DList a, DList a))
-> (DList a -> ([a], [a])) -> DList a -> (DList a, DList a)
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element [a] -> Bool) -> [a] -> ([a], [a])
forall c. Sequential c => (Element c -> Bool) -> c -> (c, c)
span Element [a] -> Bool
Element (DList a) -> Bool
f ([a] -> ([a], [a])) -> (DList a -> [a]) -> DList a -> ([a], [a])
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
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 = ([a] -> DList a)
-> ([a] -> DList a) -> ([a], [a]) -> (DList a, DList a)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList (([a], [a]) -> (DList a, DList a))
-> (DList a -> ([a], [a])) -> DList a -> (DList a, DList a)
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element [a] -> Bool) -> [a] -> ([a], [a])
forall c. Sequential c => (Element c -> Bool) -> c -> (c, c)
spanEnd Element [a] -> Bool
Element (DList a) -> Bool
f ([a] -> ([a], [a])) -> (DList a -> [a]) -> DList a -> ([a], [a])
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    filter :: (Element (DList a) -> Bool) -> DList a -> DList a
filter Element (DList a) -> Bool
f = [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element [a] -> Bool) -> [a] -> [a]
forall c. Sequential c => (Element c -> Bool) -> c -> c
filter Element [a] -> Bool
Element (DList a) -> Bool
f ([a] -> [a]) -> (DList a -> [a]) -> 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
. DList a -> [a]
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 = ([a] -> DList a)
-> ([a] -> DList a) -> ([a], [a]) -> (DList a, DList a)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList (([a], [a]) -> (DList a, DList a))
-> (DList a -> ([a], [a])) -> DList a -> (DList a, DList a)
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element [a] -> Bool) -> [a] -> ([a], [a])
forall c. Sequential c => (Element c -> Bool) -> c -> (c, c)
partition Element [a] -> Bool
Element (DList a) -> Bool
f ([a] -> ([a], [a])) -> (DList a -> [a]) -> DList a -> ([a], [a])
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    reverse :: DList a -> DList a
reverse = [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList 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 c. Sequential c => c -> c
reverse ([a] -> [a]) -> (DList a -> [a]) -> 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
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    uncons :: DList a -> Maybe (Element (DList a), DList a)
uncons DList a
dl = ([a] -> DList a) -> (a, [a]) -> (a, DList a)
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList ((a, [a]) -> (a, DList a)) -> Maybe (a, [a]) -> Maybe (a, DList a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> Maybe (Element [a], [a])
forall c. Sequential c => c -> Maybe (Element c, c)
uncons (DList a -> [Item (DList a)]
forall l. IsList l => l -> [Item l]
toList DList a
dl)
    unsnoc :: DList a -> Maybe (DList a, Element (DList a))
unsnoc DList a
dl = ([a] -> DList a) -> ([a], a) -> (DList a, a)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList (([a], a) -> (DList a, a)) -> Maybe ([a], a) -> Maybe (DList a, a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> Maybe ([a], Element [a])
forall c. Sequential c => c -> Maybe (c, Element c)
unsnoc (DList a -> [Item (DList a)]
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 = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DList (([a] -> [a]) -> DList a) -> ([a] -> [a]) -> DList a
forall a b. (a -> b) -> a -> b
$ (:) a
Element (DList a)
e ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a] -> [a]
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 = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DList (([a] -> [a]) -> DList a) -> ([a] -> [a]) -> DList a
forall a b. (a -> b) -> a -> b
$ DList a -> [a] -> [a]
forall a. DList a -> [a] -> [a]
unDList DList a
dl ([a] -> [a]) -> ([a] -> [a]) -> [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
Element (DList a)
e
    find :: (Element (DList a) -> Bool) -> DList a -> Maybe (Element (DList a))
find Element (DList a) -> Bool
f = (Element [a] -> Bool) -> [a] -> Maybe (Element [a])
forall c.
Sequential c =>
(Element c -> Bool) -> c -> Maybe (Element c)
find Element [a] -> Bool
Element (DList a) -> Bool
f ([a] -> Maybe a) -> (DList a -> [a]) -> DList a -> Maybe a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [a]
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 = [a] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element [a] -> Element [a] -> Ordering) -> [a] -> [a]
forall c.
Sequential c =>
(Element c -> Element c -> Ordering) -> c -> c
sortBy Element [a] -> Element [a] -> Ordering
Element (DList a) -> Element (DList a) -> Ordering
comp ([a] -> [a]) -> (DList a -> [a]) -> 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
. DList a -> [a]
forall l. IsList l => l -> [Item l]
toList
    singleton :: Element (DList a) -> DList a
singleton = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DList (([a] -> [a]) -> DList a) -> (a -> [a] -> [a]) -> a -> DList a
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 = [Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([Item (DList a)] -> DList a) -> [Item (DList a)] -> DList a
forall a b. (a -> b) -> a -> b
$ CountOf (Element [a]) -> Element [a] -> [a]
forall c. Sequential c => CountOf (Element c) -> Element c -> c
replicate CountOf (Element [a])
CountOf (Element (DList a))
n Element [a]
Element (DList a)
e