List of any `DataKind` in GADT

1
votes

Disclaimer

GADTs & DataKinds are unexplored territory for me, so some of the limitations and capabilities of them are unknown to me.

The Question

So I'm writing an AST for a JavaScript code emitter, and I've identified one edge case between expressions and that is that they can either be a reference or not. So I've used GADTS and datakinds to type this aspect of JavaScript expression semantics. The ast looks something like this.

Subset of the expression AST

-- at the moment I'm just using a bool to identify if the expression 
-- behaves as an reference, but I'll probably change it due to the fact
-- a bool is pretty vague

data JSExp :: Bool -> * where

  JSNumber :: Double -> JSExp False
  JSBool :: Bool -> JSExp False

  JSReference :: Text -> JSExp True
  JSProperty :: JSExp a -> Text -> JSExp True
  JSAssign :: JSExp True -> JSExp b -> JSExp b

This looks all fine and dandy, because an assignment expression requires the first expression to be a reference like a property expression ("test".shadyProperty) or a reference/identifier.

The problem

Now I want to add an array literal expression, in JavaScript it shouldn't matter what is in this list so lists like this are legal

[a, 1, true, a.b]

In my AST however this is not legal because there are multiple types in the list

data JSExp :: Bool -> * where

  -- ...

  JSArray :: [JSExp ???] -> JSExp False

let aref = JSReference "a"
in  JSArray [aref, JSNumber 2, JSBool True, JSProp aref "b"]

What goes in the place of ??? for the type? A similar problem occurs when I want to build out a constructor for JSObject's and JSFunctionCall's, as these are also expressions.

Idris's soultion

In Idris ??? would look something like this.

data JSExp : Bool -> Type where

  JSArray : List (JSExp _) -> JSExp False
  JSNumber : Float -> JSExp False
  JSBool : Bool -> JSExp False

  -- ...

Potenial soultions

Wrapping type

One soultion that isn't like the Idris one, would to have a wrapper type like this

data JSExpWrap = Refs (JSExp True) | NoRef (JSExp False)

This would make the api of my library gross and it's not what I'm looking for.

In Summary

I'm looking for the equivalent that's found in Idris, and an explanation of the implications of the solution. If there's no equivalent, a solution of the next best thing is what I'm looking for.

1
haskellgadtdata-kinds

1 Answers

6
votes

You can use existentials:

{-# LANGUAGE GADTs, DataKinds, PolyKinds #-}

data Exists :: (k -> *) -> * where
  This :: p x -> Exists p

data JSExp :: Bool -> * where
  ...
  JSArray :: [Exists JSExp] -> JSExp False

test = let aref = JSReference "a"
       in  JSArray [This aref, This (JSNumber 2), This (JSBool True), This (JSProperty aref "b")]

Or with some sugar:

infixr 5 !:
(!:) :: p x -> [Exists p] -> [Exists p]
x !: xs = This x : xs

test = let aref = JSReference "a"
       in  JSArray $ aref !: JSNumber 2 !: JSBool True !: JSProperty aref "b" !: []