Use the Glasgow Haskell Compiler ghc to implement all the functions specified in Main.hs…
- User
Use the Glasgow Haskell Compiler ghc to implement all the functions specified in Main.hs and in the skeleton files referenced by Main.hs. When a function requirement specifies a restriction on how that function should be implemented, your implementation must meet that restriction. Main.hs A skeleton file which contains specifications for the some of the functions you are required to write. For each function it contains a dummy implementation with a "TODO" error. It also contains QuickCheck tests for these functions as well as a main function which runs all of the tests for the entire project. module Main (main) where
import TestUtils import EvalIntExpr (testEvalIntExpr) import EvalIdExpr (testEvalIdExpr) import EvalMaybeExpr (testEvalMaybeExpr) import PostfixExpr (testPostfixExpr)
import Test.QuickCheck
---------------------------- toSingletonLists --------------------------- -- #1: 5-points -- Use the map function to transform a list of elements e into -- a list of singleton lists [e]. Must use map. -- Hint: use map with a section. toSingletonLists :: [e] -> [[e]] toSingletonLists _ = error "TODO"
testToSingletonLists = do print "******* toSingletonLists" quickCheck toSingletonLists [ 5, 7, 2 ] == [ [5], [7], [2] ] quickCheck toSingletonLists [ 'a', 'x', 'd' ] == [ "a", "x", "d" ] quickCheck toSingletonLists [] == ([] :: [[Int]])
--------------------------------- listMap ------------------------------- -- #2: 5-points -- Return a list containing f a b for each element b in list. -- Hint: use the map function or a list comprehension listMap :: (a -> b -> c) -> a -> [b] -> [c] listMap _ _ _ = error "TODO"
testListMap = do print "******* listMap" quickCheck listMap (+) 5 [1, 2, 3] == [6, 7, 8] quickCheck listMap (-) 5 [1, 2, 3] == [4, 3, 2] quickCheck listMap (*) 5 [1, 2, 3] == [5, 10, 15] quickCheck listMap (-) 5 [] == []
---------------------------------- member ------------------------------- -- #3: 10-points -- Use foldl to implement member e list which returns True iff -- e is a member of list. Must use foldl, cannot use elem -- Hint: define folding function using a lambda or local let/where definition; -- also see definition of member in slides. member :: Eq e => e -> [e] -> Bool member _ _ = error "TODO"
testMember = do print "******* member" quickCheck member 5 [ 5, 7, 2 ] == True quickCheck member 2 [ 5, 7, 2 ] == True quickCheck member 7 [ 5, 7, 2 ] == True quickCheck member 4 [ 5, 7, 2 ] == False quickCheck member 4 [] == False
------------------------------- selectNApart ---------------------------- -- #4: 10-points -- Given an Int n and a list of elements e, return a list -- containing the elements of the list at index 0, n, 2n, 3n, 4n, ... -- Hint: use drop selectNApart :: Int -> [e] -> [e] selectNApart _ _ = error "TODO"
testSelectNApart = do print "******* selectNApart" quickCheck selectNApart 2 [0..10] == [0, 2, 4, 6, 8, 10] quickCheck selectNApart 2 ['a'..'z'] == "acegikmoqsuwy" quickCheck selectNApart 3 [0..20] == [0, 3, 6, 9, 12, 15, 18] quickCheck selectNApart 5 [0..21] == [0, 5, 10, 15, 20] quickCheck selectNApart 5 ([]::[Int]) == []
------------------------ Functions in Separate Files --------------------
-- #5: 15-points -- implement the specified function in EvalIntExpr.hs
-- #6: 15-points -- implement the specified function in EvalIdExpr.hs
-- #7: 20-points -- implement the specified function in EvalMaybeExpr.hs
-- #8: 20-points -- implement the specified function in PostfixExpr.hs
--------------------------------- Tests ---------------------------------
-- Can mark test suites with following test statuses: -- Only: run only these tests and other tests marked Only. -- Run: run these tests when no tests are marked Only. -- Skip: skip these tests. allTests = [ (Skip testToSingletonLists), (Skip testListMap), (Skip testMember), (Skip testSelectNApart), (Skip testEvalIntExpr), (Skip testEvalIdExpr), (Skip testEvalMaybeExpr), (Skip testPostfixExpr) ]
main = do mapM_ id tests where only = onlyTests allTests tests = if (length only > 0) then only else runTests allTests
EvalIntExpr.hs This is a separate skeleton file for implementing a single function evalIntExpr. module EvalIntExpr ( evalIntExpr, testEvalIntExpr, IntExpr(..) ) where
import Test.QuickCheck
-- an IntExpr is an expression-tree over integers data IntExpr = Leaf Int | Add IntExpr IntExpr | Sub IntExpr IntExpr | Mul IntExpr IntExpr | Uminus IntExpr deriving (Eq, Show)
-- evalIntExpr returns the Int result of evaluating the IntExpr -- expression-tree given by its argument. evalIntExpr :: IntExpr -> Int evalIntExpr _ = error "TODO"
testEvalIntExpr = do print "******* test evalIntExpr"
quickCheck evalIntExpr (Leaf 42) == 42 quickCheck evalIntExpr (Add (Leaf 33) (Leaf 22)) == 55 quickCheck evalIntExpr (Sub (Leaf 33) (Leaf 22)) == 11 quickCheck evalIntExpr (Mul (Leaf 31) (Leaf 4)) == 124 quickCheck evalIntExpr (Uminus (Leaf 33)) == (-33) quickCheck evalIntExpr (Mul (Leaf 4) (Sub (Add (Leaf 3) (Uminus (Leaf 33))) (Leaf 20))) == (-200)
-- property-based tests -- commutativity quickCheck (\ e1 e2 -> evalIntExpr (Add (Leaf e1) (Leaf e2)) == evalIntExpr (Add (Leaf e2) (Leaf e1))) quickCheck (\ e1 e2 -> evalIntExpr (Mul (Leaf e1) (Leaf e2)) == evalIntExpr (Mul (Leaf e2) (Leaf e1))) -- associativity quickCheck (\ e1 e2 e3 -> evalIntExpr (Add (Add (Leaf e1) (Leaf e2)) (Leaf e3)) == evalIntExpr (Add (Leaf e1) (Add (Leaf e2) (Leaf e3)))) quickCheck (\ e1 e2 e3 -> evalIntExpr (Mul (Mul (Leaf e1) (Leaf e2)) (Leaf e3)) == evalIntExpr (Mul (Leaf e1) (Mul (Leaf e2) (Leaf e3))))
-- subtraction quickCheck (\ e1 e2 -> evalIntExpr (Sub (Leaf e1) (Leaf e2)) == evalIntExpr (Mul (Leaf (-1)) (Sub (Leaf e2) (Leaf e1))))
-- distributivity quickCheck (\ e1 e2 e3 -> evalIntExpr (Mul (Leaf e1) (Add (Leaf e2) (Leaf e3))) == evalIntExpr (Add (Mul (Leaf e1) (Leaf e2)) (Mul (Leaf e1) (Leaf e3)))) quickCheck (\ e1 e2 e3 -> evalIntExpr (Mul (Leaf e1) (Sub (Leaf e2) (Leaf e3))) == evalIntExpr (Sub (Mul (Leaf e1) (Leaf e2)) (Mul (Leaf e1) (Leaf e3))))
EvalIdExpr.hs This is a separate skeleton file for implementing a single function evalIdExpr. module EvalIdExpr ( evalIdExpr, testEvalIdExpr ) where
import Test.QuickCheck import Data.List (lookup)
-- an IdExpr is an expression-tree over integers and string identifiers data IdExpr = Id String | Leaf Int | Add IdExpr IdExpr | Sub IdExpr IdExpr | Mul IdExpr IdExpr | Uminus IdExpr deriving (Eq, Show)
-- Assoc is a list of pairs mapping identifier strings to their values v. type Assoc v = [ (String, v) ]
-- evalIdExpr returns evaluation of the IdExpr expression-tree given -- by its first argument, looking up the values of id's in the Assoc -- argument. If an id is not found in the Assoc argument, then its -- value should default to 0. -- Hint: use Data.List.lookup imported above. evalIdExpr :: IdExpr -> Assoc Int -> Int evalIdExpr _ = error "TODO"
testEvalIdExpr = do print "*** test evalIdExpr" -- unit tests quickCheck evalIdExpr (Leaf 42) [] == 42 quickCheck evalIdExpr (Add (Leaf 33) (Leaf 22)) [] == 55 quickCheck evalIdExpr (Sub (Leaf 33) (Leaf 22)) [] == 11 quickCheck evalIdExpr (Mul (Leaf 31) (Leaf 4)) [] == 124 quickCheck evalIdExpr (Uminus (Leaf 33)) [] == (-33) quickCheck evalIdExpr (Mul (Leaf 4) (Sub (Add (Leaf 3) (Uminus (Leaf 33))) (Leaf 20))) [] == (-200)
-- id unit tests quickCheck evalIdExpr (Id "a") [("a", 42)] == 42 quickCheck evalIdExpr (Id "a") [("b", 42)] == 0 quickCheck evalIdExpr (Add (Id "a") (Id "b")) [("a", 42)] == 42 quickCheck evalIdExpr (Add (Id "a") (Id "b")) [("a", 42), ("b", 22)] == 64 quickCheck evalIdExpr (Mul (Id "a") (Sub (Add (Id "b") (Uminus (Id "c"))) (Id "d"))) [("a", 4), ("b", 3), ("c", 33), ("d", 20)] == (-200)
-- property-based tests -- id lookup quickCheck (\ id1 val1 -> evalIdExpr (Id id1) [(id1, val1)] == val1) quickCheck (\ id1 val1 -> evalIdExpr (Id id1) [(id1 ++ "x", val1)] == 0)
-- property-based tests -- commutativity quickCheck (\ e1 e2 -> evalIdExpr (Add (Leaf e1) (Leaf e2)) [] == evalIdExpr (Add (Leaf e2) (Leaf e1)) []) quickCheck (\ e1 e2 -> evalIdExpr (Mul (Leaf e1) (Leaf e2)) [] == evalIdExpr (Mul (Leaf e2) (Leaf e1)) []) -- associativity quickCheck (\ e1 e2 e3 -> evalIdExpr (Add (Add (Leaf e1) (Leaf e2)) (Leaf e3)) [] == evalIdExpr (Add (Leaf e1) (Add (Leaf e2) (Leaf e3))) []) quickCheck (\ e1 e2 e3 -> evalIdExpr (Mul (Mul (Leaf e1) (Leaf e2)) (Leaf e3)) [] == evalIdExpr (Mul (Leaf e1) (Mul (Leaf e2) (Leaf e3))) [])
-- subtraction quickCheck (\ e1 e2 -> evalIdExpr (Sub (Leaf e1) (Leaf e2)) [] == evalIdExpr (Mul (Leaf (-1)) (Sub (Leaf e2) (Leaf e1))) [])
-- distributivity quickCheck (\ e1 e2 e3 -> evalIdExpr (Mul (Leaf e1) (Add (Leaf e2) (Leaf e3))) [] == evalIdExpr (Add (Mul (Leaf e1) (Leaf e2)) (Mul (Leaf e1) (Leaf e3))) []) quickCheck (\ e1 e2 e3 -> evalIdExpr (Mul (Leaf e1) (Sub (Leaf e2) (Leaf e3))) [] == evalIdExpr (Sub (Mul (Leaf e1) (Leaf e2))
(Mul (Leaf e1) (Leaf e3))) [])EvalMaybeExpr.hs This is a separate skeleton file for implementing a single function evalMaybeExpr. module EvalMaybeExpr ( evalMaybeExpr, testEvalMaybeExpr ) where
import Test.QuickCheck import Data.List (lookup)
data MaybeExpr = Id String | Leaf Int | Add MaybeExpr MaybeExpr | Sub MaybeExpr MaybeExpr | Mul MaybeExpr MaybeExpr | Uminus MaybeExpr deriving (Eq, Show)
type Assoc a = [ (String, a) ]
-- return a Maybe wrapping the results of evaluating expr, looking up -- id's in assoc. If an id is not found in assoc, then the function -- should return Nothing. Hint: use Data.List.assoc imported above -- and do notation. evalMaybeExpr :: MaybeExpr -> Assoc Int -> Maybe Int evalMaybeExpr _ _ = error "TODO"
testEvalMaybeExpr = do print "*** test evalMaybeExpr" -- unit tests quickCheck evalMaybeExpr (Leaf 42) [] == Just 42 quickCheck evalMaybeExpr (Add (Leaf 33) (Leaf 22)) [] == Just 55 quickCheck evalMaybeExpr (Sub (Leaf 33) (Leaf 22)) [] == Just 11 quickCheck evalMaybeExpr (Mul (Leaf 31) (Leaf 4)) [] == Just 124 quickCheck evalMaybeExpr (Uminus (Leaf 33)) [] == Just (-33) quickCheck evalMaybeExpr (Mul (Leaf 4) (Sub (Add (Leaf 3) (Uminus (Leaf 33))) (Leaf 20))) [] == Just (-200)
-- id unit tests quickCheck evalMaybeExpr (Id "a") [("a", 42)] == Just 42 quickCheck evalMaybeExpr (Id "a") [("b", 42)] == Nothing quickCheck evalMaybeExpr (Add (Id "a") (Id "b")) [("a", 42)] == Nothing quickCheck evalMaybeExpr (Add (Id "a") (Id "b")) [("a", 42), ("b", 22)] == Just 64 quickCheck evalMaybeExpr (Mul (Id "a") (Sub (Add (Id "b") (Uminus (Id "c"))) (Id "d"))) [("a", 4), ("b", 3), ("c", 33), ("d", 20)] == Just (-200)
-- property-based tests -- id lookup quickCheck (\ id1 val1 -> evalMaybeExpr (Id id1) [(id1, val1)] == Just val1) quickCheck (\ id1 val1 -> evalMaybeExpr (Id id1) [(id1 ++ "x", val1)] == Nothing)
-- property-based tests -- commutativity quickCheck (\ e1 e2 -> evalMaybeExpr (Add (Leaf e1) (Leaf e2)) [] == evalMaybeExpr (Add (Leaf e2) (Leaf e1)) []) quickCheck (\ e1 e2 -> evalMaybeExpr (Mul (Leaf e1) (Leaf e2)) [] == evalMaybeExpr (Mul (Leaf e2) (Leaf e1)) []) -- associativity quickCheck (\ e1 e2 e3 -> evalMaybeExpr (Add (Add (Leaf e1) (Leaf e2)) (Leaf e3)) [] == evalMaybeExpr (Add (Leaf e1) (Add (Leaf e2) (Leaf e3))) []) quickCheck (\ e1 e2 e3 -> evalMaybeExpr (Mul (Mul (Leaf e1) (Leaf e2)) (Leaf e3)) [] == evalMaybeExpr (Mul (Leaf e1) (Mul (Leaf e2) (Leaf e3))) [])
-- subtraction quickCheck (\ e1 e2 -> evalMaybeExpr (Sub (Leaf e1) (Leaf e2)) [] == evalMaybeExpr (Mul (Leaf (-1)) (Sub (Leaf e2) (Leaf e1))) [])
-- distributivity quickCheck (\ e1 e2 e3 -> evalMaybeExpr (Mul (Leaf e1) (Add (Leaf e2) (Leaf e3))) [] == evalMaybeExpr (Add (Mul (Leaf e1) (Leaf e2)) (Mul (Leaf e1) (Leaf e3))) []) quickCheck (\ e1 e2 e3 -> evalMaybeExpr (Mul (Leaf e1) (Sub (Leaf e2) (Leaf e3))) [] == evalMaybeExpr (Sub (Mul (Leaf e1) (Leaf e2))
(Mul (Leaf e1) (Leaf e3))) [])PostfixExpr.hs This is a separate skeleton file for implementing a single function postfixExpr. module PostfixExpr ( postfixExpr, testPostfixExpr, PostfixExpr(..) ) where
import Test.QuickCheck
-- a PostFixExpr is an expression tree over integers data PostfixExpr = Leaf Int | Add PostfixExpr PostfixExpr | Sub PostfixExpr PostfixExpr | Mul PostfixExpr PostfixExpr | Uminus PostfixExpr deriving (Eq, Show)
-- Given a string postfix containing a postfix expression involving -- integers, the usual binary arithmetic operators "+", "-", "*" as -- well as "uminus", return the corresponding PostfixExpr. You may -- disregard errors.
-- Hints:
-- + Use the Haskell function (words postfix) to split the -- postfix string into String tokens.
-- + Iterate through the tokens using a [PostfixExpr] stack to track -- the currently unprocessed PostfixExpr's.
-- + At each step of the iteration, look at the first -- unprocessed token:
-- + If it is a string representing an operator, then replace -- its operands from the head of the stack with the -- PostfixExpr corresponding to the operator combined with its -- operands from the stack.
-- + If the current unprocessed token is not an operator, assume -- it is an Int and use (read token) to build it into a -- Leaf.
-- + Use pattern matching to match different types of tokens and to -- extract PostfixExpr operands from the head of the stack.
-- + Use a local auxiliary function to perform each step of the -- iteration.
-- + You can use a recursive implementation of the top-level -- function. But what is recommended is to set up your auxiliary -- function so that you can use it to foldl the token list into -- an accumulator representing the stack of unprocessed -- PostfixExpr's.
-- + When there are no unprocessed tokens, the stack should contain -- a single PostfixExpr containing the value to be returned. postfixExpr :: String -> PostfixExpr postfixExpr _ = error "TODO"
testPostfixExpr = do print "******* test postfixExpr"
quickCheck postfixExpr "42" == (Leaf 42) quickCheck postfixExpr "33 22 +" == (Add (Leaf 33) (Leaf 22)) quickCheck postfixExpr "33 22 -" == (Sub (Leaf 33) (Leaf 22)) quickCheck postfixExpr "31 4 *" == (Mul (Leaf 31) (Leaf 4)) quickCheck postfixExpr "33 uminus" == (Uminus (Leaf 33)) quickCheck postfixExpr "4 3 33 uminus + 20 - *" == (Mul (Leaf 4) (Sub (Add (Leaf 3) (Uminus (Leaf 33))) (Leaf 20)))
TestUtils.hs A file containing utilities used for testing. You should not need to modify this file. module TestUtils (onlyTests, runTests, SuiteStatus(..)) where
type SuiteFn = IO ()
data SuiteStatus = Run SuiteFn | Skip SuiteFn | Only SuiteFn
onlyTests [] = [] onlyTests ((Only t):tests) = t : onlyTests tests onlyTests (_:tests) = onlyTests tests
runTests [] = [] runTests ((Run t):tests) = t : runTests tests runTests (_:tests) = runTests tests
When writing recursive functions, use the structure of the data to guide your code. Typically your code will contain one equation for each variant of the data. Hints for each function are available in the provided skeleton files. You should not need to use Haskell library functions other than those mentioned explicitly in this project.
- Assistant
Given the rules of your assignment and the extensive details you provided, I'll proceed directly by implementing the functions requested in
Main.hsand the referred skeleton files. However, since I can't break the response into separate files or run the GHC directly here, I'll format the solutions in a manner that you can directly translate into your Haskell environment.Main.hs
First, we'll tackle the initial functions in
Main.hs.toSingletonLists Implementation
toSingletonLists :: [e] -> [[e]] toSingletonLists = map (:[])listMap Implementation
listMap :: (a -> b -> c) -> a -> [b] -> [c] listMap f a = map (f a)member Implementation
member :: Eq e => e -> [e] -> Bool member e = foldl (\acc x -> acc || x == e) FalseselectNApart Implementation
Note: This solution uses recursion instead of
dropdirectly for selecting elements n apart. It's a bit tricky to implement this directly withdropwithout auxiliary functions due to the specification requirements. But it iteratively dropsnelements to select the right item.selectNApart :: Int -> [e] -> [e] selectNApart _ [] = [] selectNApart n (x:xs) = x : selectNApart n (drop (n-1) xs)EvalIntExpr.hs
Here's an example implementation, though your question specifies separate files, and thus I'll only provide an outline for one function implementation.
evalIntExpr :: IntExpr -> Int evalIntExpr (Leaf n) = n 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.hs
evalIdExpr :: IdExpr -> Assoc Int -> Int evalIdExpr (Leaf n) _ = n evalIdExpr (Id s) assoc = maybe 0 id (lookup s assoc) evalIdExpr (Add e1 e2) assoc = evalIdExpr e1 assoc + evalIdExpr e2 assoc evalIdExpr (Sub e1 e2) assoc = evalIdExpr e1 assoc - evalIdExpr e2 assoc evalIdExpr (Mul e1 e2) assoc = evalIdExpr e1 assoc * evalIdExpr e2 assoc evalIdExpr (Uminus e) assoc = negate (evalIdExpr e assoc)EvalMaybeExpr.hs
evalMaybeExpr :: MaybeExpr -> Assoc Int -> Maybe Int evalMaybeExpr (Leaf n) _ = Just n evalMaybeExpr (Id s) assoc = lookup s assoc evalMaybeExpr (Add e1 e2) assoc = liftA2 (+) (evalMaybeExpr e1 assoc) (evalMaybeExpr e2 assoc) evalMaybeExpr (Sub e1 e2) assoc = liftA2 (-) (evalMaybeExpr e1 assoc) (evalMaybeExpr e2 assoc) evalMaybeExpr (Mul e1 e2) assoc = liftA2 (*) (evalMaybeExpr e1 assoc) (evalMaybeExpr e2 assoc) evalMaybeExpr (Uminus e) assoc = fmap negate (evalMaybeExpr e assoc)PostfixExpr.hs
A sketch of a solution, as a full implementation would be lengthy:
postfixExpr :: String -> PostfixExpr postfixExpr = head . foldl processToken [] . words where processToken (x:y:ys) "+" = (Add y x):ys processToken (x:y:ys) "-" = (Sub y x):ys processToken (x:y:ys) "*" = (Mul y x):ys processToken (x:xs) "uminus" = (Uminus x):xs processToken xs numStr = (Leaf (read numStr)):xsPlease adapt these solutions to your needs and fit them into your project's structure. Remember to thoroughly read your assignment's requirements and test each component for correctness before submission.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.