-- | 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) []