module Data.Countable where

import Data.Int
import Data.Void
import Data.Word
import Prelude

-- | Values form a possibly empty, possibly finite, countable sequence.
class Eq a => Countable a where
    countPrevious :: a -> Maybe a
    countMaybeNext :: Maybe a -> Maybe a

countDown :: (Countable a) => a -> [a]
countDown :: forall a. Countable a => a -> [a]
countDown a
a =
    case a -> Maybe a
forall a. Countable a => a -> Maybe a
countPrevious a
a of
        Just a
a' -> a
a' a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (a -> [a]
forall a. Countable a => a -> [a]
countDown a
a')
        Maybe a
Nothing -> []

instance Countable Void where
    countPrevious :: Void -> Maybe Void
countPrevious = Void -> Maybe Void
forall a. Void -> a
absurd
    countMaybeNext :: Maybe Void -> Maybe Void
countMaybeNext Maybe Void
Nothing = Maybe Void
forall a. Maybe a
Nothing
    countMaybeNext (Just Void
n) = Void -> Maybe Void
forall a. Void -> a
absurd Void
n

instance Countable () where
    countPrevious :: () -> Maybe ()
countPrevious () = Maybe ()
forall a. Maybe a
Nothing
    countMaybeNext :: Maybe () -> Maybe ()
countMaybeNext Maybe ()
Nothing = () -> Maybe ()
forall a. a -> Maybe a
Just ()
    countMaybeNext (Just ()) = Maybe ()
forall a. Maybe a
Nothing

instance Countable Bool where
    countPrevious :: Bool -> Maybe Bool
countPrevious Bool
True = Bool -> Maybe Bool
forall a. a -> Maybe a
Just Bool
False
    countPrevious Bool
False = Maybe Bool
forall a. Maybe a
Nothing
    countMaybeNext :: Maybe Bool -> Maybe Bool
countMaybeNext Maybe Bool
Nothing = Bool -> Maybe Bool
forall a. a -> Maybe a
Just Bool
False
    countMaybeNext (Just Bool
False) = Bool -> Maybe Bool
forall a. a -> Maybe a
Just Bool
True
    countMaybeNext (Just Bool
True) = Maybe Bool
forall a. Maybe a
Nothing

boundedCountPrevious :: (Eq a, Bounded a, Enum a) => a -> Maybe a
boundedCountPrevious :: forall a. (Eq a, Bounded a, Enum a) => a -> Maybe a
boundedCountPrevious a
n
    | a
n a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. Bounded a => a
minBound = Maybe a
forall a. Maybe a
Nothing
boundedCountPrevious a
n = a -> Maybe a
forall a. a -> Maybe a
Just (a -> a
forall a. Enum a => a -> a
pred a
n)

boundedCountMaybeNext :: (Eq a, Bounded a, Enum a) => Maybe a -> Maybe a
boundedCountMaybeNext :: forall a. (Eq a, Bounded a, Enum a) => Maybe a -> Maybe a
boundedCountMaybeNext Maybe a
Nothing = a -> Maybe a
forall a. a -> Maybe a
Just a
forall a. Bounded a => a
minBound
boundedCountMaybeNext (Just a
n)
    | a
n a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. Bounded a => a
maxBound = Maybe a
forall a. Maybe a
Nothing
boundedCountMaybeNext (Just a
n) = a -> Maybe a
forall a. a -> Maybe a
Just (a -> a
forall a. Enum a => a -> a
succ a
n)

instance Countable Word8 where
    countPrevious :: Word8 -> Maybe Word8
countPrevious = Word8 -> Maybe Word8
forall a. (Eq a, Bounded a, Enum a) => a -> Maybe a
boundedCountPrevious
    countMaybeNext :: Maybe Word8 -> Maybe Word8
countMaybeNext = Maybe Word8 -> Maybe Word8
forall a. (Eq a, Bounded a, Enum a) => Maybe a -> Maybe a
boundedCountMaybeNext

instance Countable Word16 where
    countPrevious :: Word16 -> Maybe Word16
