Reference no: EM132223349
Programming Language Concepts Assignment -
This is a programming assignment in F#. Download the accompanying F# source file hw1.fsx and enter your solutions in it where indicated. When you are done, submit it as instructed on Piazza. Each of your answers must be free of static errors. You may receive no credit for problems whose code contains syntax or type errors.
In the following problems do not use any mutable variables (i.e., variables declared with let mutable) or any mutable predefined types such as references, mutable records, arrays, and so on. Define your functions recursively as needed and take advantage of the match operator.
1. Basic functional programming in F#
F# has a predefined list datatype. Strictly speaking, however, it is not necessary, For instance, integer lists could be simulated by the following user defined datatype
type ilist =
E
| L of int * ilist
where the constructor E stands for the empty list and the constructor L builds a new list by adding a number in front of another list. Then one can represent, say, a list with elements 1,4,6,7, in that order, with the ilist value L(1, L(4, L(6, L(7, E)))).
Using pattern matching and recursion, implement the following functions manipulating ilist values.
1. Write an F# function sum: ilist -> int which takes as input a ilist l and returns the sum of all the elements in l. For example, sum (L(1, L(3, L(3, E)))) is 7, while sum E is 0.
2. Write an F# function elem: int -> ilist -> int which takes a positive integer n and a list l, and returns the nth element of l if the list has at least n elements, and fails (using failwith) with message "Index out of bound" otherwise. For example, elem 2 (L(3, L(21, L(11, E)))) is 21.
3. Write an F# function isIn: int-> ilist -> bool which takes an integer x and an ilist l and returns true if and only if x occurs in l.
4. Write an F# function remove: int -> ilist -> ilist which, given an integer x and a list l, "removes" all the occurrences of x from l, that is, returns a list containing (in the same order) all and only the elements of l that differ from x.
For example, remove 2 (L(1, L(2, L(3, L(3, L(2, E)))))) is L(1, L(3, L(3, E))), remove 5 (L(1, L(2, L(3, E)))) is (L(1, L(2, L(3, E)))).
5. Write an F# function move: ilist -> ilist -> ilist which takes two lists and returns the result of inserting the values of the first list into the second, in reverse order. For example, move (L(1, L(2, L(3, E)))) (L(4, L(5, E))) is L(3, L(2, L(1, L(4, L(5, E))))).
6. Use function move to implement the function reverse: ilist -> ilist that returns the result of reversing its input list. For example, reverse (L(1, L(2, L(3, E)))) is L(3, L(2, L(1, E))).
2. Programming functional style with binary trees
Consider a variant of the binary tree algebraic datatype seen in class
type btree = Leaf of int | Node of btree * int * btree
and a new datatype defined as follows:
type finding = NotFound | Found of int
1. Write a function size: btree -> int which, given a tree t, returns the number of (non-leaf) nodes in it.
2. Write a function leftmost_nl: btree -> finding which takes as input a tree t, and returns NotFound if t is a leaf and otherwise returns (Found x) where x is the leftmost non-leaf value in a non-leaf node in t.
Observe that the leftmost non-leaf value of a tree of the form Node (t1, x, t2) is the same as the leftmost non-leaf value of t1 if t1 is not a leaf and is x otherwise.
3. Write a function mirror: btree -> btree which takes a tree t a returns the mirror image of t, that is, the tree obtained from t by swapping every left subtree with its corresponding right subtree.
4. Write a function leftReplace: int -> btree -> btree which, given an integer x and a btree t, returns a tree identical to t except that the leftmost value of t, if any, is replaced by x in the new tree.
The function should be such that leftReplace x t equals t when t does not have a leftmost node.
Note that differently from question 2, here the leaf values must also be considered.
5. Write a function toString nz: btree -> string which takes a tree t a returns a string consisting of all the non-zero numbers stored in t separated by white spaces. The order of the numbers in the list should correspond to a preorder traversal of the tree (root, left subtree, right subtree). The string should separate its numbers by exactly one space character and contain no initial or final spaces.
Attachment:- Assignment Files.rar