A rope is a persistent data structure to represent text. Many languages contain built-in notions of text as strings or contiguous arrays of characters. In contrast, ropes are a tree-based representation of text. A key advantage of ropes is improved running times for common operations, such as concatenation and subsequence, compared to contiguous character arrays. Some variations of ropes use self-balancing trees or support explicit balance operations. However, for these questions, we will consider a simple variation of ropes without any balancing operations. Such an unbalanced rope will be either: - a string-i.e., an array of characters - and the length of the string; - or a left rope, a right rope, and the total size of the two subropes. Questions Answer the following questions about ropes. You may use OCaml syntax or pseudocode of the style used in lecture. 1. (20 pts) Define the type for a rope as a variant. Assume that a type for strings (string) already exists. 2. (5 pts) Write a function, string-rope, to construct a rope from a string. Assume that you have a function string-length to find the length of a string. 3. (25 pts) Write a function, rope-cat, to concatenate two ropes. 4. (25 pts) Draw the tree structure of a,b, and c after the following operations. Be sure to show any shared parts of the data structures. var a rope-cat (string-rope "foo") (string-rope "bar"); varb rope-cat a (string-rope "bif"); varc rope-cat ab; 5. (25 pts) Contrast the asymptotic running times ("big-O") of (1) concatenating two strings - e.g., the C strcat function - and (2) your rope-cat function. Assume that allocating memory of size n is O(n). Explain the reason for difference in running times