module Main where import Data.Maybe (fromMaybe) import Text.Read (readEither) import…
- User
module Main where
import Data.Maybe (fromMaybe) import Text.Read (readEither) import Control.Monad (liftM2) import Test.QuickCheck
-- Expression types data IntExpr = Leaf Int | Add IntExpr IntExpr | Sub IntExpr IntExpr | Mul IntExpr IntExpr | Uminus IntExpr deriving (Show, Eq) data IdExpr = LeafId Int | Id String deriving (Show, Eq) data MaybeExpr = LeafMaybe Int | IdMaybe String | AddMaybe MaybeExpr MaybeExpr | SubMaybe MaybeExpr MaybeExpr | MulMaybe MaybeExpr MaybeExpr | UminusMaybe MaybeExpr deriving (Show, Eq)
-- Expression evaluation evalIntExpr :: IntExpr -> Int evalIntExpr (Leaf i) = i evalIntExpr (Add e1 e2) = evalIntExpr e1 + evalIntExpr e2 evalIntExpr (Sub e1 e2) = evalIntExpr e1 - evalIntExpr e2 evalIntExpr (Mul e1 e2) = evalIntExpr e1 * evalIntExpr e2 evalIntExpr (Uminus e) = negate (evalIntExpr e)
evalIdExpr :: IdExpr -> [(String, Int)] -> Int evalIdExpr (LeafId i) _ = i evalIdExpr (Id idStr) env = fromMaybe 0 (lookup idStr env)
evalMaybeExpr :: MaybeExpr -> [(String, Int)] -> Maybe Int evalMaybeExpr (LeafMaybe i) _ = Just i evalMaybeExpr (IdMaybe idStr) env = lookup idStr env evalMaybeExpr (AddMaybe m1 m2) env = liftM2 (+) (evalMaybeExpr m1 env) (evalMaybeExpr m2 env) evalMaybeExpr (SubMaybe m1 m2) env = liftM2 (-) (evalMaybeExpr m1 env) (evalMaybeExpr m2 env) evalMaybeExpr (MulMaybe m1 m2) env = liftM2 (*) (evalMaybeExpr m1 env) (evalMaybeExpr m2 env) evalMaybeExpr (UminusMaybe m) env = fmap negate (evalMaybeExpr m env)
-- Parsing data Token = Num Int | Op Operator deriving (Show, Eq) data Operator = Plus | Minus | Multiply | UnaryMinus deriving (Show, Eq)
parseToken :: String -> Either String Token parseToken "+" = Right (Op Plus) parseToken "-" = Right (Op Minus) parseToken "*" = Right (Op Multiply) parseToken str = case reads str of [(value, "")] -> Right (Num value) _ -> Left "Unable to parse token."
parseTokens :: [String] -> Either String [Token] parseTokens = mapM parseToken
postfixExpr :: String -> Either String [Token] postfixExpr = parseTokens . words
-- Expression evaluation from postfix notation evalPostfixExpr :: [Token] -> Either String Int evalPostfixExpr = evalPostfixExpr' []
evalPostfixExpr' :: [Int] -> [Token] -> Either String Int evalPostfixExpr' [result] [] = Right result evalPostfixExpr' stack (Num n : tokens) = evalPostfixExpr' (n : stack) tokens evalPostfixExpr' (y : x : stack) (Op op : tokens) = case op of Plus -> evalPostfixExpr' (x + y : stack) tokens Minus -> evalPostfixExpr' (x - y : stack) tokens Multiply -> evalPostfixExpr' (x * y : stack) tokens UnaryMinus -> evalPostfixExpr' ((-y) : stack) tokens evalPostfixExpr' _ _ = Left "Invalid expression or operator."
-- Unit tests prop_evalPostfixExpr :: String -> Bool prop_evalPostfixExpr str = case postfixExpr str of Left _ -> True Right tokens -> case evalPostfixExpr tokens of Left _ -> False Right _ -> True
main :: IO () main = do putStrLn "Expression evaluation and parsing" putStrLn "==============================="
let sampleEnv = [("x", 10), ("y", 20)] -- Sample environment
-- Sample expressions let intExpr = Add (Leaf 2) (Mul (Leaf 3) (Leaf 4)) idExpr = Add (Id "x") (LeafId 42) maybeExpr = AddMaybe (LeafMaybe 42) (IdMaybe "x")
-- Evaluate expressions putStrLn "Expression Evaluation Results:" putStrLn "Id Expression: " ++ show (evalIdExpr idExpr sampleEnv) putStrLn $ "Maybe Expression: " ++ show (evalMaybeExpr maybeExpr sampleEnv)
-- Run property-based tests putStrLn "\nProperty-based Tests:" quickCheck prop_evalPostfixExpr
- Assistant
This Haskell script covers various important concepts including algebraic data types, parsing, expression evaluation, and property-based testing with QuickCheck. Let's go through the main features:
-
Data Structures:
- It defines
IntExpr,IdExpr, andMaybeExprdata types for representing integer expressions, identifier-based expressions, and expressions that might fail to evaluate, respectively.
- It defines
-
Expression Evaluation:
evalIntExprevaluatesIntExprexpressions into integers.evalIdExprevaluatesIdExprexpressions using an environment (a list of(String, Int)tuples) to resolve identifiers.evalMaybeExprevaluatesMaybeExprexpressions with an environment, producingMaybe Intto account for the possibility of unresolved identifiers.
-
Parsing:
- Parses strings into a list of tokens (
Tokendata type) where a token can be a numeric value or an operator. - Supports a basic form of error reporting through the
Eithermonad.
- Parses strings into a list of tokens (
-
Postfix Expression Evaluation:
- Includes functionality to evaluate expressions represented in postfix notation.
evalPostfixExprprocesses a list of tokens and produces a result, handling errors such as invalid expressions or operators.
-
Property-based Testing with QuickCheck:
- Implements a property
prop_evalPostfixExprthat checks whether the postfix expression parsing and evaluation either successfully returns a value or properly reports an error, aiming to avoid runtime errors not covered by theEithererror handling.
- Implements a property
-
Main Function:
- Provides a demonstration of evaluating different expressions and shows how to run the QuickCheck property test.
Notable Observations:
-
The postfix evaluation supports unary minus, but there seems to be a slight mistake in handling the
UnaryMinusoperation inevalPostfixExpr'. The current implementation attempts to operate on two items from the stack for all operations, includingUnaryMinus. However,UnaryMinusshould operate on a single operand. This is a conceptual mistake that should be corrected to properly support unary minus in postfix expressions. -
The
UnaryMinusoperation doesn't seem to be properly integrated into the parsing phase (parseTokenfunction), meaning that as written, the script cannot correctly parse expressions involving unary minus. -
The property-based test
prop_evalPostfixExpressentially checks for the absence of runtime errors during the parsing and evaluation of postfix expressions but does not verify the correctness of the operation results.
Suggestions for Improvements:
- Correct the handling of
UnaryMinusinevalPostfixExpr'to properly evaluate expressions involving unary minus. - Extend the parsing functionality to correctly identify and handle unary minus operations.
- Enhance property-based tests to also verify the correctness of evaluated results, possibly by comparing with an alternative implementation or by checking specific known cases.
Overall, the script is a good demonstration of functional programming concepts in Haskell, including algebraic data types, monads, and property-based testing, but requires some fixes and improvements to fully support unary minus operations and to enhance its robustness and testing completeness.
-