Haskell中ST monad内隐藏幻影类型的方法咨询

这确实是ST monad使用中很常见的痛点——幻影类型s很容易渗透到整个AST定义里，搞得代码到处都是这个多余的类型参数。我来分享几个可行的解决思路，帮你把这个s藏起来：

1. 用闭包封装ST计算（最简洁的方案） #

与其让AST携带s类型参数，不如直接把每个表达式定义成返回ST s Value的多态闭包，用forall s把s封装在内部。这样你的AST完全不需要暴露s，用户只需要通过runST触发计算即可。

示例代码：

{-# LANGUAGE RankNTypes #-}

-- 先定义值类型（不需要s）
data Value = IntVal Int | BoolVal Bool

-- 核心：Expr不再带s，而是封装了一个任意s下的ST计算
data Expr = Expr { runExpr :: forall s. ST s Value }

-- 示例：变量引用的实现（假设我们用STRef存环境）
varRef :: String -> Expr
varRef name = Expr $ do
  -- 这里假设环境是一个全局的STRef（或者你可以把环境作为参数传递，用ReaderT包装ST）
  envRef <- readSTRef globalEnvRef
  env <- readSTRef envRef
  case lookup name env of
    Just val -> pure val
    Nothing -> error $ "Undefined variable: " ++ name

-- 示例：赋值语句（返回新的Expr，或者直接封装成ST动作）
assign :: String -> Expr -> Expr
assign name rhs = Expr $ do
  rhsVal <- runExpr rhs
  envRef <- readSTRef globalEnvRef
  env <- readSTRef envRef
  writeSTRef envRef (insert name rhsVal env)
  pure rhsVal -- 赋值返回值

-- 执行入口：用户只需要调用这个函数，完全看不到s
evalExpr :: Expr -> Value
evalExpr = runST . runExpr

这个方案的好处是完全隐藏了s，AST定义干净，而且符合小步解释器的计算模型——每个表达式直接对应一段可变状态下的计算逻辑。

2. 用存在类型包装带s的AST #

如果你确实需要保留AST的结构（比如要做静态分析、打印AST等），可以用存在类型把带s的AST包装起来，限制它只能在ST上下文里被使用。

示例代码：

{-# LANGUAGE ExistentialQuantification #-}
{-# LANGUAGE RankNTypes #-}

-- 带s的核心AST定义（内部使用）
data Expr s = VarRef String | Assign String (Expr s) | IntLit Int | Add (Expr s) (Expr s)

-- 存在类型包装器，隐藏s
data SomeExpr = forall s. SomeExpr (Expr s)

-- 求值函数：把存在类型打开，在ST s里执行
evalSomeExpr :: SomeExpr -> Value
evalSomeExpr (SomeExpr expr) = runST $ evalExpr expr
  where
    evalExpr :: Expr s -> ST s Value
    evalExpr (IntLit n) = pure $ IntVal n
    evalExpr (VarRef name) = -- 变量查找逻辑，和之前类似
    evalExpr (Assign name rhs) = do
      val <- evalExpr rhs
      -- 更新环境
      pure val
    evalExpr (Add e1 e2) = do
      IntVal v1 <- evalExpr e1
      IntVal v2 <- evalExpr e2
      pure $ IntVal (v1 + v2)

这个方案适合需要保留AST结构的场景，但要注意：你不能把SomeExpr内部的Expr s暴露给外部代码，否则会破坏ST monad的安全性（比如把一个s1下的STRef传递到s2的上下文里）。

3. 用MTL风格抽象状态层 #

如果你的解释器需要更灵活的扩展（比如以后可能换成IO或者纯状态模拟），可以把可变状态抽象成一个类型类，然后用ST作为底层实现，上层AST完全不依赖s。

示例代码：

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}

-- 抽象状态操作的类型类
class Monad m => MonadEnv m where
  getVar :: String -> m Value
  setVar :: String -> Value -> m ()

-- 用ST实现这个类型类（s被封装在EnvT里）
newtype EnvT s m a = EnvT { unEnvT :: ReaderT (STRef s (Map String Value)) (ST s) a }
  deriving (Functor, Applicative, Monad)

instance MonadEnv (EnvT s m) where
  getVar name = EnvT $ do
    envRef <- ask
    env <- lift $ readSTRef envRef
    case lookup name env of
      Just val -> pure val
      Nothing -> error $ "Undefined variable: " ++ name
  setVar name val = EnvT $ do
    envRef <- ask
    env <- lift $ readSTRef envRef
    lift $ writeSTRef envRef (insert name val env)

-- AST定义：只依赖MonadEnv，完全看不到s
data Expr = Expr { runExpr :: forall m. MonadEnv m => m Value }

-- 执行入口：用ST实例化EnvT并运行
evalExpr :: Expr -> Value
evalExpr expr = runST $ do
  initialEnv <- newSTRef empty
  runReaderT (unEnvT $ runExpr expr) initialEnv

这个方案的扩展性最好，但会增加一些抽象层的代码，适合中型以上的解释器项目。

为什么直接在AST里用forall s.会报错？ #

你之前尝试的forall s. Expr s本质是rank-n类型，需要开启RankNTypes扩展。但即使开启了，这种写法也有问题：因为ST的操作（比如创建STRef）是绑定到特定s的，你无法构造一个forall s. Expr s的实例——比如VarRef需要引用一个s下的STRef，这个STRef不能在任意s下使用，所以编译器会报错。正确的做法是把s封装在闭包或存在类型里，而不是直接在AST顶层用forall。

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