字符串轉換爲自定義數據類型的Haskell

Question

我創建了一個自定義的數據類型Expr的

type Name = String 
type Domain = [Integer] 
data Expr = Val Integer 
| Var Name 
| Expr :+: Expr 
| Expr :-: Expr 
| Expr :*: Expr 
| Expr :/: Expr 
| Expr :%: Expr 
    deriving Eq 

我需要創建一個用於創建從字符串數據類型Expr的，而不在Haskell使用解析器庫的分析器。

我爲初始字符串創建瞭解析器，該字符串接受「2 * a + b」形式的字符串並將其轉換爲形式「Val 2：*：Var」a：：+：Var「b 「」，這被Expr所接受，但這是我不知道該怎麼做才能走得更遠。我的問題是，我不知道如何在沒有解析器庫的情況下從這樣的字符串創建Expr。

Answer 1

import Control.Applicative (Alternative (empty, many, some, (<|>)), (<**>)) 
import Data.Char   (isSpace, isDigit) 
import Data.Maybe   (listToMaybe) 

編寫一個基本低效的解析庫實際上並不難，可以在50行以下的代碼中完成。核心類型如下：

newtype Parser a = Parser (String -> [(a, String)]) 

parse :: Parser a -> String -> Maybe a 
parse (Parser p) s = listToMaybe $ fst <$> p s 

這個解析器部分消耗一個字符串，其餘串一併返回解析後的結果a。但是可能有很多解析方案，這就是爲什麼它返回結果和剩餘部分的列表。

對於使用這種類型，我們需要一些更多的實用程序。我離開了_供您實施。

instance Functor Parser where 
    fmap (Parser p) = _ 

instance Applicative Parser where 
    pure a = Parser $ \s -> (a, s) -- Consumes nothing and returns a 
    Parser pf <*> Parser pa = _ -- Parse pf, then parse pa and apply the result 
            -- of pf to that of pa. 

instance Alternative Parser where 
    empty = Parser $ \s -> [] -- Matches nothing 
    Parser p1 <|> Parser p2 = _ -- Matches either p1 or if that fails p2. 

satisfy :: (Char -> Bool) -> Parser Char 
satisfy = _ 

space :: Parser() 
space =() <$ satisfy isSpace 

spaces :: Parser() 
spaces =() <$ many space 

char :: Char -> Parser Char 
char c = satisfy (c ==) 

-- | Detects the end of file. 
eof :: Parser() 
eof = _ 

-- | Succeeds when at the end of a word, without consuming any input 
eow :: Parser() 
eow = _ 

現在我們可以繼續使用這個解析器像任何遞歸下降解析器：

data Expr = Val Integer 
      | Expr :*: Expr 
      | Expr :+: Expr 
    deriving Show 

parseVal :: Parser Expr 
parseVal = 
    char '(' *> parseAdd <* char ')' <|> 
    Val . read <$> some (satisfy isDigit) <* eow 

parseMul :: Parser Expr 
parseMul = _ 

parseAdd :: Parser Expr 
parseAdd = _ 

parseExpr :: Parser Expr 
parseExpr = parseAdd <* eof