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 :: CList a
empty = CList a
forall a. CList a
Empty

-- |Make a (balanced) CList from a list.
fromList :: [a] -> CList a
fromList :: [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 (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 :: 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 :: 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 :: 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 :: 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 :: 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 :: 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 :: CList a -> [a]
toInfList = [a] -> [a]
forall a. [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 :: 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 :: 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 :: 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 :: 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 :: 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 :: 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 (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 (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 :: 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 :: 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 :: 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 :: 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 :: 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. [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 :: 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 :: 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 :: 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 :: (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 :: (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 :: (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 :: (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 :: (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 :: (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 :: (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 (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 :: (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 :: (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 :: (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 (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 :: 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 :: 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 :: 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 :: 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 :: 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 (t :: * -> *) a. Foldable t => t a -> Int
length [a]
l) Int -> Int -> Int
forall a. Num a => a -> a -> 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
   (String
"fromList",String
s) <- ReadS String
lex String
r
   ([a]
xs,String
t) <- ReadS [a]
forall a. Read a => ReadS a
reads String
s
   (CList a, String) -> [(CList a, String)]
forall (m :: * -> *) a. Monad m => a -> m a
return ([a] -> CList a
forall a. [a] -> CList a
fromList [a]
xs,String
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
                      () -> () -> ()
`seq` [a] -> ()
forall a. NFData a => a -> ()
rnf [a]
l
                      () -> () -> ()
`seq` [a] -> ()
forall a. NFData a => a -> ()
rnf [a]
r

instance Functor CList where
    fmap :: (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 (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 (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
fn [a]
r))

instance F.Foldable CList where
  foldMap :: (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 :: (a -> f b) -> CList a -> f (CList b)
traverse a -> f b
_ CList a
Empty         = CList b -> f (CList b)
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 (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)
T.traverse a -> f b
g [a]
r
                                                           f ([b] -> CList b) -> f [b] -> f (CList 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)
T.traverse a -> f b
g [a]
l