为什么ML/Haskell数据类型对于定义像算术表达式这样的"语言"很有用？

Question

对于像ML系列那样的函数式语言,这是一个关于静态类型系统的软问题.我理解为什么你需要数据类型来描述像列表和树这样的数据结构,但是像数据类型中的命题逻辑那样定义"表达式"似乎带来了一些便利并且不是必需的.例如

datatype arithmetic_exp = Constant of int
                        | Neg of arithmetic_exp
                        | Add of (arithmetic_exp * arithmetic_exp)
                        | Mult of (arithmetic_exp * arithmetic_exp)

定义一组值,您可以在其上编写一个eval可以为您提供结果的函数.你也可以同样定义了4个功能:const: int -> int,neg: int -> int,add: int * int -> int和mult: int * int -> int,然后排序的表达add (mult (const 3, neg 2), neg 4)会给你同样的事情,不带静电安全的任何损失.唯一的复杂因素是你必须做四件事而不是两件事.在学习SML和Haskell时,我一直在考虑哪些功能为您提供了必要的东西,哪些只是一种便利,所以这就是我要问的原因.我想如果你想要从值本身分离一个值的过程,这就很重要,但我不确定哪个有用.

非常感谢.

Answer 1

基于初始/一阶/数据类型的编码(又名深度嵌入)和最终/高阶/基于评估器的编码(又称浅嵌入)之间存在二元性.实际上,您通常可以使用类型组合器而不是数据类型(并在两者之间来回转换).

这是一个显示两种方法的模块:

{-# LANGUAGE GADTs, Rank2Types #-}

module Expr where

data Expr where
  Val :: Int -> Expr
  Add :: Expr -> Expr -> Expr

class Expr' a where
  val :: Int -> a
  add :: a -> a -> a

您可以看到这两个定义看起来非常相似.Expr' a基本上是描述一个代数,Expr这意味着你可以得到a一个Expr如果你有这样的Expr' a.同样,因为您可以编写实例,所以您可以将Expr' Expr类型的术语重新定义为类型forall a. Expr' a => a的语法值Expr:

expr :: Expr' a => Expr -> a
expr e = case e of
  Val n   -> val n
  Add p q -> add (expr p) (expr q)

instance Expr' Expr where
  val = Val
  add = Add

expr' :: (forall a. Expr' a => a) -> Expr
expr' e = e

最后,选择一个表示形式实际上取决于你的主要关注点:如果你想检查表达式的结构(例如,如果你想优化/编译它),那么如果你有权访问AST就更容易了.另一方面,如果您只对使用折叠计算不变量(例如表达式的深度或其评估)感兴趣,则可以使用更高阶的编码.