-- | Lazy quaternary random-access lists.
--
-- This module is intended to be imported qualified.
--

{-# LANGUAGE CPP, BangPatterns, PatternSynonyms, PatternGuards #-}
module Data.Nested.Seq.Quaternary.Lazy 

#include "exp_imp.inc"

--------------------------------------------------------------------------------

-- | The lazy sequence type.
--
-- The underlying (nested) data structure corresponds to the quaternary
-- representation of the length of the list. It looks like this:
--
-- > data Seq a
-- >   = Nil
-- >   | Zero        (Seq (a,a,a,a))
-- >   | One       a (Seq (a,a,a,a))
-- >   | Two     a a (Seq (a,a,a,a))
-- >   | Three a a a (Seq (a,a,a,a))
--
-- Furthermore we maintain the invariant that @Zero Nil@ never appears.
--
data Seq a 
  = Nil                  
  | ZZ      (Seq (a,a,a,a)) 
  | O     a (Seq (a,a,a,a)) 
  | T   a a (Seq (a,a,a,a))
  | D a a a (Seq (a,a,a,a))
#ifdef TESTING
  deriving Show
#endif

type Quad a = (a,a,a,a)

pattern Quad :: a -> a -> a -> a -> Quad a
pattern Quad x y z w = (x,y,z,w)

--------------------------------------------------------------------------------

#include "sequence.inc"

--------------------------------------------------------------------------------