    module Data.CircularList.Internal where

    import Control.Applicative hiding (empty)
    import Prelude
    import Data.List(find,unfoldr,foldl')
    import Control.DeepSeq(NFData(..))
    import Control.Monad(join)
    import qualified Data.Traversable as T
    import qualified Data.Foldable as F

    -- | A functional ring type.
    data CList a = Empty
                 | CList [a] a [a]

    {- Creating CLists -}

    -- | An empty CList.
    empty :: CList a
    empty :: forall a. CList a
    empty = CList a
    forall a. CList a
    Empty

    -- |Make a (balanced) CList from a list.
    fromList :: [a] -> CList a
    fromList :: forall a. [a] -> CList a
    fromList [] = CList a
    forall a. CList a
    Empty
    fromList a :: [a]
    a@(a
    i:[a]
    is) = let len :: Int
    len = [a] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [a]
    a
                            ([a]
    r,[a]
    l) = Int -> [a] -> ([a], [a])
    forall a. Int -> [a] -> ([a], [a])
    splitAt (Int
    len Int -> Int -> Int
    forall a. Integral a => a -> a -> a
    `div` Int
    2) [a]
    is
                        in [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList ([a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    l) a
    i [a]
    r

    singleton :: a -> CList a
    singleton :: forall a. a -> CList a
    singleton a
    a = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [] a
    a []

    {- Updating of CLists -}

    -- |Replaces the current focus with a new focus.
    update :: a -> CList a -> CList a
    update :: forall a. a -> CList a -> CList a
    update a
    v CList a
    Empty = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [] a
    v []
    update a
    v (CList [a]
    l a
    _ [a]
    r) = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [a]
    l a
    v [a]
    r

    -- |Reverse the direction of rotation.
    reverseDirection :: CList a -> CList a
    reverseDirection :: forall a. CList a -> CList a
    reverseDirection CList a
    Empty = CList a
    forall a. CList a
    Empty
    reverseDirection (CList [a]
    l a
    f [a]
    r) = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [a]
    r a
    f [a]
    l

    {- Creating Lists -}

    -- |Starting with the focus, go left and accumulate all
    -- elements of the CList in a list.
    leftElements :: CList a -> [a]
    leftElements :: forall a. CList a -> [a]
    leftElements CList a
    Empty = []
    leftElements (CList [a]
    l a
    f [a]
    r) = a
    f a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : ([a]
    l [a] -> [a] -> [a]
    forall a. [a] -> [a] -> [a]
    ++ ([a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    r))

    -- |Starting with the focus, go right and accumulate all
    -- elements of the CList in a list.
    rightElements :: CList a -> [a]
    rightElements :: forall a. CList a -> [a]
    rightElements CList a
    Empty = []
    rightElements (CList [a]
    l a
    f [a]
    r) = a
    f a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : ([a]
    r [a] -> [a] -> [a]
    forall a. [a] -> [a] -> [a]
    ++ ([a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    l))

    -- |Make a list from a CList.
    toList :: CList a -> [a]
    toList :: forall a. CList a -> [a]
    toList = CList a -> [a]
    forall a. CList a -> [a]
    rightElements

    -- |Make a CList into an infinite list.
    toInfList :: CList a -> [a]
    toInfList :: forall a. CList a -> [a]
    toInfList = [a] -> [a]
    forall a. HasCallStack => [a] -> [a]
    cycle ([a] -> [a]) -> (CList a -> [a]) -> CList a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CList a -> [a]
    forall a. CList a -> [a]
    toList

    {- Extraction and Accumulation -}

    -- |Return the focus of the CList.
    focus :: CList a -> Maybe a
    focus :: forall a. CList a -> Maybe a
    focus CList a
    Empty = Maybe a
    forall a. Maybe a
    Nothing
    focus (CList [a]
    _ a
    f [a]
    _) = a -> Maybe a
    forall a. a -> Maybe a
    Just a
    f

    -- |Insert an element into the CList as the new focus. The
    -- old focus is now the next element to the right.
    insertR :: a -> CList a -> CList a
    insertR :: forall a. a -> CList a -> CList a
    insertR a
    i CList a
    Empty = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [] a
    i []
    insertR a
    i (CList [a]
    l a
    f [a]
    r) = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [a]
    l a
    i (a
    fa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    r)

    -- |Insert an element into the CList as the new focus. The
    -- old focus is now the next element to the left.
    insertL :: a -> CList a -> CList a
    insertL :: forall a. a -> CList a -> CList a
    insertL a
    i CList a
    Empty = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [] a
    i []
    insertL a
    i (CList [a]
    l a
    f [a]
    r) = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList (a
    fa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    l) a
    i [a]
    r

    -- |Remove the focus from the CList. The new focus is the
    -- next element to the left.
    removeL :: CList a -> CList a
    removeL :: forall a. CList a -> CList a
    removeL CList a
    Empty = CList a
    forall a. CList a
    Empty
    removeL (CList [] a
    _ []) = CList a
    forall a. CList a
    Empty
    removeL (CList (a
    l:[a]
    ls) a
    _ [a]
    rs) = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [a]
    ls a
    l [a]
    rs
    removeL (CList [] a
    _ [a]
    rs) = let (a
    f:[a]
    ls) = [a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    rs
                              in [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [a]
    ls a
    f []

    -- |Remove the focus from the CList.
    removeR :: CList a -> CList a
    removeR :: forall a. CList a -> CList a
    removeR CList a
    Empty = CList a
    forall a. CList a
    Empty
    removeR (CList [] a
    _ []) = CList a
    forall a. CList a
    Empty
    removeR (CList [a]
    l a
    _ (a
    r:[a]
    rs)) = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [a]
    l a
    r [a]
    rs
    removeR (CList [a]
    l a
    _ []) = let (a
    f:[a]
    rs) = [a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    l
                             in [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [] a
    f [a]
    rs

    {- Manipulating Rotation -}

    -- |Return all possible rotations of the provided 'CList', where the
    -- focus is the provided 'CList'.
    allRotations :: CList a -> CList (CList a)
    allRotations :: forall a. CList a -> CList (CList a)
    allRotations CList a
    Empty = CList a -> CList (CList a)
    forall a. a -> CList a
    singleton CList a
    forall a. CList a
    Empty
    allRotations CList a
    cl = [CList a] -> CList a -> [CList a] -> CList (CList a)
    forall a. [a] -> a -> [a] -> CList a
    CList [CList a]
    ls CList a
    cl [CList a]
    rs
      where
        ls :: [CList a]
    ls = (CList a -> Maybe (CList a, CList a)) -> CList a -> [CList a]
    forall b a. (b -> Maybe (a, b)) -> b -> [a]
    unfoldr ((CList a -> (CList a, CList a))
    -> Maybe (CList a) -> Maybe (CList a, CList a)
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((CList a -> CList a -> (CList a, CList a))
    -> CList a -> (CList a, CList a)
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (,)) (Maybe (CList a) -> Maybe (CList a, CList a))
    -> (CList a -> Maybe (CList a))
    -> CList a
    -> Maybe (CList a, CList a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CList a -> Maybe (CList a)
    forall a. CList a -> Maybe (CList a)
    mRotL) CList a
    cl
        rs :: [CList a]
    rs = (CList a -> Maybe (CList a, CList a)) -> CList a -> [CList a]
    forall b a. (b -> Maybe (a, b)) -> b -> [a]
    unfoldr ((CList a -> (CList a, CList a))
    -> Maybe (CList a) -> Maybe (CList a, CList a)
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((CList a -> CList a -> (CList a, CList a))
    -> CList a -> (CList a, CList a)
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (,)) (Maybe (CList a) -> Maybe (CList a, CList a))
    -> (CList a -> Maybe (CList a))
    -> CList a
    -> Maybe (CList a, CList a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CList a -> Maybe (CList a)
    forall a. CList a -> Maybe (CList a)
    mRotR) CList a
    cl

    -- |Rotate the focus to the previous (left) element.
    rotL :: CList a -> CList a
    rotL :: forall a. CList a -> CList a
    rotL CList a
    Empty = CList a
    forall a. CList a
    Empty
    rotL r :: CList a
    r@(CList [] a
    _ []) = CList a
    r
    rotL (CList (a
    l:[a]
    ls) a
    f [a]
    rs) = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [a]
    ls a
    l (a
    fa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    rs)
    rotL (CList [] a
    f [a]
    rs) = let (a
    l:[a]
    ls) = [a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    rs
                           in [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [a]
    ls a
    l [a
    f]

    -- |A non-cyclic version of 'rotL'; that is, only rotate the focus if
    -- there is a previous (left) element to rotate to.
    mRotL :: CList a -> Maybe (CList a)
    mRotL :: forall a. CList a -> Maybe (CList a)
    mRotL (CList (a
    l:[a]
    ls) a
    f [a]
    rs) = CList a -> Maybe (CList a)
    forall a. a -> Maybe a
    Just (CList a -> Maybe (CList a)) -> CList a -> Maybe (CList a)
    forall a b. (a -> b) -> a -> b
    $ [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [a]
    ls a
    l (a
    fa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    rs)
    mRotL CList a
    _ = Maybe (CList a)
    forall a. Maybe a
    Nothing

    -- |Rotate the focus to the next (right) element.
    rotR :: CList a -> CList a
    rotR :: forall a. CList a -> CList a
    rotR CList a
    Empty = CList a
    forall a. CList a
    Empty
    rotR r :: CList a
    r@(CList [] a
    _ []) = CList a
    r
    rotR (CList [a]
    ls a
    f (a
    r:[a]
    rs)) = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList (a
    fa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    ls) a
    r [a]
    rs
    rotR (CList [a]
    ls a
    f []) = let (a
    r:[a]
    rs) = [a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    ls
                           in [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [a
    f] a
    r [a]
    rs

    -- |A non-cyclic version of 'rotL'; that is, only rotate the focus if
    -- there is a previous (left) element to rotate to.
    mRotR :: CList a -> Maybe (CList a)
    mRotR :: forall a. CList a -> Maybe (CList a)
    mRotR (CList [a]
    ls a
    f (a
    r:[a]
    rs)) = CList a -> Maybe (CList a)
    forall a. a -> Maybe a
    Just (CList a -> Maybe (CList a)) -> CList a -> Maybe (CList a)
    forall a b. (a -> b) -> a -> b
    $ [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList (a
    fa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    ls) a
    r [a]
    rs
    mRotR CList a
    _ = Maybe (CList a)
    forall a. Maybe a
    Nothing

    -- |Rotate the focus the specified number of times; if the index is
    -- positive then it is rotated to the right; otherwise it is rotated
    -- to the left.
    rotN :: Int -> CList a -> CList a
    rotN :: forall a. Int -> CList a -> CList a
    rotN Int
    _ CList a
    Empty = CList a
    forall a. CList a
    Empty
    rotN Int
    _ cl :: CList a
    cl@(CList [] a
    _ []) = CList a
    cl
    rotN Int
    n CList a
    cl = (CList a -> CList a) -> CList a -> [CList a]
    forall a. (a -> a) -> a -> [a]
    iterate CList a -> CList a
    forall a. CList a -> CList a
    rot CList a
    cl [CList a] -> Int -> CList a
    forall a. HasCallStack => [a] -> Int -> a
    !! Int
    n'
      where
        n' :: Int
    n' = Int -> Int
    forall a. Num a => a -> a
    abs Int
    n
        rot :: CList a -> CList a
    rot | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    0     = CList a -> CList a
    forall a. CList a -> CList a
    rotL
            | Bool
    otherwise = CList a -> CList a
    forall a. CList a -> CList a
    rotR

    -- |A wrapper around 'rotN' that doesn't rotate the CList if @n <= 0@.
    rotNR :: Int -> CList a -> CList a
    rotNR :: forall a. Int -> CList a -> CList a
    rotNR Int
    n CList a
    cl
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0 = CList a
    cl
      | Bool
    otherwise = Int -> CList a -> CList a
    forall a. Int -> CList a -> CList a
    rotN Int
    n CList a
    cl

    -- |Rotate the focus the specified number of times to the left (but
    -- don't rotate if @n <= 0@).
    rotNL :: Int -> CList a -> CList a
    rotNL :: forall a. Int -> CList a -> CList a
    rotNL Int
    n CList a
    cl
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0 = CList a
    cl
      | Bool
    otherwise = Int -> CList a -> CList a
    forall a. Int -> CList a -> CList a
    rotN (Int -> Int
    forall a. Num a => a -> a
    negate Int
    n) CList a
    cl

    -- |Rotate the 'CList' such that the specified element (if it exists)
    -- is focused.
    rotateTo :: (Eq a) => a -> CList a -> Maybe (CList a)
    rotateTo :: forall a. Eq a => a -> CList a -> Maybe (CList a)
    rotateTo a
    a = (a -> Bool) -> CList a -> Maybe (CList a)
    forall a. (a -> Bool) -> CList a -> Maybe (CList a)
    findRotateTo (a
    aa -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    ==)

    -- |Attempt to rotate the 'CList' such that focused element matches
    -- the supplied predicate.
    findRotateTo :: (a -> Bool) -> CList a -> Maybe (CList a)
    findRotateTo :: forall a. (a -> Bool) -> CList a -> Maybe (CList a)
    findRotateTo a -> Bool
    p = (CList a -> Bool) -> [CList a] -> Maybe (CList a)
    forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Maybe a
    find (Bool -> (a -> Bool) -> Maybe a -> Bool
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Bool
    False a -> Bool
    p (Maybe a -> Bool) -> (CList a -> Maybe a) -> CList a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CList a -> Maybe a
    forall a. CList a -> Maybe a
    focus) ([CList a] -> Maybe (CList a))
    -> (CList a -> [CList a]) -> CList a -> Maybe (CList a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CList (CList a) -> [CList a]
    forall a. CList a -> [a]
    toList (CList (CList a) -> [CList a])
    -> (CList a -> CList (CList a)) -> CList a -> [CList a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CList a -> CList (CList a)
    forall a. CList a -> CList (CList a)
    allRotations

    {- List-like functions -}

    -- |Remove those elements that do not satisfy the supplied predicate,
    -- rotating to the right if the focus does not satisfy the predicate.
    filterR :: (a -> Bool) -> CList a -> CList a
    filterR :: forall a. (a -> Bool) -> CList a -> CList a
    filterR = (CList a -> CList a) -> (a -> Bool) -> CList a -> CList a
    forall a. (CList a -> CList a) -> (a -> Bool) -> CList a -> CList a
    filterCL CList a -> CList a
    forall a. CList a -> CList a
    removeR

    -- |As with 'filterR', but rotates to the /left/ if the focus does not
    -- satisfy the predicate.
    filterL :: (a -> Bool) -> CList a -> CList a
    filterL :: forall a. (a -> Bool) -> CList a -> CList a
    filterL = (CList a -> CList a) -> (a -> Bool) -> CList a -> CList a
    forall a. (CList a -> CList a) -> (a -> Bool) -> CList a -> CList a
    filterCL CList a -> CList a
    forall a. CList a -> CList a
    removeL

    -- |Abstract away what to do with the focused element if it doesn't
    -- match the predicate when filtering.
    filterCL :: (CList a -> CList a) -> (a -> Bool) -> CList a -> CList a
    filterCL :: forall a. (CList a -> CList a) -> (a -> Bool) -> CList a -> CList a
    filterCL CList a -> CList a
    _ a -> Bool
    _ CList a
    Empty = CList a
    forall a. CList a
    Empty
    filterCL CList a -> CList a
    rm a -> Bool
    p (CList [a]
    l a
    f [a]
    r)
      | a -> Bool
    p a
    f = CList a
    cl'
      | Bool
    otherwise = CList a -> CList a
    rm CList a
    cl'
      where
        cl' :: CList a
    cl' = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList ((a -> Bool) -> [a] -> [a]
    forall a. (a -> Bool) -> [a] -> [a]
    filter a -> Bool
    p [a]
    l) a
    f ((a -> Bool) -> [a] -> [a]
    forall a. (a -> Bool) -> [a] -> [a]
    filter a -> Bool
    p [a]
    r)

    -- |A right-fold, rotating to the right through the CList.
    foldrR :: (a -> b -> b) -> b -> CList a -> b
    foldrR :: forall a b. (a -> b -> b) -> b -> CList a -> b
    foldrR = (CList a -> [a]) -> (a -> b -> b) -> b -> CList a -> b
    forall a b. (CList a -> [a]) -> (a -> b -> b) -> b -> CList a -> b
    foldrCL CList a -> [a]
    forall a. CList a -> [a]
    rightElements

    -- |A right-fold, rotating to the left through the CList.
    foldrL :: (a -> b -> b) -> b -> CList a -> b
    foldrL :: forall a b. (a -> b -> b) -> b -> CList a -> b
    foldrL = (CList a -> [a]) -> (a -> b -> b) -> b -> CList a -> b
    forall a b. (CList a -> [a]) -> (a -> b -> b) -> b -> CList a -> b
    foldrCL CList a -> [a]
    forall a. CList a -> [a]
    leftElements

    -- |Abstract away direction for a foldr.
    foldrCL :: (CList a -> [a]) -> (a -> b -> b) -> b -> CList a -> b
    foldrCL :: forall a b. (CList a -> [a]) -> (a -> b -> b) -> b -> CList a -> b
    foldrCL CList a -> [a]
    toL a -> b -> b
    f b
    a = (a -> b -> b) -> b -> [a] -> b
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr a -> b -> b
    f b
    a ([a] -> b) -> (CList a -> [a]) -> CList a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CList a -> [a]
    toL

    -- |A (strict) left-fold, rotating to the right through the CList.
    foldlR :: (a -> b -> a) -> a -> CList b -> a
    foldlR :: forall a b. (a -> b -> a) -> a -> CList b -> a
    foldlR = (CList b -> [b]) -> (a -> b -> a) -> a -> CList b -> a
    forall b a. (CList b -> [b]) -> (a -> b -> a) -> a -> CList b -> a
    foldlCL CList b -> [b]
    forall a. CList a -> [a]
    rightElements

    -- |A (strict) left-fold, rotating to the left through the CList.
    foldlL :: (a -> b -> a) -> a -> CList b -> a
    foldlL :: forall a b. (a -> b -> a) -> a -> CList b -> a
    foldlL = (CList b -> [b]) -> (a -> b -> a) -> a -> CList b -> a
    forall b a. (CList b -> [b]) -> (a -> b -> a) -> a -> CList b -> a
    foldlCL CList b -> [b]
    forall a. CList a -> [a]
    leftElements

    -- |Abstract away direction for a foldl'.
    foldlCL :: (CList b -> [b]) -> (a -> b -> a) -> a -> CList b -> a
    foldlCL :: forall b a. (CList b -> [b]) -> (a -> b -> a) -> a -> CList b -> a
    foldlCL CList b -> [b]
    toL a -> b -> a
    f a
    a = (a -> b -> a) -> a -> [b] -> a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' a -> b -> a
    f a
    a ([b] -> a) -> (CList b -> [b]) -> CList b -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CList b -> [b]
    toL

    {- Manipulating Packing -}

    -- |Balance the CList. Equivalent to `fromList . toList`
    balance :: CList a -> CList a
    balance :: forall a. CList a -> CList a
    balance = [a] -> CList a
    forall a. [a] -> CList a
    fromList ([a] -> CList a) -> (CList a -> [a]) -> CList a -> CList a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CList a -> [a]
    forall a. CList a -> [a]
    toList

    -- |Move all elements to the left side of the CList.
    packL :: CList a -> CList a
    packL :: forall a. CList a -> CList a
    packL CList a
    Empty = CList a
    forall a. CList a
    Empty
    packL (CList [a]
    l a
    f [a]
    r) = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList ([a]
    l [a] -> [a] -> [a]
    forall a. [a] -> [a] -> [a]
    ++ ([a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    r)) a
    f []

    -- |Move all elements to the right side of the CList.
    packR :: CList a -> CList a
    packR :: forall a. CList a -> CList a
    packR CList a
    Empty = CList a
    forall a. CList a
    Empty
    packR (CList [a]
    l a
    f [a]
    r) = [a] -> a -> [a] -> CList a
    forall a. [a] -> a -> [a] -> CList a
    CList [] a
    f ([a]
    r [a] -> [a] -> [a]
    forall a. [a] -> [a] -> [a]
    ++ ([a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    l))

    {- Information -}

    -- |Returns true if the CList is empty.
    isEmpty :: CList a -> Bool
    isEmpty :: forall a. CList a -> Bool
    isEmpty CList a
    Empty = Bool
    True
    isEmpty CList a
    _ = Bool
    False

    -- |Return the size of the CList.
    size :: CList a -> Int
    size :: forall a. CList a -> Int
    size CList a
    Empty = Int
    0
    size (CList [a]
    l a
    _ [a]
    r) = Int
    1 Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + ([a] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [a]
    l) Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + ([a] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [a]
    r)

    {- Instances -}

    instance (Show a) => Show (CList a) where
     showsPrec :: Int -> CList a -> ShowS
    showsPrec Int
    d CList a
    cl  = Bool -> ShowS -> ShowS
    showParen (Int
    d Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    10) (ShowS -> ShowS) -> ShowS -> ShowS
    forall a b. (a -> b) -> a -> b
    $
                       String -> ShowS
    showString String
    "fromList " ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [a] -> ShowS
    forall a. Show a => a -> ShowS
    shows (CList a -> [a]
    forall a. CList a -> [a]
    toList CList a
    cl)

    instance (Read a) => Read (CList a) where
     readsPrec :: Int -> ReadS (CList a)
    readsPrec Int
    p = Bool -> ReadS (CList a) -> ReadS (CList a)
    forall a. Bool -> ReadS a -> ReadS a
    readParen (Int
    p Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    10) (ReadS (CList a) -> ReadS (CList a))
    -> ReadS (CList a) -> ReadS (CList a)
    forall a b. (a -> b) -> a -> b
    $ \ String
    r -> do
       ("fromList",s) <- ReadS String
    lex String
    r
       (xs,t) <- reads s
       return (fromList xs,t)

    instance (Eq a) => Eq (CList a) where
      CList a
    a == :: CList a -> CList a -> Bool
    == CList a
    b = (CList a -> Bool) -> [CList a] -> Bool
    forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
    any ((CList a -> [a]
    forall a. CList a -> [a]
    toList CList a
    a [a] -> [a] -> Bool
    forall a. Eq a => a -> a -> Bool
    ==) ([a] -> Bool) -> (CList a -> [a]) -> CList a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CList a -> [a]
    forall a. CList a -> [a]
    toList) ([CList a] -> Bool)
    -> (CList (CList a) -> [CList a]) -> CList (CList a) -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CList (CList a) -> [CList a]
    forall a. CList a -> [a]
    toList (CList (CList a) -> Bool) -> CList (CList a) -> Bool
    forall a b. (a -> b) -> a -> b
    $ CList a -> CList (CList a)
    forall a. CList a -> CList (CList a)
    allRotations CList a
    b

    instance (NFData a) => NFData (CList a) where
      rnf :: CList a -> ()
    rnf CList a
    Empty         = ()
      rnf (CList [a]
    l a
    f [a]
    r) = a -> ()
    forall a. NFData a => a -> ()
    rnf a
    f
                          () -> () -> ()
    forall a b. a -> b -> b
    `seq` [a] -> ()
    forall a. NFData a => a -> ()
    rnf [a]
    l
                          () -> () -> ()
    forall a b. a -> b -> b
    `seq` [a] -> ()
    forall a. NFData a => a -> ()
    rnf [a]
    r

    instance Functor CList where
        fmap :: forall a b. (a -> b) -> CList a -> CList b
    fmap a -> b
    _ CList a
    Empty = CList b
    forall a. CList a
    Empty
        fmap a -> b
    fn (CList [a]
    l a
    f [a]
    r) = ([b] -> b -> [b] -> CList b
    forall a. [a] -> a -> [a] -> CList a
    CList ((a -> b) -> [a] -> [b]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> b
    fn [a]
    l) (a -> b
    fn a
    f) ((a -> b) -> [a] -> [b]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> b
    fn [a]
    r))

    instance F.Foldable CList where
      foldMap :: forall m a. Monoid m => (a -> m) -> CList a -> m
    foldMap = (a -> m) -> CList a -> m
    forall (t :: * -> *) m a.
    (Traversable t, Monoid m) =>
    (a -> m) -> t a -> m
    T.foldMapDefault

    instance T.Traversable CList where
      -- | traverses the list from left to right, starting at the focus
      traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> CList a -> f (CList b)
    traverse a -> f b
    _ CList a
    Empty         = CList b -> f (CList b)
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure CList b
    forall a. CList a
    Empty
      traverse a -> f b
    g (CList [a]
    l a
    f [a]
    r) = (\b
    f' [b]
    r' [b]
    l' -> [b] -> b -> [b] -> CList b
    forall a. [a] -> a -> [a] -> CList a
    CList [b]
    l' b
    f' [b]
    r') (b -> [b] -> [b] -> CList b) -> f b -> f ([b] -> [b] -> CList b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> a -> f b
    g a
    f
                                                               f ([b] -> [b] -> CList b) -> f [b] -> f ([b] -> CList b)
    forall a b. f (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (a -> f b) -> [a] -> f [b]
    forall (t :: * -> *) (f :: * -> *) a b.
    (Traversable t, Applicative f) =>
    (a -> f b) -> t a -> f (t b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> [a] -> f [b]
    T.traverse a -> f b
    g [a]
    r
                                                               f ([b] -> CList b) -> f [b] -> f (CList b)
    forall a b. f (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (a -> f b) -> [a] -> f [b]
    forall (t :: * -> *) (f :: * -> *) a b.
    (Traversable t, Applicative f) =>
    (a -> f b) -> t a -> f (t b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> [a] -> f [b]
    T.traverse a -> f b
    g [a]
    l