-- | 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 [a] as [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 [a] as [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 Bilist a a == :: Bilist a -> Bilist a -> Bool == 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 Bilist a a <> :: Bilist a -> Bilist a -> Bilist a <> 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 a x (Bilist [a] as [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 [a] as [a] bs) 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] 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 [] [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) []