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

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

#include "exp_imp.inc"

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

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

type Triple a = (a,a,a)

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

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

#include "sequence.inc"

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