COMP302 OCaml HW2
## Introduction
Copyright By PowCoder代写 加微信 powcoder
This week’s topics include list manipulation, the use of List module functions, user-defined datatypes and recursive datatypes. The following resources might be useful : [Stdlib functions](https://caml.inria.fr/pub/docs/manual-ocaml/libref/Stdlib.html) and [List functions](https://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html).
## Question 1 : Frequency Analysis (30%)
Statistics play an important part in computer science. As such, it is important to encode even the simplest statistical functions. For example, Natural Language Processing (NLP) is a field that uses a lot of statistics. It is often needed in NLP to evaluate the most common elements of language, as it helps with sentence generation. In particular, n-grams, an n-long subsequence of elements of language, are studied and used in depth.
For this question, you must write tests for and implement two functions: `mode` and `pair_mode`.
1. `mode : ‘a list -> ‘a` is a function that takes a list containing *any-type (‘a)* elements and returns the most common one (aka the mode of the distribution represented by the list). The tests should be placed in the list named `mode_tests`; however, while these tests assume that mode is used on integers, your function should remain generic. In case of tie-breakers (two or more elements are presently the same, highest number of times in the list), return the smallest one.
*Hint 1:* You are allowed to use the function call `List.sort compare (your list here)`. This sorts your list with the default comparison function. This also means that in the case of tie-breakers, the “lower” value should be returned.
*Hint 2:* A tail-recursive helper might be required!
2. `pair_mode : ‘a list -> ‘a * ‘a` takes any list and returns the most common pair of consecutive elements (or bi-gram) in the list.
*Hint 1:* You should be using `mode` within this function!
*Hint 2:* A lot of List. module functions may be useful here – make sure to consult them.
Did you know?
There are guaranteed relationships between the median, mean and mode of all unimodal (ones that have only one mode) distributions. For example, both the median and the mean must be at most 3√ standard deviations away from the mode, while the difference between the median and the mean is at most 0.6√ standard deviations. [[Source\]](https://doi.org/10.1137%2FS0040585X97975447)
## Question 2 : Custom data types (45%)
OCaml features an important concept in computer science: strong static typing. However, unlike many other languages, OCaml also allows you to create your own data types, beyond the common approaches taken by other languages such as enums and classes. What’s great about that is that it allows us to properly apply a concept called *Curry-Howard correspondence* in practice – by using types with very specific definition, we can make our code correct by construction of types.
Food for thought
In 1998, NASA launched the Orbiter, a satellite that was supposed to study the Martian climate and atmosphere. However, on September 23rd, 1999, it was lost as it likely burned in the atmosphere of Mars. This error, in a mission that cost 327.6 million USD, was caused by incorrect software which produced calculations in the wrong unit of measurement, using pounds-of-force instead of Newtons. This could have been avoided if a language was used where the compiler could detect that the wrong units of measurement were used, and either flag the error or silently convert to the correct units. [[Source\]](http://www.cnn.com/TECH/space/9909/30/mars.metric.02/index.html)
Observe in the prelude the definition of the types `dist_unit, time_unit, speed_unit` and `’a value`. Using these defintions, build a set of converting functions:
1. `convert_time : time_unit value -> time_unit -> time_unit value`
2. `convert_dist : dist_unit value -> dist_unit -> dist_unit value`
3. `convert_speed : speed_unit value -> speed_unit -> speed_unit value`
All of these take a value (a floating point number with the corresponding unit) to convert, as well as the unit required. The output should be again a appropriate `value` type, with the unit corresponding to the second argument to the function. Some useful constants for you:
– There are 3600 seconds in an hour.
– There are 5280 feet in a mile.
– A foot is 0.3048 meters.
*Hint 1:* Pattern matching will help you a lot here.
*Hint 2:* `convert_speed` should be implemented by using the other two functions – but be careful with time conversions!
Now that we have functions that can guarantee output of certain units, we can use these functions to actually calculate simple things with these quantities! Implement two more functions, `add_speed : speed_unit value -> speed_unit value -> speed_unit value`, which adds two speed values together and returns the output in the unit of the second argument; and `dist_traveled : time_unit value -> speed_unit value -> dist_unit value`, which calculates the distance traveled if the speed given was maintained for the time given. The distance unit must be the same one used inside the speed unit.
## Question 3 : Recursive data types (25%)
Recursive data types are quite common. One of the most basic data structures studied in COMP 250, the linked list, relies on nodes which have pointers to the node before and after, effectively making it a recursive data type. Trees of all kind are the next best use of recursive types, and this question is about them – both computer science and biological ones.
Did you know?
Leonardo da Vinci (1452-1519) was one of the greatest minds to ever live. Between all his accomplishments, da Vinci has made an observation about trees (the ones outside). A rephrasing of his original statement is that the sum of surface areas of all child branches is equal to the surface area of the parent branch. In 2014, researchers from the University of Tokyo showed that this is linked to, although not in such a simple relationship, tension and stress experienced by the plants during growth. [[Source\]](https://doi.org/10.1371%2Fjournal.pone.0093535)
The prelude contains the `tree` type defintion, along with one example of a tree. Each branch can contain other branches, and each branch also has a value associated to it corresponding to its thickness or width (effectively its diameter). Your goal is to write tests for and implement the function `passes_da_vinci : tree -> bool` which verifies, for each branch within the tree, that the sum of squares of its child branches’ widths is less than or equal to the square of this branch’s width. You can use 0 as the width of a `Leaf`. The tests should be placed in the `passes_da_vinci_tests` list.
*Hint 1:* You will likely need a helper function that computes the sum of squares of a list of trees.
*Hint 2:* You might also need a different helper function to assist you with recursing on the list of children branches / subtrees.
(* Section 1 : Lists *)
(* Question 1.1 : Most common element of *sorted* list *)
let mode_tests: (int list * int) list = [] ;;
let mode (l: ‘a list) : ‘a =
let rec aux l ((cur_el, cur_num) : ‘a * int) ((max_el, max_num) : ‘a * int) =
notimplemented ()
notimplemented ()
(* Question 1.2 : Most common consecutive pairing *)
let pair_mode_tests: (int list * (int * int) ) list = [] ;;
let pair_mode (l: ‘a list) : ‘a * ‘a =
notimplemented ()
(* Section 2 : Custom data types *)
let convert_time ((from_unit, val_) : time_unit value) to_unit : time_unit value =
notimplemented ()
let convert_dist ((from_unit, val_) : dist_unit value) to_unit : dist_unit value =
notimplemented ()
let convert_speed ((from_unit, val_) : speed_unit value) to_unit : speed_unit value =
notimplemented ()
let add_speed (a : speed_unit value) ((b_unit, b_val) : speed_unit value) : speed_unit value =
notimplemented ()
let dist_traveled time ((speed_unit, speed_val) : speed_unit value) : dist_unit value =
notimplemented ()
(* Section 3 : recursive data types/induction *)
let passes_da_vinci_tests : (tree * bool) list = [] ;;
let rec passes_da_vinci t =
notimplemented ()
let notimplemented () =
failwith “This function is not yet implemented.”
(* Question 2 *)
type dist_unit = Foot | Meter | Mile
type time_unit = Second | Hour
type speed_unit = dist_unit * time_unit
type ‘a value = ‘a * float
(* Question 3 *)
type tree = Branch of float * tree list | Leaf
let tree_example =
Branch (5., [
Branch (3., [Leaf; Leaf; Leaf]);
Branch (4., [])
**let** pair_mode (l: ‘a list) : ‘a * ‘a =
notimplemented ()
*(** *Section 2 : Custom data types* **)*
**let** convert_time ((from_unit, val_) : time_unit value) to_unit : time_unit value =
notimplemented ()
**let** convert_dist ((from_unit, val_) : dist_unit value) to_unit : dist_unit value =
notimplemented ()
**let** convert_speed ((from_unit, val_) : speed_unit value) to_unit : speed_unit value =
notimplemented ()
**let** add_speed (a : speed_unit value) ((b_unit, b_val) : speed_unit value) : speed_unit value =
notimplemented ()
**let** dist_traveled time ((speed_unit, speed_val) : speed_unit value) : dist_unit value =
notimplemented ()
*(** *Section 3 : recursi**v**e data types/induction* **)*
**let** passes_da_vinci_tests : (tree * bool) list = [] ;;
**let** **rec** passes_da_vinci t =
notimplemented ()
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com