如何檢查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

首先，我會將重新定義爲Bracket STree並刪除EBracket。然後，我會更改解析器以跟蹤「當前STree」以及父級列表。每次遇到括號時，都會將當前樹推入父列表並創建一棵新樹。當你遇到一個括號時，你把你當前的樹，用Bracket的構造函數包裝起來，彈出你的第一個父元素，將括號添加到最後，並使你的當前樹。

---

這裏是一個完全未經測試（沒有上過這種組合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