如何使用GADT与Data.Map构建Haskell类型化玩具语言的环境映射

问题原因 #

你定义的Env a类型约束了Map中所有值必须是同一种Expr a类型，要么全是Expr Bool，要么全是Expr Int，自然无法同时存储两种类型的表达式值。

解决方案 #

使用存在量化类型包装Expr，隐藏其内部的类型参数差异，让Map可以存储任意类型的Expr。

实现步骤 #

1. 新增语言扩展：开启ExistentialQuantification，如果需要后续做运行时类型匹配，额外开启Typeable。
2. 定义存在量化包装类型，把任意Expr a封装为统一的AnyExpr类型：

-- 仅需异构存储的最简写法
data AnyExpr = forall a. AnyExpr (Expr a)

-- 支持后续类型匹配的写法
{-# LANGUAGE Typeable #-}
data AnyExpr = forall a. Typeable a => AnyExpr (Expr a)

3. 重新定义Env类型，值类型替换为AnyExpr：

type Env = M.Map Char AnyExpr

4. 构造环境时，给每个Expr套上AnyExpr包装即可：

env = M.fromList [('x', AnyExpr $ B True), ('y', AnyExpr $ I 10)]

完整修正代码 #

{-# LANGUAGE GADTs, RankNTypes, ExistentialQuantification, Typeable #-}

module Foo where

import qualified Data.Map as M
import Data.Maybe
import Data.Typeable (Typeable, cast)

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
  deriving (Typeable)

-- 异构表达式包装
data AnyExpr = forall a. Typeable a => AnyExpr (Expr a)

type Env = M.Map Char AnyExpr

env :: Env
env = M.fromList [('x', AnyExpr $ B True), ('y', AnyExpr $ I 10)]

-- 示例：按期望类型从环境中安全取值
lookupExpr :: Typeable a => Char -> Env -> Maybe (Expr a)
lookupExpr k env = do
  AnyExpr e <- M.lookup k env
  cast e

内容的提问来源于stack exchange，提问作者geckos