Let's write β

プログラミング中にできたことか、思ったこととか

Haskellでラムダ式をパース

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Char
import Control.Monad

data LambdaExpr = Var Char | Lambda LambdaExpr LambdaExpr | Apply LambdaExpr LambdaExpr deriving (Show)

identifier :: GenParser Char st LambdaExpr
identifier = do
                c <- noneOf "().^"
                return $ Var c

lambdaExpr :: GenParser Char st LambdaExpr
lambdaExpr = try (do
                char '('
                char '^' -- lambda
                ide <- identifier
                char '.'
                expr <- lambdaExpr
                char ')'
                return $ Lambda ide expr)
                <|> try (do
                                char '('
                                e1 <- lambdaExpr
                                spaces
                                e2 <- lambdaExpr
                                char ')'
                                return $ Apply e1 e2)
                <|> identifier

parseLambdaExpr str = parse (do
                                expr <-lambdaExpr
                                notFollowedBy anyChar
                                return expr) "Parse Error" str

こんな感じかな

*Main> parseLambdaExpr "(^x.(^y.x))"
Right (Lambda (Var 'x') (Lambda (Var 'y') (Var 'x')))