1. Homepage
  2. Programming
  3. CS 440 Programming Languages and Translators - Homework 2: ADTs and HOFs

CS 440 Programming Languages and Translators - Homework 2: ADTs and HOFs

Engage in a Conversation
USIITIllinois Institute of TechnologyCS 440Programming Languages and TranslatorsADTs and HOFs

CS 440 HW2

In this homework you will be writing and making use of higher order functions -- an important class of functions discussed in class. You'll also be writing functions that perform symbolic manipulation --- a step in the direction of implementing compilers/interpreters. CourseNana.COM

Your code for this homework will go in three different files, one for each part. You'll find stubs for each of the programming exercises. Remember to git add all three of these files before committing and pushing your final submission. CourseNana.COM


This assignment is to be completed individually, subject to the academic integrity policy on the course website. Make sure you read and understand these. CourseNana.COM

At the end of this assignment, we will ask you to list any students you discussed the homework with, as well as any websites or other resources (please list specific URLs when applicable) you referred to. CourseNana.COM

Important notes about grading

Your submissions will be graded automatically for correctness, as well as checked by hand. Please keep our autograder (and Xincheng, who has to run it) happy: CourseNana.COM

  1. Do not change or remove any lines that start with (*>*. CourseNana.COM

  2. Do not change the names or types of any functions defined in the starter code. This includes adding rec to functions that don't have it. CourseNana.COM

Part 1: HOFs (20 points)

Your code for this part will go in the fine "hof.ml" IMPORTANT: In this part, you may not use recursion unless otherwise specified. CourseNana.COM

  1. join takes a string sep and a string list l and returns a string consisting of all of the strings of l concatenated, and separated with sep. It's OK if there's one extra sep at the end (not the beginning). e.g., CourseNana.COM

     # join ", " ["Python"; "Java"; "OCaml"];;
     - : string = "Python, Java, OCaml, "
     # join ", " [];;
     - : string = ""
  2. concat takes a list of lists and returns one list with all of the elements of all of the original list, e.g., CourseNana.COM

     # concat [[1; 2; 3]; [4]; [5; 6]; []];;
     - : int list = [1; 2; 3; 4; 5; 6]
     # concat [];;
     - : 'a list = []
     # concat [[]; []];;
     - : 'a list = []
  3. run_length_encode is the same as on HW1, but this time you'll implement it with higher-order functions instead of recursion. CourseNana.COM

    Returns a run-length encoding of the argument list. Run-length encoding stores each value together with the number of times it appears (contiguously) — in this way, a value that is repeated multiple times can be more efficiently represented. E.g., CourseNana.COM

     # run_length_encode ['a'; 'a'; 'a'; 'a'; 'a'; 'b'; 'b'; 'b'];;
     - : (char * int) list = [('a', 5); ('b', 3)]
     # run_length_encode [1; 1; 6; 6; 6; 6; 2];;
     - : (int * int) list = [(1, 2); (6, 4); (2, 1)]
     # run_length_encode [];;
     - : ('a * int) list = []

    You may assume that adjacent elements can be compared for equality using =. CourseNana.COM

  4. run_length_decode is the same as on HW1, but this time you'll implement it with higher-order functions instead of recursion. CourseNana.COM

    Given a run-length encoded list argument, returns the original list. E.g., CourseNana.COM

     # run_length_decode [('a', 5); ('b', 3)];;
     - : char list = ['a'; 'a'; 'a'; 'a'; 'a'; 'b'; 'b'; 'b']
  5. (BONUS - 2 points) Write a tail-recursive version of List.fold_right without using List.fold_left or List.rev (or re-implementing either of these; your function should make just one pass over the list). Other than tail recursion, your function should behave identically to List.fold_right. You may use recursion for this question only. CourseNana.COM

    Hint: Try changing the function you pass to the recursive application. CourseNana.COM

    Note: This, like other bonus tasks we'll occasionally include in assignments, is quite difficult and is worth a small number of bonus points. Try it for an extra challenge if you want (probably after completing the rest of the assignment). CourseNana.COM

Part 2: Trees (15 points)

For this section, put your answers in trees.ml. IMPORTANT: In this part, you may not use recursion unless otherwise specified. CourseNana.COM

Higher-order functions aren't just for lists! Recall the algebraic data type of binary trees from lecture: CourseNana.COM

    type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree

In this section, you'll implement and use higher-order functions over trees. CourseNana.COM

As an example, we implemented the function tree_fold : 'a tree -> 'b -> ('a -> 'b -> 'b -> 'b) that folds over trees like List.fold_right folds over lists. For example, CourseNana.COM

    tree_fold (Node (v1, Node (v2, Leaf, Leaf), Leaf)) u f

is f v1 (f v2 u u) u. CourseNana.COM

Note that our implementation isn't tail-recursive. The Cornell book (linked from the course website) gives a tail-recursive version. CourseNana.COM

  1. Implement the function tree_map : 'a tree -> ('a -> 'b) -> 'b tree that returns a tree with the same structure as the original tree, but with the given function applied to every node. Use tree_fold. Do not use recursion.

There are various ways of traversing a tree to flatten it. Consider the tree below. CourseNana.COM


An in-order traversal goes down the left subtree of a node first, then visits the node itself, then the right subtree. A in-order traversal of the above tree would visit nodes in the order 4, 2, 5, 1, 3. You can think of this as basically visiting the nodes left-to-right as they're drawn on the page. CourseNana.COM

A pre-order traversal visits the node itself, then the left subtree, then the right subtree. A pre-order traversal of the above tree visits the nodes in the order 1, 2, 4, 5, 3. CourseNana.COM

  1. Implement the function inorder : 'a tree -> 'a list that lists the nodes of a tree in the order given by an in-order traversal. (So, inorder applied to the above tree would give [4;2;5;1;3]. Use tree_fold. Do not use recursion. CourseNana.COM

  2. Implement the function preorder : 'a tree -> 'a list that lists the nodes of a tree in the order given by an pre-order traversal. (So, preorder applied to the above tree would give [1;2;4;5;3].) Use tree_fold. Do not use recursion. CourseNana.COM

Part 3: Expression evaluation (10 points)

For this section, put your answers in "expression.ml". CourseNana.COM

In this section, we'll work with a datatype that represents arithmetic expressions of a single variable. This is actually defined as two data types: CourseNana.COM

    (* Binary operators. *)
    type binop = Add | Sub | Mul | Div | Pow ;;
    type expression =
      | Num of float
      | Var
      | Binop of expression * binop * expression
      | Neg of expression

Num a represents the floating-point number a. Var represents the only variable, which we'll call x. Binop (e1, o, e2) represents a binary operation on subexpressions e1 and e2. The binary operation is given by o of type binop which can be Add, Sub, Mul, Div, or Pow. Neg e is the negation of e (e.g., Neg (Num 1.0) represents -1). CourseNana.COM

For example, we could represent 3.0x2 + x + 2.0 as CourseNana.COM

    Binop (Binop (Neg (Num 3.0), Mul, Binop (Var, Pow, Num 2.0)),
           Binop (Var,
                  Num 2.0)

(There are other ways we could represent it too.) CourseNana.COM

Parsing expressions

We've provided functions (below the definition of the data types, in a large block of code you can ignore) for parsing strings into expression datatypes. You may find this helpful when testing your code, unless you particularly like manually typing things like the expression above. The parser is reasonably robust, but not great, so you may need to fiddle around a bit to get your strings in the right format. We can get the above expression by running CourseNana.COM

    parse "~3.0*x^2 + x + 2.0";;

Note that we use ~ instead of - to represent negation. This lets the parser distinguish between negation and subtraction. We also need to explicitly include the * between ~3.0 and x^2 rather than just concatenating the two like we do when writing math normally. CourseNana.COM


Write a function evaluate : expression -> float -> float. The application evaluate e v should substitute v for x in the given expression and evaluate it to a float. For example, CourseNana.COM

    # evaluate (parse "~3.0*x^2 + x + 2.0") 0.0
    - : float = 2.0

    # evaluate (parse "~3.0*x^2 + x + 2.0") 1.0
    - : float = 0.0

    # evaluate (parse "~3.0*x^2 + x + 2.0") 2.0
    - : float = -8.0

Your implementation may be recursive (it need not be tail-recursive). CourseNana.COM


As before, you can test your code by adding assert statements after each function, then compiling the program using CourseNana.COM

make CourseNana.COM

This time, this will produce three separate binaries, one for each file. You can run them using the appropriate command, ./hof, ./trees and ./expression. CourseNana.COM

A note on testing trees.ml: We defined trees t1, t2, and t3, which you can use in tests. t3 is the tree shown in the picture above. CourseNana.COM

A note on testing expression.ml: It's not a good idea to use = on floats (as we discussed in class, 1.0 as a floating point number can easily become 1.00000000001 for reasons outside your control, and those won't be seen as equal). Instead, we've provided the float_eq function for you to use in assert tests. float_eq a b returns true if a and b are close to each other, even if they're not exactly equal. CourseNana.COM

Extra questions

These questions are worth 0 points, but are nevertheless important. Answer these questions in expression.ml. CourseNana.COM

  1. Fill in students_collaborated_with with a list of strings giving the names of other students with whom you discussed this homework, and urls_consulted with a (string) list of web URLs or other resources you consulted while doing the homework. Be as specific and thorough as possible, within reason. Remember that this helps clear up confusion if we have any questions about your work. If either answer is "None", you should still fill in the empty list ([]). CourseNana.COM

  2. Also fill in minutes_worked with the (approximate) number of minutes you spent working on this assignment. Your honest feedback will help us with future assignments. CourseNana.COM


When you are done with your work, make sure you have compiled your code using make (and ideally tested it using the instructions above). Submissions that do not compile will receive no credit. When finished, simply commit your changes and push them to our shared private GitHub repository. Please note that your submission date will be based on your most recent push (unless you let us know to grade an earlier version). CourseNana.COM

Make sure to git add all three .ml files before you commit so we see your changes, and make sure to git push. Double check Github and make sure you can see your latest code. There are no automatic tests this time. CourseNana.COM


Get in Touch with Our Experts

Wechat WeChat
Whatsapp Whatsapp
US代写,IIT代写,Illinois Institute of Technology代写,CS 440代写,Programming Languages and Translators代写,ADTs and HOFs代写,US代编,IIT代编,Illinois Institute of Technology代编,CS 440代编,Programming Languages and Translators代编,ADTs and HOFs代编,US代考,IIT代考,Illinois Institute of Technology代考,CS 440代考,Programming Languages and Translators代考,ADTs and HOFs代考,UShelp,IIThelp,Illinois Institute of Technologyhelp,CS 440help,Programming Languages and Translatorshelp,ADTs and HOFshelp,US作业代写,IIT作业代写,Illinois Institute of Technology作业代写,CS 440作业代写,Programming Languages and Translators作业代写,ADTs and HOFs作业代写,US编程代写,IIT编程代写,Illinois Institute of Technology编程代写,CS 440编程代写,Programming Languages and Translators编程代写,ADTs and HOFs编程代写,USprogramming help,IITprogramming help,Illinois Institute of Technologyprogramming help,CS 440programming help,Programming Languages and Translatorsprogramming help,ADTs and HOFsprogramming help,USassignment help,IITassignment help,Illinois Institute of Technologyassignment help,CS 440assignment help,Programming Languages and Translatorsassignment help,ADTs and HOFsassignment help,USsolution,IITsolution,Illinois Institute of Technologysolution,CS 440solution,Programming Languages and Translatorssolution,ADTs and HOFssolution,