Project 2 (Due: December 6th, 2026 - Sunday)
Handin under assignment project2
(Frequencies) 10 Points
Implement the following function in Haskell that takes a String as input and returns the frequency of occurrence of each character in the input.frequencies :: String -> [(Char,Int)] ???
For example,frequencies "mississippi" = [('i',4),('p',2),('s',4),('m',1)](N-ary Trees)
Complete the definition of the functions that operate on a n-ary Tree type. You must use folds/maps on the list structure that stores the child nodes of an interior node.data NTree a = Nil | Tree a [NTree a] deriving Show -- Returns the sum of all values stored in the nodes in the input tree sumElements :: NTree Int -> Int ??? -- Returns height of input tree (height=length of longest path from root to leaf) heightNTree :: NTree Int -> Int ??? -- Returns a list of all the values stored in the tree in pre-order preOrder :: NTree Int -> [Int] ???
The following are 3 examples of n-ary trees:t1 = Nil t2 = Tree 10 [] t3 = Tree 10 [ Tree 20 [], Tree 30 [ Tree 60 [], Tree 70 [] ], Tree 40 [ Tree 80 [ Tree 90 [Tree 95 []], Tree 100 [] ] ], Tree 50 [] ]WAE expressions are generalized form of arithmetic expressions defined as follows:
- Any number is a WAE expression
- Any variable is a WAE expression
- If w1 and w2 are WAE expressions then {+ w1 w2}, {- w1 w2}, {* w1 w2}, and {/ w1 w2} are also WAE expressions. The values of these expressions are the usual except that we have a prefix syntax for the arithmetic operations.
- If w1, w2, and w3 are WAE expressions then {if w1 w2 w3} is a WAE expression. This is a conditional arithmetic expression whose value is w2 if w1 evaluates to non-zero and w3 otherwise.
- If w is a WAE expression and v1, v2, ..., vn are variables and w1, w2, ..., wn are WAE expressions then {with {{v1 w1}{v2 w2}...{vn wn}} w} is a WAE expression. The value of this expression will be computed by first evaluating w1, w2, ..., wn and then replacing vi by wi in w and then evaluating w. The normal scoping rules of nested expressions will be used in the replacement.
- Nothing else is a WAE expression.
{with {{x 3}} {+ x x}} should evaluate to 6 {with {{x 3}} {with {{y 4}} {+ x y}}} should evaluate to 7 {with {{x {with {{x 3}} {+ x x}}}} {* x x }} should evaluate to 36 {with {{x 3} {y 4} {z 5}} {+ x {* y z}}} should evaluate to 23 {with {{x 3} {y 4} {z 5}} {+ {with {{x 10} {z 20}} x} {* {+ x y} z}}} should evaluate to 45 {with {{x 3} {y 4} {z 5} {y 3}} {+ x {* y z}}} # syntactically valid but has a semantic error - multiple y in with expression {with {{x 4}{y 4}} {/ 9 {- x y}}} # syntactivally valid but has a semantic error - divide by 0Yoou will write an evaluator for WAE expressions in Haskell. For this you will use the following type definition:-- WAE Data Type Definition data WAE a = Var String | Num a | Plus (WAE a) (WAE a) | Minus (WAE a) (WAE a) | Times (WAE a) (WAE a) | Div (WAE a) (WAE a) | If (WAE a) (WAE a) (WAE a) | With [(String,WAE a)] (WAE a) deriving ShowI have written the parsing code (Parsing.hs, and Convert.hs) to take a WAE expression as a Haskell String and returns a value under this data type. See following for how to convert WAE in String form into WAE value under the data type.$ ghci -package containers Convert.hs ghci> convert "{with {{x 3}} {+ 3 3}}" With [("x",Num 3.0)] (Plus (Num 3.0) (Num 3.0)) ghci> convert "{with {{x 3} {y 4} {z 5}} {+ x {* y z}}}" With [("x",Num 3.0),("y",Num 4.0),("z",Num 5.0)] (Plus (Var "x") (Times (Var "y") (Var "z")))You will have to complete the definition of eval in the skeleton file wae.hs having the signature:eval :: WAE Double -> Map.Map String (Maybe Double) -> Maybe Double ??? evalWAE xs = eval (convert xs) Map.empty
What to submit? freqencies.hs, ntree.hs, and wae.hs.