    -- | List type that supports O(1) amortized 'cons', 'snoc', 'uncons' and 'isEmpty'.
    module General.Bilist(
        Bilist, cons, snoc, uncons, toList, isEmpty
        ) where

    import Data.Semigroup
    import Prelude

    data Bilist a = Bilist [a] [a]

    toList :: Bilist a -> [a]
    toList :: Bilist a -> [a]
    toList (Bilist as :: [a]
    as bs :: [a]
    bs) = [a]
    as [a] -> [a] -> [a]
    forall a. [a] -> [a] -> [a]
    ++ [a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    bs

    isEmpty :: Bilist a -> Bool
    isEmpty :: Bilist a -> Bool
    isEmpty (Bilist as :: [a]
    as bs :: [a]
    bs) = [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null [a]
    as Bool -> Bool -> Bool
    && [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null [a]
    bs

    instance Eq a => Eq (Bilist a) where
        a :: Bilist a
    a == :: Bilist a -> Bilist a -> Bool
    == b :: Bilist a
    b = Bilist a -> [a]
    forall a. Bilist a -> [a]
    toList Bilist a
    a [a] -> [a] -> Bool
    forall a. Eq a => a -> a -> Bool
    == Bilist a -> [a]
    forall a. Bilist a -> [a]
    toList Bilist a
    b

    instance Semigroup (Bilist a) where
        a :: Bilist a
    a <> :: Bilist a -> Bilist a -> Bilist a
    <> b :: Bilist a
    b = [a] -> [a] -> Bilist a
    forall a. [a] -> [a] -> Bilist a
    Bilist (Bilist a -> [a]
    forall a. Bilist a -> [a]
    toList Bilist a
    a [a] -> [a] -> [a]
    forall a. [a] -> [a] -> [a]
    ++ Bilist a -> [a]
    forall a. Bilist a -> [a]
    toList Bilist a
    b) []

    instance Monoid (Bilist a) where
        mempty :: Bilist a
    mempty = [a] -> [a] -> Bilist a
    forall a. [a] -> [a] -> Bilist a
    Bilist [] []
        mappend :: Bilist a -> Bilist a -> Bilist a
    mappend = Bilist a -> Bilist a -> Bilist a
    forall a. Semigroup a => a -> a -> a
    (<>)

    cons :: a -> Bilist a -> Bilist a
    cons :: a -> Bilist a -> Bilist a
    cons x :: a
    x (Bilist as :: [a]
    as bs :: [a]
    bs) = [a] -> [a] -> Bilist a
    forall a. [a] -> [a] -> Bilist a
    Bilist (a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    as) [a]
    bs

    snoc :: Bilist a -> a -> Bilist a
    snoc :: Bilist a -> a -> Bilist a
    snoc (Bilist as :: [a]
    as bs :: [a]
    bs) x :: a
    x = [a] -> [a] -> Bilist a
    forall a. [a] -> [a] -> Bilist a
    Bilist [a]
    as (a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    bs)

    uncons :: Bilist a -> Maybe (a, Bilist a)
    uncons :: Bilist a -> Maybe (a, Bilist a)
    uncons (Bilist [] []) = Maybe (a, Bilist a)
    forall a. Maybe a
    Nothing
    uncons (Bilist (a :: a
    a:as :: [a]
    as) bs :: [a]
    bs) = (a, Bilist a) -> Maybe (a, Bilist a)
    forall a. a -> Maybe a
    Just (a
    a, [a] -> [a] -> Bilist a
    forall a. [a] -> [a] -> Bilist a
    Bilist [a]
    as [a]
    bs)
    uncons (Bilist [] bs :: [a]
    bs) = Bilist a -> Maybe (a, Bilist a)
    forall a. Bilist a -> Maybe (a, Bilist a)
    uncons (Bilist a -> Maybe (a, Bilist a))
    -> Bilist a -> Maybe (a, Bilist a)
    forall a b. (a -> b) -> a -> b
    $ [a] -> [a] -> Bilist a
    forall a. [a] -> [a] -> Bilist a
    Bilist ([a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    bs) []