How to create a typed toy language environment mapping usign GADT and Data.Map?

Question

I'm playing with Haskell, the idea were to create a toy language with help of GADTs. Interpreters usually have an environment mapping that maps variables names to values.

I have basically two types in my toy language int and bool represented by I 10 and B True for example.

The problem is that I can't create a map that hold both of these, here is my code

{-# LANGUAGE GADTs, RankNTypes #-}

module Foo where

import qualified Data.Map as M
import Data.Maybe

data Expr a where
  V :: Char -> Expr a
  B :: Bool -> Expr Bool
  I :: Int -> Expr Int
  If :: Expr Bool -> Expr a -> Expr a -> Expr a

type Env a = M.Map Char (Expr a)

env = M.fromList [('x', B True), ('y', I 10)]
-- Error here                      ----^^^^
-- [typecheck -Wdeferred-type-errors] [E] • Couldn't match type ‘Int’ with ‘Bool’
--   Expected type: Expr Bool
--     Actual type: Expr Int
-- • In the expression: I 10
--   In the expression: ('y', I 10)
--   In the first argument of ‘M.fromList’, namely
--     ‘[('x', B True), ('y', I 10)]’

How can I create such mapping?

Is there any reason you can’t just make each element an Either (Expr Int) (Expr Bool)? But if not, you can use existential types: newtype SomeExpr = forall a. SomeExpr (Expr a), then make it a list of SomeExprs. — bradrn
Besides having only Int and Book in this case I would like to use more types in fufure, I will try the new type solution thanks — geckos
@ geckos That’s basically the same as @DanielWagner’s answer — bradrn

Daniel Wagner Daniel Wagner · Accepted Answer · 2021-08-26T03:02:16

With such a small collection of types, I would use one of these:

type Env = Map Variable (Either (Expr Int) (Expr Bool))
type Env = (Map Variable (Expr Int), Map Variable (Expr Bool))

...depending on whether you want separate namespaces for each type or not. When there are more types available, then I would use one of these:

data UntypedExpr = forall a. UE (TypeRep a) (Expr a)
type Env = Map Variable UntypedExpr
-- OR
newtype SingleTypeEnv a = STE (Map Variable (Expr a))
type Env = TypeRepMap SingleTypeEnv

...again depending on whether you want a separate namespace for each type or not.

TypeRep is from the base package (or you could make up some new GADT that's more specific to your EDSL's types), and TypeRepMap is from typerep-map.

How to create a typed toy language environment mapping usign GADT and Data.Map?

1 Answers