Project 2 (Due: December 6th, 2026 - Sunday)

Handin under assignment project2

  1. (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)]
    
  2. (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 []
                 ]
    
  3. WAE expressions are generalized form of arithmetic expressions defined as follows:

    1. Any number is a WAE expression
    2. Any variable is a WAE expression
    3. 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.
    4. 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.
    5. 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.
    6. Nothing else is a WAE expression.
    Some examples of WAE expressions are:
    {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 0
    
    Yoou 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 Show
    
    I 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.