{-# LANGUAGE GeneralizedNewtypeDeriving #-}
module Internal.SnocList
    ( SnocList
    , fromList
    , empty
    , snoc
    , singleton
    ) where

import Data.Foldable
import Data.Hashable (Hashable)

-- | A 'SnocList' is just a list, but with efficient appending instead of
-- prepending. The indended use case is when you want to append a bunch of
-- things to a list, and then get the final list to work with.
--
-- A standard trick for this is to cons each element onto the *front* of
-- the list, and then reverse the list before processing. A SnocList
-- just packages up this trick so you can't forget to do the reverse.
newtype SnocList a = SnocList [a]
    deriving(SnocList a -> SnocList a -> Bool
(SnocList a -> SnocList a -> Bool)
-> (SnocList a -> SnocList a -> Bool) -> Eq (SnocList a)
forall a. Eq a => SnocList a -> SnocList a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: SnocList a -> SnocList a -> Bool
$c/= :: forall a. Eq a => SnocList a -> SnocList a -> Bool
== :: SnocList a -> SnocList a -> Bool
$c== :: forall a. Eq a => SnocList a -> SnocList a -> Bool
Eq, Int -> SnocList a -> Int
SnocList a -> Int
(Int -> SnocList a -> Int)
-> (SnocList a -> Int) -> Hashable (SnocList a)
forall a. Hashable a => Int -> SnocList a -> Int
forall a. Hashable a => SnocList a -> Int
forall a. (Int -> a -> Int) -> (a -> Int) -> Hashable a
hash :: SnocList a -> Int
$chash :: forall a. Hashable a => SnocList a -> Int
hashWithSalt :: Int -> SnocList a -> Int
$chashWithSalt :: forall a. Hashable a => Int -> SnocList a -> Int
Hashable)

-- | Convert a list to a 'SnocList'. O(n)
fromList :: [a] -> SnocList a
fromList :: [a] -> SnocList a
fromList = [a] -> SnocList a
forall a. [a] -> SnocList a
SnocList ([a] -> SnocList a) -> ([a] -> [a]) -> [a] -> SnocList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. [a] -> [a]
reverse

-- | A one-element 'SnocList'.
singleton :: a -> SnocList a
singleton :: a -> SnocList a
singleton a
x = [a] -> SnocList a
forall a. [a] -> SnocList a
SnocList [a
x]

-- | The empty 'SnocList'.
empty :: SnocList a
empty :: SnocList a
empty = [a] -> SnocList a
forall a. [a] -> SnocList a
SnocList []

-- | Append a value to the 'SnocList'. A note on the name: 'snoc' is @cons@
-- backwards.
snoc :: SnocList a -> a -> SnocList a
snoc :: SnocList a -> a -> SnocList a
snoc (SnocList [a]
xs) a
x = [a] -> SnocList a
forall a. [a] -> SnocList a
SnocList (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)

instance Foldable SnocList where
    foldMap :: (a -> m) -> SnocList a -> m
foldMap a -> m
f = (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f ([a] -> m) -> (SnocList a -> [a]) -> SnocList a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SnocList a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList
    toList :: SnocList a -> [a]
toList (SnocList [a]
xs) = [a] -> [a]
forall a. [a] -> [a]
reverse [a]
xs

instance Semigroup (SnocList a) where
    (SnocList [a]
l) <> :: SnocList a -> SnocList a -> SnocList a
<> (SnocList [a]
r) = [a] -> SnocList a
forall a. [a] -> SnocList a
SnocList ([a]
r [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> [a]
l)

instance Monoid (SnocList a) where
    mempty :: SnocList a
mempty = SnocList a
forall a. SnocList a
empty