-- |
-- 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 = [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 = [Item (DList a)] -> String
forall a. Show a => a -> String
show ([Item (DList a)] -> String)
-> (DList a -> [Item (DList a)]) -> DList a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [Item (DList 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 b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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 a. a -> a
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 = (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
forall a. (Element (DList a) -> a -> a) -> a -> DList a -> a
foldr (b -> DList b -> DList b
Element (DList 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 b c a. (b -> c) -> (a -> b) -> a -> c
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 :: forall a. a -> DList a
pure = a -> DList a
Element (DList a) -> DList a
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 DList (a -> b) -> ((a -> b) -> DList b) -> DList b
forall a b. DList a -> (a -> 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 a b. 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 a. a -> DList a
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 = (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
forall a. (Element (DList a) -> a -> a) -> a -> DList a -> 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 b c a. (b -> c) -> (a -> b) -> a -> c
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 :: forall a. a -> DList a
return = a -> DList a
forall a. a -> DList a
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 = (Element [Item (DList a)] -> a -> a) -> a -> [Item (DList a)] -> a
forall collection a.
Foldable collection =>
(Element collection -> a -> a) -> a -> collection -> a
forall a.
(Element [Item (DList a)] -> a -> a) -> a -> [Item (DList a)] -> a
foldr Element [Item (DList a)] -> a -> a
Element (DList a) -> a -> a
f a
b ([Item (DList a)] -> a)
-> (DList a -> [Item (DList a)]) -> DList a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [Item (DList a)]
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 = (a -> Element [Item (DList a)] -> a) -> a -> [Item (DList a)] -> a
forall collection a.
Foldable collection =>
(a -> Element collection -> a) -> a -> collection -> a
forall a.
(a -> Element [Item (DList a)] -> a) -> a -> [Item (DList a)] -> a
foldl' a -> Element [Item (DList a)] -> a
a -> Element (DList a) -> a
f a
b ([Item (DList a)] -> a)
-> (DList a -> [Item (DList a)]) -> DList a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [Item (DList a)]
forall l. IsList l => l -> [Item l]
toList

instance Collection (DList a) where
    null :: DList a -> Bool
null = [Item (DList a)] -> Bool
forall c. Collection c => c -> Bool
null ([Item (DList a)] -> Bool)
-> (DList a -> [Item (DList a)]) -> DList a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [Item (DList a)]
forall l. IsList l => l -> [Item l]
toList
    length :: DList a -> CountOf (Element (DList a))
length = [Item (DList a)] -> CountOf a
[Item (DList a)] -> CountOf (Element [Item (DList a)])
forall c. Collection c => c -> CountOf (Element c)
length ([Item (DList a)] -> CountOf a)
-> (DList a -> [Item (DList a)]) -> DList a -> CountOf a
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [Item (DList a)]
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 = Element [Item (DList a)] -> [Item (DList a)] -> Bool
forall a.
(Eq a, a ~ Element [Item (DList a)]) =>
Element [Item (DList a)] -> [Item (DList a)] -> Bool
forall c a.
(Collection c, Eq a, a ~ Element c) =>
Element c -> c -> Bool
elem Element [Item (DList a)]
Element (DList a)
a ([Item (DList a)] -> Bool)
-> (DList a -> [Item (DList a)]) -> DList a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [Item (DList a)]
forall l. IsList l => l -> [Item l]
toList
    maximum :: forall a.
(Ord a, a ~ Element (DList a)) =>
NonEmpty (DList a) -> Element (DList a)
maximum = NonEmpty [Item (NonEmpty (DList a))] -> a
NonEmpty [Item (NonEmpty (DList a))]
-> Element [Item (NonEmpty (DList a))]
forall a.
(Ord a, a ~ Element [Item (NonEmpty (DList a))]) =>
NonEmpty [Item (NonEmpty (DList a))]
-> Element [Item (NonEmpty (DList a))]
forall c a.
(Collection c, Ord a, a ~ Element c) =>
NonEmpty c -> Element c
maximum (NonEmpty [Item (NonEmpty (DList a))] -> a)
-> (NonEmpty (DList a) -> NonEmpty [Item (NonEmpty (DList a))])
-> NonEmpty (DList a)
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. [Item (NonEmpty (DList a))] -> NonEmpty [Item (NonEmpty (DList a))]
forall c. Collection c => c -> NonEmpty c
nonEmpty_ ([Item (NonEmpty (DList a))]
 -> NonEmpty [Item (NonEmpty (DList a))])
-> (NonEmpty (DList a) -> [Item (NonEmpty (DList a))])
-> NonEmpty (DList a)
-> NonEmpty [Item (NonEmpty (DList a))]
forall b c a. (b -> c) -> (a -> b) -> a -> c
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) -> [Item (NonEmpty (DList a))]
forall l. IsList l => l -> [Item l]
toList
    minimum :: forall a.
(Ord a, a ~ Element (DList a)) =>
NonEmpty (DList a) -> Element (DList a)
minimum = NonEmpty [Item (NonEmpty (DList a))] -> a
NonEmpty [Item (NonEmpty (DList a))]
-> Element [Item (NonEmpty (DList a))]
forall a.
(Ord a, a ~ Element [Item (NonEmpty (DList a))]) =>
NonEmpty [Item (NonEmpty (DList a))]
-> Element [Item (NonEmpty (DList a))]
forall c a.
(Collection c, Ord a, a ~ Element c) =>
NonEmpty c -> Element c
minimum (NonEmpty [Item (NonEmpty (DList a))] -> a)
-> (NonEmpty (DList a) -> NonEmpty [Item (NonEmpty (DList a))])
-> NonEmpty (DList a)
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. [Item (NonEmpty (DList a))] -> NonEmpty [Item (NonEmpty (DList a))]
forall c. Collection c => c -> NonEmpty c
nonEmpty_ ([Item (NonEmpty (DList a))]
 -> NonEmpty [Item (NonEmpty (DList a))])
-> (NonEmpty (DList a) -> [Item (NonEmpty (DList a))])
-> NonEmpty (DList a)
-> NonEmpty [Item (NonEmpty (DList a))]
forall b c a. (b -> c) -> (a -> b) -> a -> c
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) -> [Item (NonEmpty (DList a))]
forall l. IsList l => l -> [Item l]
toList
    all :: (Element (DList a) -> Bool) -> DList a -> Bool
all Element (DList a) -> Bool
f = (Element [Item (DList a)] -> Bool) -> [Item (DList a)] -> Bool
forall c. Collection c => (Element c -> Bool) -> c -> Bool
all Element [Item (DList a)] -> Bool
Element (DList a) -> Bool
f ([Item (DList a)] -> Bool)
-> (DList a -> [Item (DList a)]) -> DList a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [Item (DList a)]
forall l. IsList l => l -> [Item l]
toList
    any :: (Element (DList a) -> Bool) -> DList a -> Bool
any Element (DList a) -> Bool
f = (Element [Item (DList a)] -> Bool) -> [Item (DList a)] -> Bool
forall c. Collection c => (Element c -> Bool) -> c -> Bool
any Element [Item (DList a)] -> Bool
Element (DList a) -> Bool
f ([Item (DList a)] -> Bool)
-> (DList a -> [Item (DList a)]) -> DList a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [Item (DList 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
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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 a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
[Item (DList 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 b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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 a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [a] -> DList a
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([[a]] -> [DList a]) -> (DList a -> [[a]]) -> DList a -> [DList a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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 a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
[Item (DList 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 b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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 a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
[Item (DList 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 b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList a)]
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 = ([a] -> DList a)
-> ([a] -> DList a) -> ([a], [a]) -> (DList a, DList a)
forall a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
[Item (DList 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 b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList a)]
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 = Element [Item (DList a)]
-> [Item (DList a)] -> Element [Item (DList a)]
forall c.
(Sequential c, Monoid (Item c)) =>
Element c -> c -> Element c
intercalate Element [Item (DList a)]
Element (DList a)
e ([Item (DList a)] -> a)
-> (DList a -> [Item (DList a)]) -> DList a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [Item (DList 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 a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
[Item (DList 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 b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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 a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
[Item (DList 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 b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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 a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> DList a
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList [a] -> DList a
[Item (DList 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 b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList a)]
forall l. IsList l => l -> [Item l]
toList
    reverse :: DList a -> DList a
reverse = [a] -> DList a
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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 b c a. (b -> c) -> (a, b) -> (a, c)
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second [a] -> DList a
[Item (DList 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 a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first [a] -> DList a
[Item (DList 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 b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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 [Item (DList a)] -> Bool)
-> [Item (DList a)] -> Maybe (Element [Item (DList a)])
forall c.
Sequential c =>
(Element c -> Bool) -> c -> Maybe (Element c)
find Element [Item (DList a)] -> Bool
Element (DList a) -> Bool
f ([Item (DList a)] -> Maybe a)
-> (DList a -> [Item (DList a)]) -> DList a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. DList a -> [Item (DList 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
[Item (DList a)] -> DList a
forall l. IsList l => [Item l] -> l
fromList ([a] -> DList a) -> (DList a -> [a]) -> DList a -> DList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
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 b c a. (b -> c) -> (a -> b) -> a -> c
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]
DList a -> [Item (DList 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 b c a. (b -> c) -> (a -> b) -> a -> c
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