countPrevious = Word16 -> Maybe Word16
forall a. (Eq a, Bounded a, Enum a) => a -> Maybe a
boundedCountPrevious
    countMaybeNext :: Maybe Word16 -> Maybe Word16
countMaybeNext = Maybe Word16 -> Maybe Word16
forall a. (Eq a, Bounded a, Enum a) => Maybe a -> Maybe a
boundedCountMaybeNext

instance Countable Word32 where
    countPrevious :: Word32 -> Maybe Word32
countPrevious = Word32 -> Maybe Word32
forall a. (Eq a, Bounded a, Enum a) => a -> Maybe a
boundedCountPrevious
    countMaybeNext :: Maybe Word32 -> Maybe Word32
countMaybeNext = Maybe Word32 -> Maybe Word32
forall a. (Eq a, Bounded a, Enum a) => Maybe a -> Maybe a
boundedCountMaybeNext

instance Countable Word64 where
    countPrevious :: Word64 -> Maybe Word64
countPrevious = Word64 -> Maybe Word64
forall a. (Eq a, Bounded a, Enum a) => a -> Maybe a
boundedCountPrevious
    countMaybeNext :: Maybe Word64 -> Maybe Word64
countMaybeNext = Maybe Word64 -> Maybe Word64
forall a. (Eq a, Bounded a, Enum a) => Maybe a -> Maybe a
boundedCountMaybeNext

instance Countable Int8 where
    countPrevious :: Int8 -> Maybe Int8
countPrevious = Int8 -> Maybe Int8
forall a. (Eq a, Bounded a, Enum a) => a -> Maybe a
boundedCountPrevious
    countMaybeNext :: Maybe Int8 -> Maybe Int8
countMaybeNext = Maybe Int8 -> Maybe Int8
forall a. (Eq a, Bounded a, Enum a) => Maybe a -> Maybe a
boundedCountMaybeNext

instance Countable Int16 where
    countPrevious :: Int16 -> Maybe Int16
countPrevious = Int16 -> Maybe Int16
forall a. (Eq a, Bounded a, Enum a) => a -> Maybe a
boundedCountPrevious
    countMaybeNext :: Maybe Int16 -> Maybe Int16
countMaybeNext = Maybe Int16 -> Maybe Int16
forall a. (Eq a, Bounded a, Enum a) => Maybe a -> Maybe a
boundedCountMaybeNext

instance Countable Int32 where
    countPrevious :: Int32 -> Maybe Int32
countPrevious = Int32 -> Maybe Int32
forall a. (Eq a, Bounded a, Enum a) => a -> Maybe a
boundedCountPrevious
    countMaybeNext :: Maybe Int32 -> Maybe Int32
countMaybeNext = Maybe Int32 -> Maybe Int32
forall a. (Eq a, Bounded a, Enum a) => Maybe a -> Maybe a
boundedCountMaybeNext

instance Countable Int64 where
    countPrevious :: Int64 -> Maybe Int64
countPrevious = Int64 -> Maybe Int64
forall a. (Eq a, Bounded a, Enum a) => a -> Maybe a
boundedCountPrevious
    countMaybeNext :: Maybe Int64 -> Maybe Int64
countMaybeNext = Maybe Int64 -> Maybe Int64
forall a. (Eq a, Bounded a, Enum a) => Maybe a -> Maybe a
boundedCountMaybeNext

instance Countable Integer where
    countPrevious :: Integer -> Maybe Integer
countPrevious Integer
0 = Maybe Integer
forall a. Maybe a
Nothing
    countPrevious Integer
a
        | Integer
a Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 = Integer -> Maybe Integer
forall a. a -> Maybe a
Just (-Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1)
    countPrevious Integer
a = Integer -> Maybe Integer
forall a. a -> Maybe a
Just (-Integer
a)
    countMaybeNext :: Maybe Integer -> Maybe Integer
countMaybeNext = Integer -> Maybe Integer
forall a. a -> Maybe a
Just (Integer -> Maybe Integer)
-> (Maybe Integer -> Integer) -> Maybe Integer -> Maybe Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe Integer -> Integer
forall a. InfiniteCountable a => Maybe a -> a
countNext

instance (Countable a) => Countable (Maybe a) where
    countPrevious :: Maybe a -> Maybe (Maybe a)
