在Haskell中实现一种语言:同源列表

Question

我正在尝试为haskell中的函数式语言创建一个解释器(我是该语言的新手).我正在创造可能是极简主义和便利的奇怪组合 - 没有抽象数据类型,但我想提供制作同类列表的能力.

所以我的基本变量是data Datum = DatInt Int | DatDbl Double | DatBool Bool,我已经意识到我完全不确定如何表示同类列表.添加构造函数List Datum或类似的东西会产生异构列表,并为每种类型创建单独的列表,即ListInt [Int] | ListDbl [Double]排除列表列表.

表示同质列表的最佳方法是什么？

Answer 1

一个有用的概念(无论你是否适合性感类型)都是类型标签.非性感版本更易于处理.

data Tag = IntTag
         | DoubleTag
         | BoolTag
         | ListTag Tag
   deriving (Eq, Show)

现在您的类型由这些各种标签表示.An Int由...表示IntTag.列表由... Int表示ListTag IntTag.

现在,您可以表示类似注释的表达式,如下所示:

data Expr = IntLit Int
          | DoubleLit Double
          | BoolLit Bool
          | ListLit Tag [Expr]

-- Check that an expression is validly annotated
typeCheck :: Expr -> Maybe Tag
typeCheck IntLit{} = Just IntTag
...
typeCheck (ListLit tag els)
  | all good els = Just (ListTag tag)
  | otherwise = Nothing
  where
    good el = case typeCheck el of
                Nothing -> False
                Just res = res == tag