Description
## Introduction
This exercise consists of a few short functions to help you familiarize yourself with OCaml. You can review the content of the discussion in [notes.rb](notes.rb), which includes the topics and examples from the discussion video.
### Testing & Submitting
You will submit this project to [Gradescope](https://www.gradescope.com/courses/171498/assignments/718825). You may only submit the **disc5.ml** file. To test locally, run `dune runtest -f`.
## Part 1: Currying and Partial Applications
These function are best implemented using the concepts of currying and partial application. While you are not _required_ to implement them in this way, it is **_highly_** recommended.
#### `mul_n n lst`
– **Type**: `int -> int list -> int list`
– **Description**: Given an int list, multiply every element in the list by `n`
– **Examples**:
“`ocaml
mul_n 3 [1;2;3] = [3; 6; 9]
mul_n 5 [1;2;3] = [5;10;15]
mul_n 0 [1;2;3] = [0;0;0]
mul_n 10 [] = []
“`
#### `join strs sep`
– **Type**: `string list -> string -> string`
– **Description**: Given a list of strings and a separator, return a new string that is each string concatenated with the separator inbetween them.
– **Examples**:
“`ocaml
join [“a”;”b”;”c”] “, ” = “a, b, c”;
join [“coffee”; “pizza”; “water”] ” and ” = “coffee and pizza and water”
“`
## Part 2: Option Functions
#### `list_of_option o`
– **Type**: `’a option -> ‘a list`
– **Description**: Take in an option and return `[]` of the option is `None` or `[a]` if the option is `Some a`.
– **Examples**:
“`ocaml
list_of_option None = []
list_of_option (Some 1) = [1]
list_of_option (Some (Some 3)) = [Some 3]
“`
#### `match_key k p`
– **Type**: `’k -> ‘k*’v -> ‘v option`
– **Description**: If the pair `p`’s key matches `k` returns the value as an option. Otherwise return `None`
– **Examples**:
“`ocaml
match_key 1 (1, “str”) = Some “str”
match_key 2 (1, “str”) = None
match_key “key” (“key”, “pizza”) = Some “pizza”
match_key “not key” (“key”, “pizza”) = None
“`
## Part 3: LengthLists
For this part, you will be working with the `lengthlist` type. This type is meant to represent the idea of _run length encoding_ – essentially, compressing a list by grouping terms together if there are _multiple_ of the same term in a row. For example, the list `[1;1;1;1;2;2;2;3;3;4]` can be represented as, for example, using tuples of the form `(value, count)`, `[(1,4); (2, 3); (3, 2); (4, 1)]`.
The `’a lengthlist` type encodes this idea, while keeping the linkedlist structure of the default OCaml list. The type is defined as in below:
“`ocaml
type ‘a lengthlist =
Cons of (‘a * int * ‘a lengthlist)
| Empty
“`
Now, we would represent the above list as `Cons(1, 4, Cons(2, 3, Cons(3, 2, Cons(4, 1, Empty))))`. We ask you to implement the following functions for length lists.
#### `length_to_list llst`
– **Type**: `’a lengthlist -> ‘a list`
– **Description**: Converts a lengthlist into its equivalent Ocaml list.
– **Examples**:
“`ocaml
lengthlist Cons(1, 4, Cons(2, 3, Cons(3, 2, Cons(4, 1, Empty)))) = [1;1;1;1;2;2;2;3;3;4]
lengthlist Empty = []
lengthlist Cons(“hi”, 2, Cons(“hello”, 3, Empty)) = [“hi”; “hi”; “hello”; “hello”; “hello”]
“`
#### `map fn llst`
– **Type**: `(‘a->’b) -> ‘a lengthlist -> ‘b lengthlist`
– **Description**: Recreate the map function, but for lengthlists. Note that we only operate on the elements, and not the number of each element.
– **Examples**:
“`ocaml
map (+ 3) Cons(1, 4, Cons(2, 3, Cons(3, 2, Cons(4, 1, Empty)))) = Cons(4, 4, Cons(5, 3, Cons(6, 2, Cons(7, 1, Empty))))
map string_of_int Cons(1, 4, Cons(2, 3, Cons(3, 2, Cons(4, 1, Empty)))) = Cons(“1:, 4, Cons(“2”, 3, Cons(“3”, 2, Cons(“4”, 1, Empty))))
“`
#### `decrement_count llst`
– **Type**: `’a lengthlist -> ‘a lengthlist`
– **Description**: Remove one of each element in the lengthlist. If the number of an element decreases to 0, remove it from the list entirely
– **Examples**:
“`ocaml
decrement_count Cons(1, 4, Cons(2, 3, Cons(3, 2, Cons(4, 1, Empty)))) = Cons(1, 3, Cons(2, 2, Cons(3, 1, Empty)))
decrement_count Cons(1, 4, Cons(2, 3, Empty)) = Cons(1, 3, Cons(2, 2, Empty))
decrement_count Cons(“str”, 1, Empty) = Empty
decrement_count Empty = Empty
“`