countPrevious = (a -> Maybe a) -> Maybe a -> Maybe (Maybe a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Maybe a
forall a. Countable a => a -> Maybe a
countPrevious
    countMaybeNext :: Maybe (Maybe a) -> Maybe (Maybe a)
countMaybeNext Maybe (Maybe a)
Nothing = Maybe a -> Maybe (Maybe a)
forall a. a -> Maybe a
Just Maybe a
forall a. Maybe a
Nothing
    countMaybeNext (Just Maybe a
ma) = (a -> Maybe a) -> Maybe a -> Maybe (Maybe a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Maybe a
forall a. a -> Maybe a
Just (Maybe a -> Maybe a
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext Maybe a
ma)

maybeRecount :: (Countable a, Countable b) => a -> Maybe b
maybeRecount :: forall a b. (Countable a, Countable b) => a -> Maybe b
maybeRecount a
a =
    case a -> Maybe a
forall a. Countable a => a -> Maybe a
countPrevious a
a of
        Just a
a' -> do
            Maybe b
b' <- a -> Maybe (Maybe b)
forall a b. (Countable a, Countable b) => a -> Maybe b
maybeRecount a
a'
            Maybe b -> Maybe b
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext Maybe b
b'
        Maybe a
Nothing -> Maybe b -> Maybe b
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext Maybe b
forall a. Maybe a
Nothing

{-
Right 0
Left 0
Right 1
Left 1
Left 2
Left 3
-}
instance (Countable a, Countable b) => Countable (Either a b) where
    countPrevious :: Either a b -> Maybe (Either a b)
countPrevious (Right b
b) =
        case b -> Maybe b
forall a. Countable a => a -> Maybe a
countPrevious b
b of
            Just b
b' ->
                case b -> Maybe a
forall a b. (Countable a, Countable b) => a -> Maybe b
maybeRecount b
b' of
                    Just a
a -> Either a b -> Maybe (Either a b)
forall a. a -> Maybe a
Just (a -> Either a b
forall a b. a -> Either a b
Left a
a)
                    Maybe a
Nothing -> Either a b -> Maybe (Either a b)
forall a. a -> Maybe a
Just (b -> Either a b
forall a b. b -> Either a b
Right b
b)
            Maybe b
Nothing -> Maybe (Either a b)
forall a. Maybe a
Nothing
    countPrevious (Left a
a) =
        case a -> Maybe b
forall a b. (Countable a, Countable b) => a -> Maybe b
maybeRecount a
a of
            Just b
b -> Either a b -> Maybe (Either a b)
forall a. a -> Maybe a
Just (b -> Either a b
forall a b. b -> Either a b
Right b
b)
            Maybe b
Nothing -> (a -> Either a b) -> Maybe a -> Maybe (Either a b)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Either a b
forall a b. a -> Either a b
Left (a -> Maybe a
forall a. Countable a => a -> Maybe a
countPrevious a
a)
    countMaybeNext :: Maybe (Either a b) -> Maybe (Either a b)
countMaybeNext Maybe (Either a b)
Nothing =
        case Maybe b -> Maybe b
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext Maybe b
forall a. Maybe a
Nothing of
            Just b
b -> Either a b -> Maybe (Either a b)
forall a. a -> Maybe a
Just (b -> Either a b
forall a b. b -> Either a b
Right b
b)
            Maybe b
Nothing -> (a -> Either a b) -> Maybe a -> Maybe (Either a b)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Either a b
forall a b. a -> Either a b
Left (Maybe a -> Maybe a
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext Maybe a
forall a. Maybe a
Nothing)
    countMaybeNext (Just (Right b
b)) =
        case b -> Maybe a
forall a b. (Countable a, Countable b) => a -> Maybe b
maybeRecount b
b of
            Just a
a -> Either a b -> Maybe (Either a b)
forall a. a -> Maybe a
Just (a -> Either a b
forall a b. a -> Either a b
Left a
a)
            Maybe a
Nothing -> (b -> Either a b) -> Maybe b -> Maybe (Either a b)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap b -> Either a b
forall a b. b -> Either a b
Right (Maybe b -> Maybe b
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext (b -> Maybe b
forall a. a -> Maybe a
Just b
b))
    countMaybeNext (Just (Left a
a)) =
        case a -> Maybe b
forall a b. (Countable a, Countable b) => a -> Maybe b
maybeRecount a
a Maybe b -> (b -> Maybe b) -> Maybe b
forall a b. Maybe a -> (a -> Maybe b) -> Maybe b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (Maybe b -> Maybe b
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext (Maybe b -> Maybe b) -> (b -> Maybe b) -> b -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> Maybe b
forall a. a -> Maybe a
Just) of
            Just b
b -> (Either a b -> Maybe (Either a b)
forall a. a -> Maybe a
Just (b -> Either a b
forall a b. b -> Either a b
Right b
b))
            Maybe b
Nothing -> (a -> Either a b) -> Maybe a -> Maybe (Either a b)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Either a b
forall a b. a -> Either a b
Left (Maybe a -> Maybe a
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext (a -> Maybe a
forall a. a -> Maybe a
Just a
a))

countDownUp :: (Countable down, Countable up) => (down, up) -> Maybe (down, up)
countDownUp :: forall down up.
(Countable down, Countable up) =>
(down, up) -> Maybe (down, up)
countDownUp (down
down, up
up) = do
    down
down' <- down -> Maybe down
forall a. Countable a => a -> Maybe a
countPrevious down
down
    up
up' <- Maybe up -> Maybe up
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext (up -> Maybe up
forall a. a -> Maybe a
Just up
up)
    (down, up) -> Maybe (down, up)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (down
down', up
up')

countUpDown :: (Countable up, Countable down) => (up, down) -> Maybe (up, down)
countUpDown :: forall down up.
(Countable down, Countable up) =>
(down, up) -> Maybe (down, up)
countUpDown (up
up, down
down) = do
    up
up' <- Maybe up -> Maybe up
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext (up -> Maybe up
forall a. a -> Maybe a
Just up
up)
    down
down' <- down -> Maybe down
forall a. Countable a => a -> Maybe a
countPrevious down
down
    (up, down) -> Maybe (up, down)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (up
up', down
down')

finalIteration :: (a -> Maybe a) -> a -> a
finalIteration :: forall a. (a -> Maybe a) -> a -> a
finalIteration a -> Maybe a
f a
a =
    case a -> Maybe a
f a
a of
        Just a
a' -> (a -> Maybe a) -> a -> a
forall a. (a -> Maybe a) -> a -> a
finalIteration a -> Maybe a
f a
a'
        Maybe a
Nothing -> a
a

instance (Countable a, Countable b) => Countable (a, b) where
    countPrevious :: (a, b) -> Maybe (a, b)
countPrevious (a, b)
ab =
        case (a, b) -> Maybe (a, b)
forall down up.
(Countable down, Countable up) =>
(down, up) -> Maybe (down, up)
countUpDown (a, b)
ab of
            Just (a, b)
ab' -> (a, b) -> Maybe (a, b)
forall a. a -> Maybe a
Just (a, b)
ab'
            Maybe (a, b)
_ -> let
                (a
a', b
b') = ((a, b) -> Maybe (a, b)) -> (a, b) -> (a, b)
forall a. (a -> Maybe a) -> a -> a
finalIteration (a, b) -> Maybe (a, b)
forall down up.
(Countable down, Countable up) =>
(down, up) -> Maybe (down, up)
countDownUp (a, b)
ab
                in case a -> Maybe a
forall a. Countable a => a -> Maybe a
countPrevious a
a' of
                       Just a
a'' -> (a, b) -> Maybe (a, b)
forall a. a -> Maybe a
Just (a
a'', b
b')
                       Maybe a
Nothing ->
                           case b -> Maybe b
forall a. Countable a => a -> Maybe a
countPrevious b
b' of
                               Just b
b'' -> (a, b) -> Maybe (a, b)
forall a. a -> Maybe a
Just (a
a', b
b'')
                               Maybe b
Nothing -> Maybe (a, b)
forall a. Maybe a
Nothing
    countMaybeNext :: Maybe (a, b) -> Maybe (a, b)
countMaybeNext Maybe (a, b)
Nothing = do
        a
a <- Maybe a -> Maybe a
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext Maybe a
forall a. Maybe a
Nothing
        b
b <- Maybe b -> Maybe b
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext Maybe b
forall a. Maybe a
Nothing
        (a, b) -> Maybe (a, b)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
a, b
b)
    countMaybeNext (Just (a, b)
ab) =
        case (a, b) -> Maybe (a, b)
forall down up.
(Countable down, Countable up) =>
(down, up) -> Maybe (down, up)
countDownUp (a, b)
ab of
            Just (a, b)
ab' -> (a, b) -> Maybe (a, b)
forall a. a -> Maybe a
Just (a, b)
ab'
            Maybe (a, b)
_ -> let
                (a
a', b
b') = ((a, b) -> Maybe (a, b)) -> (a, b) -> (a, b)
forall a. (a -> Maybe a) -> a -> a
finalIteration (a, b) -> Maybe (a, b)
forall down up.
(Countable down, Countable up) =>
(down, up) -> Maybe (down, up)
countUpDown (a, b)
ab
                in case Maybe a -> Maybe a
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext (a -> Maybe a
forall a. a -> Maybe a
Just a
a') of
                       Just a
a'' -> (a, b) -> Maybe (a, b)
forall a. a -> Maybe a
Just (a
a'', b
b')
                       Maybe a
Nothing ->
                           case Maybe b -> Maybe b
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext (b -> Maybe b
forall a. a -> Maybe a
Just b
b') of
                               Just b
b'' -> (a, b) -> Maybe (a, b)
forall a. a -> Maybe a
Just (a
a', b
b'')
                               Maybe b
Nothing -> Maybe (a, b)
forall a. Maybe a
Nothing

-- | Values form a non-empty, possibly finite, countable sequence.
class Countable a => AtLeastOneCountable a where
    countFirst :: a

instance AtLeastOneCountable () where
    countFirst :: ()
countFirst = ()

instance AtLeastOneCountable Bool where
    countFirst :: Bool
countFirst = Bool
False

instance AtLeastOneCountable Word8 where
    countFirst :: Word8
countFirst = Word8
forall a. Bounded a => a
minBound

instance AtLeastOneCountable Word16 where
    countFirst :: Word16
countFirst = Word16
forall a. Bounded a => a
minBound

instance AtLeastOneCountable Word32 where
    countFirst :: Word32
countFirst = Word32
forall a. Bounded a => a
minBound

instance AtLeastOneCountable Word64 where
    countFirst :: Word64
countFirst = Word64
forall a. Bounded a => a
minBound

instance AtLeastOneCountable Int8 where
    countFirst :: Int8
countFirst = Int8
forall a. Bounded a => a
minBound

instance AtLeastOneCountable Int16 where
    countFirst :: Int16
countFirst = Int16
forall a. Bounded a => a
minBound

instance AtLeastOneCountable Int32 where
    countFirst :: Int32
countFirst = Int32
forall a. Bounded a => a
minBound

instance AtLeastOneCountable Int64 where
    countFirst :: Int64
countFirst = Int64
forall a. Bounded a => a
minBound

instance AtLeastOneCountable Integer where
    countFirst :: Integer
countFirst = Integer
0

instance (Countable a) => AtLeastOneCountable (Maybe a) where
    countFirst :: Maybe a
countFirst = Maybe a
forall a. Maybe a
Nothing

instance (Countable a, AtLeastOneCountable b) => AtLeastOneCountable (Either a b) where
    countFirst :: Either a b
countFirst = b -> Either a b
forall a b. b -> Either a b
Right b
forall a. AtLeastOneCountable a => a
countFirst

instance (AtLeastOneCountable a, AtLeastOneCountable b) => AtLeastOneCountable (a, b) where
    countFirst :: (a, b)
countFirst = (a
forall a. AtLeastOneCountable a => a
countFirst, b
forall a. AtLeastOneCountable a => a
countFirst)

-- | Values form an infinite countable sequence.
class (AtLeastOneCountable a) => InfiniteCountable a where
    countNext :: Maybe a -> a

instance InfiniteCountable Integer where
    countNext :: Maybe Integer -> Integer
countNext Maybe Integer
Nothing = Integer
0
    countNext (Just Integer
a)
        | Integer
a Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 = -Integer
a
    countNext (Just Integer
a) = -Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1

instance (InfiniteCountable a) => InfiniteCountable (Maybe a) where
    countNext :: Maybe (Maybe a) -> Maybe a
countNext = (Maybe a -> a) -> Maybe (Maybe a) -> Maybe a
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Maybe a -> a
forall a. InfiniteCountable a => Maybe a -> a
countNext

instance (AtLeastOneCountable a, InfiniteCountable b) => InfiniteCountable (a, b) where
    countNext :: Maybe (a, b) -> (a, b)
countNext Maybe (a, b)
Nothing = (a
forall a. AtLeastOneCountable a => a
countFirst, Maybe b -> b
forall a. InfiniteCountable a => Maybe a -> a
countNext Maybe b
forall a. Maybe a
Nothing)
    countNext (Just (a, b)
ab) =
        case (a, b) -> Maybe (a, b)
forall down up.
(Countable down, Countable up) =>
(down, up) -> Maybe (down, up)
countDownUp (a, b)
ab of
            Just (a, b)
ab' -> (a, b)
ab'
            Maybe (a, b)
_ -> let
                (a
a', b
b') = ((a, b) -> Maybe (a, b)) -> (a, b) -> (a, b)
forall a. (a -> Maybe a) -> a -> a
finalIteration (a, b) -> Maybe (a, b)
forall down up.
(Countable down, Countable up) =>
(down, up) -> Maybe (down, up)
countUpDown (a, b)
ab
                in case Maybe a -> Maybe a
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext (a -> Maybe a
forall a. a -> Maybe a
Just a
a') of
                       Just a
a'' -> (a
a'', b
b')
                       Maybe a
Nothing -> (a
a', Maybe b -> b
forall a. InfiniteCountable a => Maybe a -> a
countNext (b -> Maybe b
forall a. a -> Maybe a
Just b
b'))

recount :: (Countable a, InfiniteCountable b) => a -> b
recount :: forall a b. (Countable a, InfiniteCountable b) => a -> b
recount = Maybe b -> b
forall a. InfiniteCountable a => Maybe a -> a
countNext (Maybe b -> b) -> (a -> Maybe b) -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a -> b) -> Maybe a -> Maybe b
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
forall a b. (Countable a, InfiniteCountable b) => a -> b
recount) (Maybe a -> Maybe b) -> (a -> Maybe a) -> a -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Maybe a
forall a. Countable a => a -> Maybe a
countPrevious

instance (Countable a, InfiniteCountable b) => InfiniteCountable (Either a b) where
    countNext :: Maybe (Either a b) -> Either a b
countNext Maybe (Either a b)
Nothing = b -> Either a b
forall a b. b -> Either a b
Right (Maybe b -> b
forall a. InfiniteCountable a => Maybe a -> a
countNext Maybe b
forall a. Maybe a
Nothing)
    countNext (Just (Right b
b)) =
        case b -> Maybe a
forall a b. (Countable a, Countable b) => a -> Maybe b
maybeRecount b
b of
            Just a
a -> a -> Either a b
forall a b. a -> Either a b
Left a
a
            Maybe a
Nothing -> b -> Either a b
forall a b. b -> Either a b
Right (Maybe b -> b
forall a. InfiniteCountable a => Maybe a -> a
countNext (b -> Maybe b
forall a. a -> Maybe a
Just b
b))
    countNext (Just (Left a
a)) = b -> Either a b
forall a b. b -> Either a b
Right (Maybe b -> b
forall a. InfiniteCountable a => Maybe a -> a
countNext (a -> Maybe b
forall a b. (Countable a, InfiniteCountable b) => a -> b
recount a
a))

instance (Countable a) => Countable [a] where
    countPrevious :: [a] -> Maybe [a]
countPrevious [] = Maybe [a]
forall a. Maybe a
Nothing
    countPrevious (a
x:[a]
xs) =
        case Maybe a -> Maybe a
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext Maybe a
forall a. Maybe a
Nothing of
            Maybe a
Nothing -> a -> Maybe [a] -> Maybe [a]
forall a b. a -> b -> b
seq a
x Maybe [a]
forall a. HasCallStack => a
undefined -- x not supposed to exist
            Just a
firsta -> [a] -> Maybe [a]
forall a. a -> Maybe a
Just (a -> [a] -> [a]
pp a
x [a]
xs)
                where pp :: a -> [a] -> [a]
pp a
a [a]
r =
                          case a -> Maybe a
forall a. Countable a => a -> Maybe a
countPrevious a
a of
                              Just a
a' -> a
firsta a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (a -> [a] -> [a]
pp a
a' [a]
r)
                              Maybe a
Nothing ->
                                  case [a]
r of
                                      [] -> []
                                      a
b:[a]
r' ->
                                          case Maybe a -> Maybe a
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext (a -> Maybe a
forall a. a -> Maybe a
Just a
b) of
                                              Just a
b' -> a
b' a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
r'
                                              Maybe a
Nothing -> a
firsta a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (a -> [a] -> [a]
pp a
b [a]
r')
    countMaybeNext :: Maybe [a] -> Maybe [a]
countMaybeNext Maybe [a]
Nothing = [a] -> Maybe [a]
forall a. a -> Maybe a
Just []
    countMaybeNext (Just [a]
l) =
        case Maybe a -> Maybe a
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext Maybe a
forall a. Maybe a
Nothing of
            Maybe a
Nothing -> Maybe [a]
forall a. Maybe a
Nothing
            Just a
firsta -> [a] -> Maybe [a]
forall a. a -> Maybe a
Just ([a] -> [a]
countNext' [a]
l)
                where countNext' :: [a] -> [a]
countNext' [] = [a
firsta]
                      countNext' (a
a:[a]
r) =
                          case a -> Maybe a
forall a. Countable a => a -> Maybe a
countPrevious a
a of
                              Just a
a' -> a
firsta a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a
a' a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
r
                              Maybe a
Nothing -> [a] -> [a]
upOne ([a] -> [a]
countNext' [a]
r)
                      upOne :: [a] -> [a]
upOne [] = [a
firsta]
                      upOne (a
a:[a]
r) =
                          case Maybe a -> Maybe a
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext (a -> Maybe a
forall a. a -> Maybe a
Just a
a) of
                              Just a
a' -> a
a' a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
r
                              Maybe a
Nothing -> a
firsta a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
r

instance (Countable a) => AtLeastOneCountable [a] where
    countFirst :: [a]
countFirst = []

instance (AtLeastOneCountable a) => InfiniteCountable [a] where
    countNext :: Maybe [a] -> [a]
countNext Maybe [a]
Nothing = []
    countNext (Just [a]
l) = [a] -> [a]
forall {a}. AtLeastOneCountable a => [a] -> [a]
countNext' [a]
l
      where
        countNext' :: [a] -> [a]
countNext' [] = [a
forall a. AtLeastOneCountable a => a
countFirst]
        countNext' (a
a:[a]
r) =
            case a -> Maybe a
forall a. Countable a => a -> Maybe a
countPrevious a
a of
                Just a
a' -> a
forall a. AtLeastOneCountable a => a
countFirst a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a
a' a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
r
                Maybe a
Nothing -> [a] -> [a]
forall {a}. AtLeastOneCountable a => [a] -> [a]
upOne ([a] -> [a]
countNext' [a]
r)
        upOne :: [a] -> [a]
upOne [] = [a
forall a. AtLeastOneCountable a => a
countFirst]
        upOne (a
a:[a]
r) =
            case Maybe a -> Maybe a
forall a. Countable a => Maybe a -> Maybe a
countMaybeNext (a -> Maybe a
forall a. a -> Maybe a
Just a
a) of
                Just a
a' -> a
a' a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
r
                Maybe a
Nothing -> a
forall a. AtLeastOneCountable a => a
countFirst a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
r