    {-
    (c) The University of Glasgow 2006
    (c) The AQUA Project, Glasgow University, 1993-1998

    -}
    {-# LANGUAGE ViewPatterns #-}
    {-# LANGUAGE PatternSynonyms #-}
    {-# LANGUAGE UnboxedTuples #-}

    -- | Provide trees (of instructions), so that lists of instructions can be
    -- appended in linear time.
    module GHC.Data.OrdList (
            OrdList, pattern NilOL, pattern ConsOL, pattern SnocOL,
            nilOL, isNilOL, unitOL, appOL, consOL, snocOL, concatOL, lastOL,
            headOL,
            mapOL, mapOL', fromOL, toOL, foldrOL, foldlOL,
            partitionOL, reverseOL, fromOLReverse, strictlyEqOL, strictlyOrdOL
    ) where

    import GHC.Prelude
    import Data.Foldable

    import GHC.Utils.Misc (strictMap)
    import GHC.Utils.Outputable
    import GHC.Utils.Panic

    import Data.List.NonEmpty (NonEmpty(..))
    import qualified Data.List.NonEmpty as NE
    import qualified Data.Semigroup as Semigroup

    infixl 5  `appOL`
    infixl 5  `snocOL`
    infixr 5  `consOL`

    data OrdList a
      = None
      | One a
      | Many (NonEmpty a)
      | Cons a (OrdList a)
      | Snoc (OrdList a) a
      | Two (OrdList a) -- Invariant: non-empty
            (OrdList a) -- Invariant: non-empty
      deriving ((forall a b. (a -> b) -> OrdList a -> OrdList b)
    -> (forall a b. a -> OrdList b -> OrdList a) -> Functor OrdList
    forall a b. a -> OrdList b -> OrdList a
    forall a b. (a -> b) -> OrdList a -> OrdList b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    $cfmap :: forall a b. (a -> b) -> OrdList a -> OrdList b
    fmap :: forall a b. (a -> b) -> OrdList a -> OrdList b
    $c<$ :: forall a b. a -> OrdList b -> OrdList a
    <$ :: forall a b. a -> OrdList b -> OrdList a
    Functor)

    instance Outputable a => Outputable (OrdList a) where
      ppr :: OrdList a -> SDoc
    ppr OrdList a
    ol = [a] -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr (OrdList a -> [a]
    forall a. OrdList a -> [a]
    fromOL OrdList a
    ol)  -- Convert to list and print that

    instance Semigroup (OrdList a) where
      <> :: OrdList a -> OrdList a -> OrdList a
    (<>) = OrdList a -> OrdList a -> OrdList a
    forall a. OrdList a -> OrdList a -> OrdList a
    appOL

    instance Monoid (OrdList a) where
      mempty :: OrdList a
    mempty = OrdList a
    forall a. OrdList a
    nilOL
      mappend :: OrdList a -> OrdList a -> OrdList a
    mappend = OrdList a -> OrdList a -> OrdList a
    forall a. Semigroup a => a -> a -> a
    (Semigroup.<>)
      mconcat :: [OrdList a] -> OrdList a
    mconcat = [OrdList a] -> OrdList a
    forall a. [OrdList a] -> OrdList a
    concatOL

    instance Foldable OrdList where
      foldr :: forall a b. (a -> b -> b) -> b -> OrdList a -> b
    foldr   = (a -> b -> b) -> b -> OrdList a -> b
    forall a b. (a -> b -> b) -> b -> OrdList a -> b
    foldrOL
      foldl' :: forall b a. (b -> a -> b) -> b -> OrdList a -> b
    foldl'  = (b -> a -> b) -> b -> OrdList a -> b
    forall b a. (b -> a -> b) -> b -> OrdList a -> b
    foldlOL
      toList :: forall a. OrdList a -> [a]
    toList  = OrdList a -> [a]
    forall a. OrdList a -> [a]
    fromOL
      null :: forall a. OrdList a -> Bool
    null    = OrdList a -> Bool
    forall a. OrdList a -> Bool
    isNilOL
      length :: forall a. OrdList a -> Int
    length  = OrdList a -> Int
    forall a. OrdList a -> Int
    lengthOL

    instance Traversable OrdList where
      traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> OrdList a -> f (OrdList b)
    traverse a -> f b
    f OrdList a
    xs = [b] -> OrdList b
    forall a. [a] -> OrdList a
    toOL ([b] -> OrdList b) -> f [b] -> f (OrdList b)
    forall (f :: * -> *) a b. Functor 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]
    traverse a -> f b
    f (OrdList a -> [a]
    forall a. OrdList a -> [a]
    fromOL OrdList a
    xs)

    nilOL    :: OrdList a
    isNilOL  :: OrdList a -> Bool

    unitOL   :: a           -> OrdList a
    snocOL   :: OrdList a   -> a         -> OrdList a
    consOL   :: a           -> OrdList a -> OrdList a
    appOL    :: OrdList a   -> OrdList a -> OrdList a
    concatOL :: [OrdList a] -> OrdList a
    headOL   :: OrdList a   -> a
    lastOL   :: OrdList a   -> a
    lengthOL :: OrdList a   -> Int

    nilOL :: forall a. OrdList a
    nilOL        = OrdList a
    forall a. OrdList a
    None
    unitOL :: forall a. a -> OrdList a
    unitOL a
    as    = a -> OrdList a
    forall a. a -> OrdList a
    One a
    as
    snocOL :: forall a. OrdList a -> a -> OrdList a
    snocOL OrdList a
    as   a
    b    = OrdList a -> a -> OrdList a
    forall a. OrdList a -> a -> OrdList a
    Snoc OrdList a
    as a
    b
    consOL :: forall a. a -> OrdList a -> OrdList a
    consOL a
    a    OrdList a
    bs   = a -> OrdList a -> OrdList a
    forall a. a -> OrdList a -> OrdList a
    Cons a
    a OrdList a
    bs
    concatOL :: forall a. [OrdList a] -> OrdList a
    concatOL [OrdList a]
    aas = (OrdList a -> OrdList a -> OrdList a)
    -> OrdList a -> [OrdList a] -> OrdList a
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr OrdList a -> OrdList a -> OrdList a
    forall a. OrdList a -> OrdList a -> OrdList a
    appOL OrdList a
    forall a. OrdList a
    None [OrdList a]
    aas

    pattern NilOL :: OrdList a
    pattern $mNilOL :: forall {r} {a}. OrdList a -> ((# #) -> r) -> ((# #) -> r) -> r
    $bNilOL :: forall a. OrdList a
    NilOL <- (isNilOL -> True) where
      NilOL = OrdList a
    forall a. OrdList a
    None

    -- | An unboxed 'Maybe' type with two unboxed fields in the 'Just' case.
    -- Useful for defining 'viewCons' and 'viewSnoc' without overhead.
    type VMaybe a b = (# (# a, b #) | (# #) #)
    pattern VJust :: a -> b -> VMaybe a b
    pattern $mVJust :: forall {r} {a} {b}.
    VMaybe a b -> (a -> b -> r) -> ((# #) -> r) -> r
    $bVJust :: forall a b. a -> b -> VMaybe a b
    VJust a b = (# (# a, b #) | #)
    pattern VNothing :: VMaybe a b
    pattern $mVNothing :: forall {r} {a} {b}. VMaybe a b -> ((# #) -> r) -> ((# #) -> r) -> r
    $bVNothing :: (# #) -> forall a b. VMaybe a b
    VNothing = (# | (# #) #)
    {-# COMPLETE VJust, VNothing #-}

    pattern ConsOL :: a -> OrdList a -> OrdList a
    pattern $mConsOL :: forall {r} {a}.
    OrdList a -> (a -> OrdList a -> r) -> ((# #) -> r) -> r
    $bConsOL :: forall a. a -> OrdList a -> OrdList a
    ConsOL x xs <- (viewCons -> VJust x xs) where
      ConsOL a
    x OrdList a
    xs = a -> OrdList a -> OrdList a
    forall a. a -> OrdList a -> OrdList a
    consOL a
    x OrdList a
    xs
    {-# COMPLETE NilOL, ConsOL #-}

    viewCons :: OrdList a -> VMaybe a (OrdList a)
    viewCons :: forall a. OrdList a -> VMaybe a (OrdList a)
    viewCons OrdList a
    None        = (# #) -> forall a b. VMaybe a b
    forall b. VMaybe (OrdList a) b
    VNothing
    viewCons (One a
    a)     = a -> OrdList a -> VMaybe a (OrdList a)
    forall a b. a -> b -> VMaybe a b
    VJust a
    a OrdList a
    forall a. OrdList a
    NilOL
    viewCons (Many (a
    a :| [])) = a -> OrdList a -> VMaybe a (OrdList a)
    forall a b. a -> b -> VMaybe a b
    VJust a
    a OrdList a
    forall a. OrdList a
    NilOL
    viewCons (Many (a
    a :| a
    b : [a]
    bs)) = a -> OrdList a -> VMaybe a (OrdList a)
    forall a b. a -> b -> VMaybe a b
    VJust a
    a (NonEmpty a -> OrdList a
    forall a. NonEmpty a -> OrdList a
    Many (a
    b a -> [a] -> NonEmpty a
    forall a. a -> [a] -> NonEmpty a
    :| [a]
    bs))
    viewCons (Cons a
    a OrdList a
    as) = a -> OrdList a -> VMaybe a (OrdList a)
    forall a b. a -> b -> VMaybe a b
    VJust a
    a OrdList a
    as
    viewCons (Snoc OrdList a
    as a
    a) = case OrdList a -> VMaybe a (OrdList a)
    forall a. OrdList a -> VMaybe a (OrdList a)
    viewCons OrdList a
    as of
      VJust a
    a' OrdList a
    as' -> a -> OrdList a -> VMaybe a (OrdList a)
    forall a b. a -> b -> VMaybe a b
    VJust a
    a' (OrdList a -> a -> OrdList a
    forall a. OrdList a -> a -> OrdList a
    Snoc OrdList a
    as' a
    a)
      VMaybe a (OrdList a)
    VNothing     -> a -> OrdList a -> VMaybe a (OrdList a)
    forall a b. a -> b -> VMaybe a b
    VJust a
    a OrdList a
    forall a. OrdList a
    NilOL
    viewCons (Two OrdList a
    as1 OrdList a
    as2) = case OrdList a -> VMaybe a (OrdList a)
    forall a. OrdList a -> VMaybe a (OrdList a)
    viewCons OrdList a
    as1 of
      VJust a
    a' OrdList a
    as1' -> a -> OrdList a -> VMaybe a (OrdList a)
    forall a b. a -> b -> VMaybe a b
    VJust a
    a' (OrdList a -> OrdList a -> OrdList a
    forall a. OrdList a -> OrdList a -> OrdList a
    Two OrdList a
    as1' OrdList a
    as2)
      VMaybe a (OrdList a)
    VNothing      -> OrdList a -> VMaybe a (OrdList a)
    forall a. OrdList a -> VMaybe a (OrdList a)
    viewCons OrdList a
    as2

    pattern SnocOL :: OrdList a -> a -> OrdList a
    pattern $mSnocOL :: forall {r} {a}.
    OrdList a -> (OrdList a -> a -> r) -> ((# #) -> r) -> r
    $bSnocOL :: forall a. OrdList a -> a -> OrdList a
    SnocOL xs x <- (viewSnoc -> VJust xs x) where
      SnocOL OrdList a
    xs a
    x = OrdList a -> a -> OrdList a
    forall a. OrdList a -> a -> OrdList a
    snocOL OrdList a
    xs a
    x
    {-# COMPLETE NilOL, SnocOL #-}

    viewSnoc :: OrdList a -> VMaybe (OrdList a) a
    viewSnoc :: forall a. OrdList a -> VMaybe (OrdList a) a
    viewSnoc OrdList a
    None        = (# #) -> forall a b. VMaybe a b
    forall b. VMaybe a b
    VNothing
    viewSnoc (One a
    a)     = OrdList a -> a -> VMaybe (OrdList a) a
    forall a b. a -> b -> VMaybe a b
    VJust OrdList a
    forall a. OrdList a
    NilOL a
    a
    viewSnoc (Many NonEmpty a
    as)   = (OrdList a -> a -> VMaybe (OrdList a) a
    forall a b. a -> b -> VMaybe a b
    `VJust` NonEmpty a -> a
    forall a. NonEmpty a -> a
    NE.last NonEmpty a
    as) (OrdList a -> VMaybe (OrdList a) a)
    -> OrdList a -> VMaybe (OrdList a) a
    forall a b. (a -> b) -> a -> b
    $ case NonEmpty a -> [a]
    forall a. NonEmpty a -> [a]
    NE.init NonEmpty a
    as of
      [] -> OrdList a
    forall a. OrdList a
    NilOL
      a
    b : [a]
    bs -> NonEmpty a -> OrdList a
    forall a. NonEmpty a -> OrdList a
    Many (a
    b a -> [a] -> NonEmpty a
    forall a. a -> [a] -> NonEmpty a
    :| [a]
    bs)
    viewSnoc (Snoc OrdList a
    as a
    a) = OrdList a -> a -> VMaybe (OrdList a) a
    forall a b. a -> b -> VMaybe a b
    VJust OrdList a
    as a
    a
    viewSnoc (Cons a
    a OrdList a
    as) = case OrdList a -> VMaybe (OrdList a) a
    forall a. OrdList a -> VMaybe (OrdList a) a
    viewSnoc OrdList a
    as of
      VJust OrdList a
    as' a
    a' -> OrdList a -> a -> VMaybe (OrdList a) a
    forall a b. a -> b -> VMaybe a b
    VJust (a -> OrdList a -> OrdList a
    forall a. a -> OrdList a -> OrdList a
    Cons a
    a OrdList a
    as') a
    a'
      VMaybe (OrdList a) a
    VNothing     -> OrdList a -> a -> VMaybe (OrdList a) a
    forall a b. a -> b -> VMaybe a b
    VJust OrdList a
    forall a. OrdList a
    NilOL a
    a
    viewSnoc (Two OrdList a
    as1 OrdList a
    as2) = case OrdList a -> VMaybe (OrdList a) a
    forall a. OrdList a -> VMaybe (OrdList a) a
    viewSnoc OrdList a
    as2 of
      VJust OrdList a
    as2' a
    a' -> OrdList a -> a -> VMaybe (OrdList a) a
    forall a b. a -> b -> VMaybe a b
    VJust (OrdList a -> OrdList a -> OrdList a
    forall a. OrdList a -> OrdList a -> OrdList a
    Two OrdList a
    as1 OrdList a
    as2') a
    a'
      VMaybe (OrdList a) a
    VNothing      -> OrdList a -> VMaybe (OrdList a) a
    forall a. OrdList a -> VMaybe (OrdList a) a
    viewSnoc OrdList a
    as1

    headOL :: forall a. OrdList a -> a
    headOL OrdList a
    None        = String -> a
    forall a. HasCallStack => String -> a
    panic String
    "headOL"
    headOL (One a
    a)     = a
    a
    headOL (Many NonEmpty a
    as)   = NonEmpty a -> a
    forall a. NonEmpty a -> a
    NE.head NonEmpty a
    as
    headOL (Cons a
    a OrdList a
    _)  = a
    a
    headOL (Snoc OrdList a
    as a
    _) = OrdList a -> a
    forall a. OrdList a -> a
    headOL OrdList a
    as
    headOL (Two OrdList a
    as OrdList a
    _)  = OrdList a -> a
    forall a. OrdList a -> a
    headOL OrdList a
    as

    lastOL :: forall a. OrdList a -> a
    lastOL OrdList a
    None        = String -> a
    forall a. HasCallStack => String -> a
    panic String
    "lastOL"
    lastOL (One a
    a)     = a
    a
    lastOL (Many NonEmpty a
    as)   = NonEmpty a -> a
    forall a. NonEmpty a -> a
    NE.last NonEmpty a
    as
    lastOL (Cons a
    _ OrdList a
    as) = OrdList a -> a
    forall a. OrdList a -> a
    lastOL OrdList a
    as
    lastOL (Snoc OrdList a
    _ a
    a)  = a
    a
    lastOL (Two OrdList a
    _ OrdList a
    as)  = OrdList a -> a
    forall a. OrdList a -> a
    lastOL OrdList a
    as

    lengthOL :: forall a. OrdList a -> Int
    lengthOL OrdList a
    None        = Int
    0
    lengthOL (One a
    _)     = Int
    1
    lengthOL (Many NonEmpty a
    as)   = NonEmpty a -> Int
    forall a. NonEmpty a -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length NonEmpty a
    as
    lengthOL (Cons a
    _ OrdList a
    as) = Int
    1 Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + OrdList a -> Int
    forall a. OrdList a -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length OrdList a
    as
    lengthOL (Snoc OrdList a
    as a
    _) = Int
    1 Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + OrdList a -> Int
    forall a. OrdList a -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length OrdList a
    as
    lengthOL (Two OrdList a
    as OrdList a
    bs) = OrdList a -> Int
    forall a. OrdList a -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length OrdList a
    as Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + OrdList a -> Int
    forall a. OrdList a -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length OrdList a
    bs

    isNilOL :: forall a. OrdList a -> Bool
    isNilOL OrdList a
    None = Bool
    True
    isNilOL OrdList a
    _    = Bool
    False

    OrdList a
    None  appOL :: forall a. OrdList a -> OrdList a -> OrdList a
    `appOL` OrdList a
    b     = OrdList a
    b
    OrdList a
    a     `appOL` OrdList a
    None  = OrdList a
    a
    One a
    a `appOL` OrdList a
    b     = a -> OrdList a -> OrdList a
    forall a. a -> OrdList a -> OrdList a
    Cons a
    a OrdList a
    b
    OrdList a
    a     `appOL` One a
    b = OrdList a -> a -> OrdList a
    forall a. OrdList a -> a -> OrdList a
    Snoc OrdList a
    a a
    b
    OrdList a
    a     `appOL` OrdList a
    b     = OrdList a -> OrdList a -> OrdList a
    forall a. OrdList a -> OrdList a -> OrdList a
    Two OrdList a
    a OrdList a
    b

    fromOL :: OrdList a -> [a]
    fromOL :: forall a. OrdList a -> [a]
    fromOL OrdList a
    a = OrdList a -> [a] -> [a]
    forall {a}. OrdList a -> [a] -> [a]
    go OrdList a
    a []
      where go :: OrdList a -> [a] -> [a]
    go OrdList a
    None       [a]
    acc = [a]
    acc
            go (One a
    a)    [a]
    acc = a
    a a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : [a]
    acc
            go (Cons a
    a OrdList a
    b) [a]
    acc = a
    a a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : OrdList a -> [a] -> [a]
    go OrdList a
    b [a]
    acc
            go (Snoc OrdList a
    a a
    b) [a]
    acc = OrdList a -> [a] -> [a]
    go OrdList a
    a (a
    ba -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    acc)
            go (Two OrdList a
    a OrdList a
    b)  [a]
    acc = OrdList a -> [a] -> [a]
    go OrdList a
    a (OrdList a -> [a] -> [a]
    go OrdList a
    b [a]
    acc)
            go (Many NonEmpty a
    xs)  [a]
    acc = NonEmpty a -> [a]
    forall a. NonEmpty a -> [a]
    NE.toList NonEmpty a
    xs [a] -> [a] -> [a]
    forall a. [a] -> [a] -> [a]
    ++ [a]
    acc

    fromOLReverse :: OrdList a -> [a]
    fromOLReverse :: forall a. OrdList a -> [a]
    fromOLReverse OrdList a
    a = OrdList a -> [a] -> [a]
    forall {a}. OrdList a -> [a] -> [a]
    go OrdList a
    a []
            -- acc is already in reverse order
      where go :: OrdList a -> [a] -> [a]
            go :: forall {a}. OrdList a -> [a] -> [a]
    go OrdList a
    None       [a]
    acc = [a]
    acc
            go (One a
    a)    [a]
    acc = a
    a a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : [a]
    acc
            go (Cons a
    a OrdList a
    b) [a]
    acc = OrdList a -> [a] -> [a]
    forall {a}. OrdList a -> [a] -> [a]
    go OrdList a
    b (a
    a a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : [a]
    acc)
            go (Snoc OrdList a
    a a
    b) [a]
    acc = a
    b a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : OrdList a -> [a] -> [a]
    forall {a}. OrdList a -> [a] -> [a]
    go OrdList a
    a [a]
    acc
            go (Two OrdList a
    a OrdList a
    b)  [a]
    acc = OrdList a -> [a] -> [a]
    forall {a}. OrdList a -> [a] -> [a]
    go OrdList a
    b (OrdList a -> [a] -> [a]
    forall {a}. OrdList a -> [a] -> [a]
    go OrdList a
    a [a]
    acc)
            go (Many NonEmpty a
    xs)  [a]
    acc = [a] -> [a]
    forall a. [a] -> [a]
    reverse (NonEmpty a -> [a]
    forall a. NonEmpty a -> [a]
    NE.toList NonEmpty a
    xs) [a] -> [a] -> [a]
    forall a. [a] -> [a] -> [a]
    ++ [a]
    acc

    mapOL :: (a -> b) -> OrdList a -> OrdList b
    mapOL :: forall a b. (a -> b) -> OrdList a -> OrdList b
    mapOL = (a -> b) -> OrdList a -> OrdList b
    forall a b. (a -> b) -> OrdList a -> OrdList b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap

    mapOL' :: (a->b) -> OrdList a -> OrdList b
    mapOL' :: forall a b. (a -> b) -> OrdList a -> OrdList b
    mapOL' a -> b
    _ OrdList a
    None        = OrdList b
    forall a. OrdList a
    None
    mapOL' a -> b
    f (One a
    x)     = b -> OrdList b
    forall a. a -> OrdList a
    One (b -> OrdList b) -> b -> OrdList b
    forall a b. (a -> b) -> a -> b
    $! a -> b
    f a
    x
    mapOL' a -> b
    f (Cons a
    x OrdList a
    xs) = let !x1 :: b
    x1 = a -> b
    f a
    x
                               !xs1 :: OrdList b
    xs1 = (a -> b) -> OrdList a -> OrdList b
    forall a b. (a -> b) -> OrdList a -> OrdList b
    mapOL' a -> b
    f OrdList a
    xs
                           in b -> OrdList b -> OrdList b
    forall a. a -> OrdList a -> OrdList a
    Cons b
    x1 OrdList b
    xs1
    mapOL' a -> b
    f (Snoc OrdList a
    xs a
    x) = let !x1 :: b
    x1 = a -> b
    f a
    x
                               !xs1 :: OrdList b
    xs1 = (a -> b) -> OrdList a -> OrdList b
    forall a b. (a -> b) -> OrdList a -> OrdList b
    mapOL' a -> b
    f OrdList a
    xs
                           in OrdList b -> b -> OrdList b
    forall a. OrdList a -> a -> OrdList a
    Snoc OrdList b
    xs1 b
    x1
    mapOL' a -> b
    f (Two OrdList a
    b1 OrdList a
    b2) = let !b1' :: OrdList b
    b1' = (a -> b) -> OrdList a -> OrdList b
    forall a b. (a -> b) -> OrdList a -> OrdList b
    mapOL' a -> b
    f OrdList a
    b1
                               !b2' :: OrdList b
    b2' = (a -> b) -> OrdList a -> OrdList b
    forall a b. (a -> b) -> OrdList a -> OrdList b
    mapOL' a -> b
    f OrdList a
    b2
                           in OrdList b -> OrdList b -> OrdList b
    forall a. OrdList a -> OrdList a -> OrdList a
    Two OrdList b
    b1' OrdList b
    b2'
    mapOL' a -> b
    f (Many (a
    x :| [a]
    xs)) = let !x1 :: b
    x1 = a -> b
    f a
    x
                                    !xs1 :: [b]
    xs1 = (a -> b) -> [a] -> [b]
    forall a b. (a -> b) -> [a] -> [b]
    strictMap a -> b
    f [a]
    xs
                                in NonEmpty b -> OrdList b
    forall a. NonEmpty a -> OrdList a
    Many (b
    x1 b -> [b] -> NonEmpty b
    forall a. a -> [a] -> NonEmpty a
    :| [b]
    xs1)

    foldrOL :: (a->b->b) -> b -> OrdList a -> b
    foldrOL :: forall a b. (a -> b -> b) -> b -> OrdList a -> b
    foldrOL a -> b -> b
    _ b
    z OrdList a
    None        = b
    z
    foldrOL a -> b -> b
    k b
    z (One a
    x)     = a -> b -> b
    k a
    x b
    z
    foldrOL a -> b -> b
    k b
    z (Cons a
    x OrdList a
    xs) = a -> b -> b
    k a
    x ((a -> b -> b) -> b -> OrdList a -> b
    forall a b. (a -> b -> b) -> b -> OrdList a -> b
    foldrOL a -> b -> b
    k b
    z OrdList a
    xs)
    foldrOL a -> b -> b
    k b
    z (Snoc OrdList a
    xs a
    x) = (a -> b -> b) -> b -> OrdList a -> b
    forall a b. (a -> b -> b) -> b -> OrdList a -> b
    foldrOL a -> b -> b
    k (a -> b -> b
    k a
    x b
    z) OrdList a
    xs
    foldrOL a -> b -> b
    k b
    z (Two OrdList a
    b1 OrdList a
    b2) = (a -> b -> b) -> b -> OrdList a -> b
    forall a b. (a -> b -> b) -> b -> OrdList a -> b
    foldrOL a -> b -> b
    k ((a -> b -> b) -> b -> OrdList a -> b
    forall a b. (a -> b -> b) -> b -> OrdList a -> b
    foldrOL a -> b -> b
    k b
    z OrdList a
    b2) OrdList a
    b1
    foldrOL a -> b -> b
    k b
    z (Many NonEmpty a
    xs)   = (a -> b -> b) -> b -> NonEmpty a -> b
    forall a b. (a -> b -> b) -> b -> NonEmpty a -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr a -> b -> b
    k b
    z NonEmpty a
    xs

    -- | Strict left fold.
    foldlOL :: (b->a->b) -> b -> OrdList a -> b
    foldlOL :: forall b a. (b -> a -> b) -> b -> OrdList a -> b
    foldlOL b -> a -> b
    _ b
    z OrdList a
    None        = b
    z
    foldlOL b -> a -> b
    k b
    z (One a
    x)     = b -> a -> b
    k b
    z a
    x
    foldlOL b -> a -> b
    k b
    z (Cons a
    x OrdList a
    xs) = let !z' :: b
    z' = (b -> a -> b
    k b
    z a
    x) in (b -> a -> b) -> b -> OrdList a -> b
    forall b a. (b -> a -> b) -> b -> OrdList a -> b
    foldlOL b -> a -> b
    k b
    z' OrdList a
    xs
    foldlOL b -> a -> b
    k b
    z (Snoc OrdList a
    xs a
    x) = let !z' :: b
    z' = ((b -> a -> b) -> b -> OrdList a -> b
    forall b a. (b -> a -> b) -> b -> OrdList a -> b
    foldlOL b -> a -> b
    k b
    z OrdList a
    xs) in b -> a -> b
    k b
    z' a
    x
    foldlOL b -> a -> b
    k b
    z (Two OrdList a
    b1 OrdList a
    b2) = let !z' :: b
    z' = ((b -> a -> b) -> b -> OrdList a -> b
    forall b a. (b -> a -> b) -> b -> OrdList a -> b
    foldlOL b -> a -> b
    k b
    z OrdList a
    b1) in (b -> a -> b) -> b -> OrdList a -> b
    forall b a. (b -> a -> b) -> b -> OrdList a -> b
    foldlOL b -> a -> b
    k b
    z' OrdList a
    b2
    foldlOL b -> a -> b
    k b
    z (Many NonEmpty a
    xs)   = (b -> a -> b) -> b -> NonEmpty a -> b
    forall b a. (b -> a -> b) -> b -> NonEmpty a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' b -> a -> b
    k b
    z NonEmpty a
    xs

    partitionOL :: (a -> Bool) -> OrdList a -> (OrdList a, OrdList a)
    partitionOL :: forall a. (a -> Bool) -> OrdList a -> (OrdList a, OrdList a)
    partitionOL a -> Bool
    _ OrdList a
    None = (OrdList a
    forall a. OrdList a
    None,OrdList a
    forall a. OrdList a
    None)
    partitionOL a -> Bool
    f (One a
    x)
      | a -> Bool
    f a
    x       = (a -> OrdList a
    forall a. a -> OrdList a
    One a
    x, OrdList a
    forall a. OrdList a
    None)
      | Bool
    otherwise = (OrdList a
    forall a. OrdList a
    None, a -> OrdList a
    forall a. a -> OrdList a
    One a
    x)
    partitionOL a -> Bool
    f (Two OrdList a
    xs OrdList a
    ys) = (OrdList a -> OrdList a -> OrdList a
    forall a. OrdList a -> OrdList a -> OrdList a
    Two OrdList a
    ls1 OrdList a
    ls2, OrdList a -> OrdList a -> OrdList a
    forall a. OrdList a -> OrdList a -> OrdList a
    Two OrdList a
    rs1 OrdList a
    rs2)
      where !(!OrdList a
    ls1,!OrdList a
    rs1) = (a -> Bool) -> OrdList a -> (OrdList a, OrdList a)
    forall a. (a -> Bool) -> OrdList a -> (OrdList a, OrdList a)
    partitionOL a -> Bool
    f OrdList a
    xs
            !(!OrdList a
    ls2,!OrdList a
    rs2) = (a -> Bool) -> OrdList a -> (OrdList a, OrdList a)
    forall a. (a -> Bool) -> OrdList a -> (OrdList a, OrdList a)
    partitionOL a -> Bool
    f OrdList a
    ys
    partitionOL a -> Bool
    f (Cons a
    x OrdList a
    xs)
      | a -> Bool
    f a
    x       = (a -> OrdList a -> OrdList a
    forall a. a -> OrdList a -> OrdList a
    Cons a
    x OrdList a
    ls, OrdList a
    rs)
      | Bool
    otherwise = (OrdList a
    ls, a -> OrdList a -> OrdList a
    forall a. a -> OrdList a -> OrdList a
    Cons a
    x OrdList a
    rs)
      where !(!OrdList a
    ls,!OrdList a
    rs) = (a -> Bool) -> OrdList a -> (OrdList a, OrdList a)
    forall a. (a -> Bool) -> OrdList a -> (OrdList a, OrdList a)
    partitionOL a -> Bool
    f OrdList a
    xs
    partitionOL a -> Bool
    f (Snoc OrdList a
    xs a
    x)
      | a -> Bool
    f a
    x       = (OrdList a -> a -> OrdList a
    forall a. OrdList a -> a -> OrdList a
    Snoc OrdList a
    ls a
    x, OrdList a
    rs)
      | Bool
    otherwise = (OrdList a
    ls, OrdList a -> a -> OrdList a
    forall a. OrdList a -> a -> OrdList a
    Snoc OrdList a
    rs a
    x)
      where !(!OrdList a
    ls,!OrdList a
    rs) = (a -> Bool) -> OrdList a -> (OrdList a, OrdList a)
    forall a. (a -> Bool) -> OrdList a -> (OrdList a, OrdList a)
    partitionOL a -> Bool
    f OrdList a
    xs
    partitionOL a -> Bool
    f (Many NonEmpty a
    xs) = ([a] -> OrdList a
    forall a. [a] -> OrdList a
    toOL [a]
    ls, [a] -> OrdList a
    forall a. [a] -> OrdList a
    toOL [a]
    rs)
      where !(![a]
    ls,![a]
    rs) = (a -> Bool) -> NonEmpty a -> ([a], [a])
    forall a. (a -> Bool) -> NonEmpty a -> ([a], [a])
    NE.partition a -> Bool
    f NonEmpty a
    xs

    toOL :: [a] -> OrdList a
    toOL :: forall a. [a] -> OrdList a
    toOL [] = OrdList a
    forall a. OrdList a
    None
    toOL [a
    x] = a -> OrdList a
    forall a. a -> OrdList a
    One a
    x
    toOL (a
    x : [a]
    xs) = NonEmpty a -> OrdList a
    forall a. NonEmpty a -> OrdList a
    Many (a
    x a -> [a] -> NonEmpty a
    forall a. a -> [a] -> NonEmpty a
    :| [a]
    xs)

    reverseOL :: OrdList a -> OrdList a
    reverseOL :: forall a. OrdList a -> OrdList a
    reverseOL OrdList a
    None = OrdList a
    forall a. OrdList a
    None
    reverseOL (One a
    x) = a -> OrdList a
    forall a. a -> OrdList a
    One a
    x
    reverseOL (Cons a
    a OrdList a
    b) = OrdList a -> a -> OrdList a
    forall a. OrdList a -> a -> OrdList a
    Snoc (OrdList a -> OrdList a
    forall a. OrdList a -> OrdList a
    reverseOL OrdList a
    b) a
    a
    reverseOL (Snoc OrdList a
    a a
    b) = a -> OrdList a -> OrdList a
    forall a. a -> OrdList a -> OrdList a
    Cons a
    b (OrdList a -> OrdList a
    forall a. OrdList a -> OrdList a
    reverseOL OrdList a
    a)
    reverseOL (Two OrdList a
    a OrdList a
    b)  = OrdList a -> OrdList a -> OrdList a
    forall a. OrdList a -> OrdList a -> OrdList a
    Two (OrdList a -> OrdList a
    forall a. OrdList a -> OrdList a
    reverseOL OrdList a
    b) (OrdList a -> OrdList a
    forall a. OrdList a -> OrdList a
    reverseOL OrdList a
    a)
    reverseOL (Many NonEmpty a
    xs)  = NonEmpty a -> OrdList a
    forall a. NonEmpty a -> OrdList a
    Many (NonEmpty a -> NonEmpty a
    forall a. NonEmpty a -> NonEmpty a
    NE.reverse NonEmpty a
    xs)

    -- | Compare not only the values but also the structure of two lists
    strictlyEqOL :: Eq a => OrdList a   -> OrdList a -> Bool
    strictlyEqOL :: forall a. Eq a => OrdList a -> OrdList a -> Bool
    strictlyEqOL OrdList a
    None         OrdList a
    None       = Bool
    True
    strictlyEqOL (One a
    x)     (One a
    y)     = a
    x a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    y
    strictlyEqOL (Cons a
    a OrdList a
    as) (Cons a
    b OrdList a
    bs) = a
    a a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    b Bool -> Bool -> Bool
    && OrdList a
    as OrdList a -> OrdList a -> Bool
    forall a. Eq a => OrdList a -> OrdList a -> Bool
    `strictlyEqOL` OrdList a
    bs
    strictlyEqOL (Snoc OrdList a
    as a
    a) (Snoc OrdList a
    bs a
    b) = a
    a a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    b Bool -> Bool -> Bool
    && OrdList a
    as OrdList a -> OrdList a -> Bool
    forall a. Eq a => OrdList a -> OrdList a -> Bool
    `strictlyEqOL` OrdList a
    bs
    strictlyEqOL (Two OrdList a
    a1 OrdList a
    a2) (Two OrdList a
    b1 OrdList a
    b2) = OrdList a
    a1 OrdList a -> OrdList a -> Bool
    forall a. Eq a => OrdList a -> OrdList a -> Bool
    `strictlyEqOL` OrdList a
    b1 Bool -> Bool -> Bool
    && OrdList a
    a2 OrdList a -> OrdList a -> Bool
    forall a. Eq a => OrdList a -> OrdList a -> Bool
    `strictlyEqOL` OrdList a
    b2
    strictlyEqOL (Many NonEmpty a
    as)   (Many NonEmpty a
    bs)   = NonEmpty a
    as NonEmpty a -> NonEmpty a -> Bool
    forall a. Eq a => a -> a -> Bool
    == NonEmpty a
    bs
    strictlyEqOL OrdList a
    _            OrdList a
    _          = Bool
    False

    -- | Compare not only the values but also the structure of two lists
    strictlyOrdOL :: Ord a => OrdList a   -> OrdList a -> Ordering
    strictlyOrdOL :: forall a. Ord a => OrdList a -> OrdList a -> Ordering
    strictlyOrdOL OrdList a
    None         OrdList a
    None       = Ordering
    EQ
    strictlyOrdOL OrdList a
    None         OrdList a
    _          = Ordering
    LT
    strictlyOrdOL (One a
    x)     (One a
    y)     = a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    x a
    y
    strictlyOrdOL (One a
    _)      OrdList a
    _          = Ordering
    LT
    strictlyOrdOL (Cons a
    a OrdList a
    as) (Cons a
    b OrdList a
    bs) =
      a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    a a
    b Ordering -> Ordering -> Ordering
    forall a. Monoid a => a -> a -> a
    `mappend` OrdList a -> OrdList a -> Ordering
    forall a. Ord a => OrdList a -> OrdList a -> Ordering
    strictlyOrdOL OrdList a
    as OrdList a
    bs
    strictlyOrdOL (Cons a
    _ OrdList a
    _)   OrdList a
    _          = Ordering
    LT
    strictlyOrdOL (Snoc OrdList a
    as a
    a) (Snoc OrdList a
    bs a
    b) =
      a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    a a
    b Ordering -> Ordering -> Ordering
    forall a. Monoid a => a -> a -> a
    `mappend` OrdList a -> OrdList a -> Ordering
    forall a. Ord a => OrdList a -> OrdList a -> Ordering
    strictlyOrdOL OrdList a
    as OrdList a
    bs
    strictlyOrdOL (Snoc OrdList a
    _ a
    _)   OrdList a
    _          = Ordering
    LT
    strictlyOrdOL (Two OrdList a
    a1 OrdList a
    a2) (Two OrdList a
    b1 OrdList a
    b2) =
      (OrdList a -> OrdList a -> Ordering
    forall a. Ord a => OrdList a -> OrdList a -> Ordering
    strictlyOrdOL OrdList a
    a1 OrdList a
    b1) Ordering -> Ordering -> Ordering
    forall a. Monoid a => a -> a -> a
    `mappend` (OrdList a -> OrdList a -> Ordering
    forall a. Ord a => OrdList a -> OrdList a -> Ordering
    strictlyOrdOL OrdList a
    a2 OrdList a
    b2)
    strictlyOrdOL (Two OrdList a
    _ OrdList a
    _)    OrdList a
    _          = Ordering
    LT
    strictlyOrdOL (Many NonEmpty a
    as)   (Many NonEmpty a
    bs)   = NonEmpty a -> NonEmpty a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare NonEmpty a
    as NonEmpty a
    bs
    strictlyOrdOL (Many NonEmpty a
    _ )   OrdList a
    _           = Ordering
    GT