如何检查Haskell中的数据类型？

Question

我正在尝试在Haskell中编写一个brainfuck解释器作为一个练习/有趣的项目,我遇到了一个小问题.

Brainfuck的"while循环"结构只是括在括号内的一系列命令.我正在尝试以一种方式构建语法树,我将操作符存储在[数据构造函数内部的循环中.

这就是命令和语法"树"的数据声明当前的样子:

data Operator = Plus
                | Minus
                | RShift 
                | LShift
                | Dot
                | Comma
                | SBracket [Operator]
                | EBracket
                deriving (Show, Eq)


type STree = [Operator] 

我正在尝试做的是采取一些String命令,"+><[.>]"并将其解析为STree如下所示:

[Plus, RShift, LShift, SBracket [Dot, RShift], EBracket]

到目前为止,我只能得到一个一维列表String,因为我不知道如何检查列表的头是否是SBracket为了将新的运算符放在它的运算符列表而不是主要清单的负责人.

这是我用来解析的函数:

matchChar :: Char -> Maybe Operator
matchChar c = case c of 
                '+' -> Just Plus
                '-' -> Just Minus
                '>' -> Just RShift  
                '<' -> Just LShift
                '.' -> Just Dot
                ',' -> Just Comma
                '[' -> Just (SBracket [])
                ']' -> Just EBracket
                _   -> Nothing

getChars :: [Char] -> STree
getChars str = foldr toOp [] str
    where 
            toOp x acc = case matchChar x of
                            Just a -> a:acc
                            Nothing -> acc

我希望能够做的是检查是否head acc是一个SBracket例子,如果是这样,而不是前面加上新Operator的列表,在前面加上它SBracket的Operator名单.

我已经尝试过模式匹配(toOp x ((SBracket list):xs) = ...)以及尝试显式检查列表的头部(if head acc == SBracket ...),但这些都不能正常工作.

任何帮助都会很棒!

Answer 1

首先,我将重新定义SBracket [Operator]为公正Bracket STree并摆脱EBracket.然后我会更改你的解析器以跟踪"当前STree"以及父母列表.每次遇到括号时,都会将当前树推送到父列表并创建新树.当您遇到一个结束括号时,您将获取当前树,使用Bracket构造函数包装它,弹出第一个父项,将括号添加到其末尾并将其作为当前树.

这是完全未经测试的(在此comp上没有ghc)版本,可能有效也可能无效:

data Operator = Plus
                | Minus
                | RShift
                | LShift
                | Dot
                | Comma
                | Bracket [Operator]
                deriving (Show, Eq)

parse :: [Char] -> Either String [Operator]
parse str = parse' str [] []
  where parse' :: [Char] -> [Operator] -> [[Operator]] -> Either String [Operator]
        parse' [] context [] = Right (reverse context)
        parse' [] context _ = Left "unclosed []"
        parse' (']':cs) _ [] = Left "unexpected ]"
        parse' (c:cs) ctx stack
            | c == '+' = parse' cs (Plus:ctx) stack
            | c == '-' = parse' cs (Minus:ctx) stack
            | c == '>' = parse' cs (RShift:ctx) stack
            | c == '<' = parse' cs (LShift:ctx) stack
            | c == '.' = parse' cs (Dot:ctx) stack
            | c == ',' = parse' cs (Comma:ctx) stack
            | c == '[' = parse' cs [] (ctx:stack)
            | c == ']' = parse' cs (Bracket (reverse ctx):s) tack
            | otherwise = parse' cs ctx stack
          where (s:tack) = stack