haskell/zap/lib/Internal/SnocList.hs

{-# 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 (Eq, Hashable)

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

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

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

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

instance Foldable SnocList where
  foldMap f = foldMap f . toList
  toList (SnocList xs) = reverse xs

instance Semigroup (SnocList a) where
  (SnocList l) <> (SnocList r) = SnocList (r <> l)

instance Monoid (SnocList a) where
  mempty = empty