字符串转换为自定义数据类型的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