Enable multi-value Variants to remove unneeded runtime boxing

[JordanMartinez]

Right now, a Variant only permits a single value to be associated with a tag:

newtype VariantRep a = VariantRep
  { type :: String
  , value :: a
  }

foreign import data Variant :: Row Type -> Type

data OneOrPair0
  = One Int
  | Pair Int Int

type OneOrPair1 = Variant 
  ( one :: Int
  , pair :: Tuple Int Int
  )

If one wants to define a Variant-based List type, they pay for an extra level of boxing:

newtype List a = List (
  Variant 
    ( nil :: Unit
    -- extra nesting occurs here due to usage of 
    -- `Tuple` to store 2 args
    , cons :: Tuple a (List a)
    )
  )

_nil = Proxy :: Proxy "nil"
_cons = Proxy :: Proxy "cons"

nil = List $ V.inj _nil unit
cons head tail = List $ V.inj cons_ $ Tuple head tail

cons12 = cons 1 $ cons 2 nil
{-
which has the following runtime representation on JS:

{ type: "cons"
, value:
   { tag: "Tuple" -- extra nesting
   , value0: 1
   , value1: 
      { type: "cons"
      , value:
          { tag: "Tuple" -- extra nesting
          , value0: 2
          , value1:
              { type: "nil"
              , value: undefined
              }
          }
      }
   }
}
-}

as opposed to just using List directly:

cons12 = Cons 1 $ Cons 2 Nil
{-
{ type: "Cons"
, value0: 1
, value1:
   { tag: "Cons"
   , value0: 2
   , value1: 
      { type: "Nil"
      }
   }
}
-}

AFAICT, Variant could denest this extra boxing by using the following representation, which I call Variance to distinguish it from the current Variant. I show both Variant and Variance below to show the small change made:

newtype VariantRep a = VariantRep
  { type :: String
  , value :: a
  }

newtype VarianceRep r = VarianceRep
  { __ctorTag :: String
  | r
  }

foreign import data Variant ::  Row      Type  -> Type
foreign import data Variance :: Row (Row Type) -> Type

data OneOrPair0
  = One Int
  | Pair Int Int

type OneOrPair1 = Variant 
  ( one :: Int
  , pair :: Tuple Int Int
  )
type OneOrPair2 = Variance 
  ( one :: (int :: Int)
  , pair :: (fst :: Int, snd :: Int)
  )

pairVariant :: OneOrPair1
pairVariant = V.inj _pair $ Tuple 1 2
{-
Runtime representation:

{ type: "pair"
, value:
    { tag: "Tuple"
    , value0: 1
    , value1: 2
    }
}
-}

pairVariance :: OneOrPair2
pairVariance = Variance.inj _pair { fst: 1, snd: 2 }
{-
Runtime representation:

{ __ctorTag: "pair"
, fst: 1
, snd: 2
}
-}

Variance.inj is implemented as:

inj
  :: forall sym ctorRows ctorsTail ctorsAll
   . Row.Lacks "__ctorTag" ctorRows
  => Row.Cons sym ctorRows ctorsTail ctorsAll
  => IsSymbol sym
  => Proxy sym
  -> { | ctorRows }
  -> Variance ctorsAll
inj p value = coerceV $ VarianceRep $ Record.insert __ctorTag (reflectSymbol p) value
  where
  coerceV :: VarianceRep ctorRows → Variance ctorsAll
  coerceV = unsafeCoerce

Similarly, Variance.on is implemented as below. Notably, the entire representation is passed to the function so as not to duplicate the record without the __ctorTag field:

on
  :: forall sym ctorRows remaining all b
   . Row.Cons sym ctorRows remaining all
  => Reflectable sym String
  => Proxy sym
  -> ({ __ctorTag :: String | ctorRows } -> b)
  -> (Variance remaining -> b)
  -> Variance all
  -> b
on p f g r = case coerceR r of
  VarianceRep rep | rep.__tag == reflectSymbol p -> f rep
  _ -> g (coerceTail r)
  where
  coerceR :: Variance all -> VarianceRep ctorRows
  coerceR = unsafeCoerce

  coerceTail :: Variance all -> Variance remaining
  coerceTail = unsafeCoerce

By using the above representation, it enables the following Variance-based List type:

type NIL :: forall k. Row (Row k) -> Row (Row k)
type NIL r = (nil :: () | r)
_nil = Proxy :: Proxy "nil"

type CONS :: forall k. k -> k -> Row (Row k) -> Row (Row k)
type CONS a tail r = (cons :: (head :: a, tail :: tail) | r)
_cons = Proxy :: Proxy "cons"

newtype List :: Type -> Type
newtype List a = List
  (Variance 
    ( nil :: ()
    , cons :: (head :: a, tail :: List a)
    )
  )

Besides the smaller boxing, the Nil case also doesn't specify an unused value as it's runtime representation is just { __ctorTag: "nil" }. If one wanted to remove even that boxing and just have the string "Nil" for constructors that have no arguments, then FFI would need to be added that does a typeof x === "string" check.