{-# 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
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
forall a. Eq a -> (Int -> a -> Int) -> (a -> Int) -> Hashable a
forall {a}. Hashable a => Eq (SnocList a)
forall a. Hashable a => Int -> SnocList a -> Int
forall a. Hashable a => SnocList a -> Int
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 :: forall a. [a] -> SnocList a
fromList = forall a. [a] -> SnocList a
SnocList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. [a] -> [a]
reverse

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

-- | The empty 'SnocList'.
empty :: SnocList a
empty :: forall a. SnocList a
empty = 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 :: forall a. SnocList a -> a -> SnocList a
snoc (SnocList [a]
xs) a
x = forall a. [a] -> SnocList a
SnocList (a
x forall a. a -> [a] -> [a]
: [a]
xs)

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

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

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