Assignment #2 Functional Programming Solution

Problem 1: In Lecture 10, we discussed the ML datatype for a simple binary tree




datatype ‘a tree = leaf of ‘a | node of ‘a tree * ‘a tree




and the function cat shown below for concatenating all strings in a string tree, with blanks separating consecutive strings.




fun cat(leaf(s) = s




| cat(node(t1, t2)) = cat(t1) ^ “ “ ^ cat(t2);




Write a tail-recursive equivalent of cat, called cat2, such that for all string trees t, cat(t) = cat2(t), i.e., they produce the same output given the same input.




Hint: Define cat2 in terms of a tail-recursive function cat_tail: string tree list * string - string, where the first component of the input tuple is a list of trees and the second is the accumulator.




Place your code in a file called cat.sml and submit it using the submit_cse505 command. Starter code including test cases posted at ResourcesHomeworkscat.sml.




Problem 2: Towards the end of Lecture 10, we discussed a flatten function for a two-level list. Note that a two-level ML list of type ‘a list list is homogeneous and hence a list such as [1, [2], 3] is not well-typed.




We can define a heterogeneous multi-level list in ML by a type ‘a mixed list by defining a type called ‘a mixed with two constructors, base and nest. The use of these two constructors is illustrated below for encoding the heterogeneous list [1, [2, [3, 4]], 5, [6]]:




[base(1), nest([base(2), nest([base(3), base(4)])]), base(5), nest([base(6)])]




We refer to the above list as a mixed list. The constructor base encodes a basic value of any type, and the constructor nest encodes a nested mixed list of the same type of basic value.




Write an ML datatype for the type ‘a mixed in terms of constructors base and nest.



Write a function flatten: ‘a mixed list - ‘a list which takes a mixed list as input and produces a single-level list as output. So, for the above example, the output would be



[1,2,3,4,5,6].




Place your code for (i) and (ii) in a file called mixed.sml and submit it using the submit_cse505 command. Starter code and test cases posted at ResourcesHomeworksmixed.sml.




End of Problems 1 and 2