如果您正在寻找类似于 S 表达式的东西，那么在 Haskell 中可以很容易地对其进行建模。举例来说，我们想要用变量表示简单的代数方程，例如
x + 5 / (y * 2 - z)
这可以用 Haskell 中的简单 AST 来表示，特别是我们可以将其实现为
data Expr
= Lit Double -- Literal numbers
| Var Char -- Variables have single letter names
| Add Expr Expr -- We can add things together
| Sub Expr Expr -- And subtract them
| Mul Expr Expr -- Why not multiply, too?
| Div Expr Expr -- And divide
deriving (Eq)
这将使我们将上面的方程表示为
Add (Var 'x') (Div (Lit 5) (Sub (Mul (Var 'y') (Lit 2)) (Var 'z')))
但这写起来相当笨拙并且难以阅读。让我们先做一些工作Show魔法，让它打印得漂亮：
instance Show Expr where
showsPrec n (Lit x) = showParen (n > 10) $ showsPrec 11 x
showsPrec n (Var x) = showParen (n > 10) $ showChar x
showsPrec n (Add x y) = showParen (n > 6) $ showsPrec 7 x . showString " + " . showsPrec 7 y
showsPrec n (Sub x y) = showParen (n > 6) $ showsPrec 7 x . showString " - " . showsPrec 7 y
showsPrec n (Mul x y) = showParen (n > 7) $ showsPrec 8 x . showString " * " . showsPrec 8 y
showsPrec n (Div x y) = showParen (n > 7) $ showsPrec 8 x . showString " / " . showsPrec 8 y
如果您不理解这里发生的所有事情，那也没关系，通过一些内置函数，可以轻松有效地构建带有括号的字符串以及所有有趣的东西，从而使很多复杂性变得容易。它几乎是从文档中复制出来的Text.Show。现在，如果我们从上面打印出我们的表达式，它将看起来像
x + 5.0 / (y * 2.0 - z)
现在简化这些表达式的构建。因为它们几乎都是数字，所以我们可以实现Num（除了abs and signum) and Fractional:
instance Num Expr where
fromInteger = Lit . fromInteger
(+) = Add
(-) = Sub
(*) = Mul
abs = undefined
signum = undefined
instance Fractional Expr where
(/) = Div
fromRational = Lit . fromRational
现在我们可以输入上面的表达式
Var 'x' + 5 / (Var 'y' * 2 - Var 'z')
即使我们必须手动指定变量，这至少更容易直观地解析。
现在我们有了相当多的输入和输出，让我们专注于评估这些表达式。由于这里有变量，因此我们需要某种将变量与值关联起来的环境
import Data.Map (Map)
import qualified Data.Map as M
type Env = Map Char Double
现在它只是基本的模式匹配（以及辅助函数）
import Control.Applicative
binOp :: (Double -> Double -> Double) -> Expr -> Expr -> Env -> Maybe Double
binOp op x y vars = op <$> evalExpr x vars <*> evalExpr y vars
evalExpr :: Expr -> Env -> Maybe Double
evalExpr (Lit x) = const $ Just x
evalExpr (Var x) = M.lookup x
evalExpr (Add x y) = binOp (+) x y
evalExpr (Sub x y) = binOp (-) x y
evalExpr (Mul x y) = binOp (*) x y
evalExpr (Div x y) = binOp (/) x y
现在我们可以使用evalExpr通过变量替换来评估我们的迷你语言中的表达式。如果存在未定义的变量，则所有错误处理均由Maybemonad，我们甚至可以通过隐含环境参数来减少重复。对于简单的 DSL 表达式来说，这都是非常标准的。
因此，为了有趣一点，生成随机表达式和（最终）突变。为此，我们需要System.Random。我们希望能够生成不同复杂度的表达式，因此我们将粗略地表达它。由于它是随机的，因此我们有可能获得比指定的更短或更深的树。您可能需要对此进行调整和调整以获得所需的结果。首先，因为我有先见之明已经编写了这段代码，所以让我们定义两个助手来生成随机文字和随机变量：
randomLit, randomVar :: IO Expr
randomLit = Lit <$> randomRIO (-100, 100)
randomVar = Var <$> randomRIO ('x', 'z')
这里没什么令人兴奋的，我们得到 -100 到 100 之间的双精度数，以及最多 3 个变量。现在我们可以生成大型表达式树。
generateExpr :: Int -> IO Expr
-- When the depth is 1, return a literal or a variable randomly
generateExpr 1 = do
isLit <- randomIO
if isLit
then randomLit
else randomVar
-- Otherwise, generate a tree using helper
generateExpr n = randomRIO (0, 100) >>= helper
where
helper :: Int -> IO Expr
helper prob
-- 20% chance that it's a literal
| prob < 20 = randomLit
-- 10% chance that it's a variable
| prob < 30 = randomVar
-- 15% chance of Add
| prob < 45 = (+) <$> generateExpr (n - 1) <*> generateExpr (n - 1)
-- 15% chance of Sub
| prob < 60 = (-) <$> generateExpr (n - 1) <*> generateExpr (n - 1)
-- 15% chance of Mul
| prob < 75 = (*) <$> generateExpr (n - 1) <*> generateExpr (n - 1)
-- 15% chance of Div
| prob < 90 = (/) <$> generateExpr (n - 1) <*> generateExpr (n - 1)
-- 10% chance that we generate a possibly taller tree
| otherwise = generateExpr (n + 1)
该函数的大部分内容只是指定生成给定节点的概率，然后为每个运算符生成左节点和右节点。由于我们重载了，我们甚至必须使用普通的算术运算符Num，多么方便啊！
现在，请记住，我们仍然可以在这个构造函数上进行模式匹配Expr用于其他操作的类型，例如替换节点、交换节点或测量深度。为此，您只需将其视为 Haskell 中的任何其他二叉树类型，除了它有 2 个叶构造函数和 4 个节点构造函数。至于突变，您必须编写遍历此结构的代码，并选择何时交换节点以及用什么交换节点。它将生活在IOmonad 因为您将生成随机值，但这应该不会太困难。这个结构应该很容易根据需要进行扩展，例如如果您想添加三角函数和求幂，您只需要更多的构造函数，更多的表达式evalExpr，以及中的适当条款helper，以及一些概率调整。
您可以获得此示例的完整代码here https://gist.github.com/609ebd2073c6342827b6。希望这可以帮助您了解如何在 Haskell 中制定类似 S 表达式的内容。
