    -- | 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 (Semigroup(..))
    import Data.Monoid hiding ((<>))
    import Prelude

    data Bilist a = Bilist [a] [a]

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

    isEmpty :: Bilist a -> Bool
    isEmpty (Bilist as bs) = null as && null bs

    instance Eq a => Eq (Bilist a) where
        a == b = toList a == toList b

    instance Semigroup (Bilist a) where
        a <> b = Bilist (toList a ++ toList b) []

    instance Monoid (Bilist a) where
        mempty = Bilist [] []
        mappend = (<>)

    cons :: a -> Bilist a -> Bilist a
    cons x (Bilist as bs) = Bilist (x:as) bs

    snoc :: Bilist a -> a -> Bilist a
    snoc (Bilist as bs) x = Bilist as (x:bs)

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