Cornell CS 3110 FlashCards (Prelim 1 Learning Objectives)

Cornell 3110 Learning Strategies + Vocab

State and define in your own words the five aspects of learning a programming language. (Basics 1)

State and define in your own words the five aspects of learning a programming language. (Basics 1)

Syntax: rules for a correct textually program in a language

Semantics: what does the program mean

Idioms: common ways to use language features to express computation

Libraries: bundles of code for you <3

Tools: just tools… (IDE, compiler, interpreter)

In your own words, explain the difference between: syntax and semantics; static and dynamic semantics; values and expressions. (Basic 1)

(what is it. what are the rules. what does it produce)

Syntax is what the language looks like to make it work, while semantics is how does it work, what does it mean.

Static semantics checks if the program is legal at compile-time. there are different types of static semantics. These are type-checking rules. This will produce a type or fail. Dynamic semantics checks if the program is legal at run-time. These are evaluation rules. This will produce a value, an exception, or an infinite loop.

value: an expression that does not need any further evaluation

Given a primitive type that is [int], [float], [bool], [string], or [char], write a few values of that type, and write a few expressions of that type that are not values. (Basic 1)

int: 2
float: 2.0
bool: true
string: "yo"
char: 'a'

Translate a short, 1-line mathematical formula into an OCaml expression that computes the formula. The formula could involve integers, floating-point numbers, and Booleans, as well as arithmetic, logical, and relational operators. (Basic 1)

# 3.0 *. 5.0 
---
15.0

# let x = "hi"
---
string
# "abc".[0]
---
char = 'a'

Given a desired type [int] or [float], correctly choose the numeric operators for addition, multiplication, etc. on that type. (Basic 1)

int: +, -, *

float: +., -., *.

you gotta do conversions to: int_of_float, float_of_int

In your own words, explain the difference between structural equality and physical equality, and choose the appropriate operator symbol, [=] vs [==], [<>] vs [!=], for each. Correctly choose which kind of equality should be used for all code written at this point in the course.

(Basic 1)

(Answer: use only structural equality until we introduce mutable features such as references aka pointers.) the == and != compares physical equalities.

structural equal: two objects have the same value?

physical equality: same location in memory?

State from memory the dynamic and static semantics for [if] expressions. (Basic 1)

static semantics:

if e1 : bool` and e2 : t1 and e3 : t1, then (if e1 then e2 else e3) : t1dy

dynamic semantics:

if e1 => true and e2 => v1

• then if e1 then e2 else e3 => v1

if e1=> false and e3 => v2

• then if e1 then e2 else e3 => v2

Given a well-typed expression involving operators and literals (i.e., values of primitive types), state the value to which it reduces, and explain how it reduces to that value using the dynamic semantics; and, state the type of the expression, and explain why it has that type using the static semantics. Or, given an ill-typed expression, explain using the static semantics why it does not type check. (Basic 1, Basics 2))

Example 1:

1. let x = 7 in if true then 4 else 5

2. let x = 8 in (let x = 9 in (let x = 10 in x) + x) + x)

3. let f x = x + 1 in f true

(todo: find some examples from lecture)

in general:

static semantics:

if e1: t1 and, under the assumption that x: t1, it holds that e2: t2

then (let x = e1 in e2) : t2

dynamic semantics:

if e1 => v1, and under the assum. that x =v1, we have that e2 => v2,

then (let x = e1 in e2) => v2

examples:

1. let x = 7 in if true then 4 else 5

static:

• 7: int,

• we assume that x: int, typecheck that if true then 4 else 5 : int

  • true: bool

  • typecheck 4 (4 : int)

  • typecheck 5 (5 : int)

  • so (if ture then 4 else 5) : int

• then (let x = 7 in if true then 4 else 5) => int

dynamic:

• if 7 => 7

• under the assume that x = 7, we evaluate if true then 4 else 5 => 4.

• then (let x = 7 in if true then 4 else 5) => 4

2.let x = 8 in (let x = 9 in (let x = 10 in x) + x) + x)

note: if given something like this, i would just rewrite the scoped x into

(let x = 8 in (let x’ = 9 in (let x’’ = 10 in x’’) + x’) + x)

static:

8 : int

• under the assum. that x : int, we typecheck: (let x = 9 in (let x = 10 in x) + x) + x)

• 9 : int

• under the assum. that x’ : int, we typecheck (let x = 10 in x) + x)

• 10: int

• under the assum. that x’’ : int, we typecheck (let x = 10 in x)

  • x : x’’ : int

• ((let x = 10 in x): int + x’: int) : int

• (let x = 9 in (let x = 10 in x) + x) + x): int

  then (let x = 8 in (let x = 9 in (let x = 10 in x) + x) + x) : int

dynamics:

• 8 => 8

• under the assumption that x = 8, we evaluate (let x = 9 in (let x = 10 in x) + x) + 8)

• 9 => 9

• under the assumption that x’ = 9, we evaluate (let x = 10 in x) + 9 + 8

• 10 => 10

• under the assumptation that x’’ = 10, we evaluate 10+9+8 = 27

3. let f x = x+1 in f true

   Type of f: f is a function that takes an int and returns an int. The inferred type of f is int -> int because x is added to 1, and + expects both arguments to be of type int.

   Function application: The function f is applied to the argument true, which has type bool.

   The function f expects an argument of type int, but it is being applied to an argument of type bool. This violates the function's type signature, causing a type error.

Launch and quit the OCaml toplevel, utop. Enter phrases into it and explain in your own words what the response means. (Basic 1)

utop

then to quit use either ctrl+D or #quit;;

From the terminal, open VS Code, create a new “.ml” file, enter code into that file, launch utop, load the “.ml” file with the [#use] directive in utop, and enter phrases into utop that make use of the code from the file.

(Basic 1)

# #use "name of .ml file";;

must use another #

given a let expression, circle the parts of it that are the binding expression, and the body expression.

(Basics 2)

For example, in let x = 5 in x + 2, "x = 5" is the binding expression, and "x + 2" is the body expression.

Given an identifier, state whether it is in camel case or snake case. Rewrite it to be in the other case. State which case is idiomatic/legal in OCaml

(Basics 2)

• snakecase is legal and idiomatic

• camecalse with no capital starting letter is legal but not idiomatic

• camelcase with caiptal starting letter is illegal for certain identiifers (not modules)

Given a snippet of code, state whether it is a [let] definition, [let] expression, or neither.

1. let x = 5 in x + 2

2. let x = 5

3. let 

4. let square x = x * x in square 5 + square 6 

(Basics 2)

• let defintion is defining something (global scope and part of top-level definitions)

• let expression always has the in keyword

Given an identifier and a one-sentence specification of the value it should contain, write a [let] definition that satisfies the specification. Examples: “[x] should be [y] plus [1]”, “compute the average of floats [a], [b], and [c], and store it in [avg]”, “given a string [str], let [plural] be [str] with an [“s”] at the end”.

(Basics 2)

1. 
let y = ...
let x = y + 1

2. 
let a = ...
let b = ...
let c = ...
let avg = (a +b +c) /. 3.

3. 
let str = ...
let plural = str ^ "s"

Given a sequence of [let] definitions, predict how utop would respond to each definition. Explain in your own words what each response means.

1. let square n = n * n
2. let greeting = "Hello, world!"
3. let add a b = a + b
4. let x = 5 in x + 3
5. let rec factorial n =
	if n = 0 then 1
	else n * factorial (n-1)
6. let pair = (10, "then")

(Basics 2)

if there’s a variable name and not limited to a local scope. val represents a successful binding.

val name : type 

however there isn’t a variable name or limited to a local scope

- : type

= <fun> shown when defining a function, indicating that it is ready to be invoked

examples:

1. val square: int → int = <fun>

2. val greeting: string = “Hello, world!”

3. val add: int → int → int = <fun>

4. - : int = 8

5. val factorial : int → int = <func>

6. val pair: int * string = (10, “then”)

Correctly evaluate a [let] expression containing identifiers with overlapping scope, aka shadowing.

Example: [let x = 5 in (let x = 6 in x) + x].

(Basics 2)

best to rewrite it as

let x = 5 in (let x’ = 6 in x’) + x)

you can substitute in x’ and x with the bindings from each let x = … let x’ = ….

in the end it will be 6 + 5 = 11

State from memory the Principle of Name Irrelevance, and how it is relevant to substitution.

(Basics 2)

the name of the variable does not matter, so if two expressions are only different in their variable names, then they are treated as equal during evaluations. So have to be careful and consistent with it.

Substitution is the process of replacing a variable in an expression with another expression. Variable Binding: When substituting a variable in a function or expression, the name of the variable being replaced does not matter. What matters is the structure of the expression and the binding of variables.

Given a condition that should hold at a point in a program, add an [assert] expression to the program to check that the condition does indeed hold.

(Basics 2)

usually for me its

assert (x = true)

Explain in your own words the difference between a type annotation and a type cast.

(Basics 2)

• Type Annotation:

  • Specifies what type a variable or expression should be.

  • Used primarily for documentation and type checking.

  • Does not change the actual value's type; it only informs the type system of the expected type.

• Type Cast:

  • Converts a value from one type to another.

  • Used to forcefully treat a value as a different type for compatibility.

  • Can potentially lead to errors if the conversion is not valid.

Given a well-typed expression with some subexpression called out, add a type annotation that keeps the expression well-typed. Example: you are given [1 + 2] and asked to add an annotation to subexpression [1].

(Basics 2)

Answer: [(1 : int) + 2].

State from memory the dynamic and static semantics for anonymous function expressions. and function application expressions. (this is a combination of two learning objectives).

(Basics 3)

static semantics

anonymous function:

x1 : t1, ..., xn : tn and e : u
then (fun x1 .... xn -> e) is t1 -> ... -> tn -> u

function application:

remember e0 represents the function (and thus including the input type)

if e0 : t1 -> ... -> tn -> u
and e1 : t1, 
    ...
    en : tn
then e0 e1 ... en : u

dynamic semantics

for [e0 e1 … en]

1. evaluate subexpressions

   e0 => v0, … , en => vn

   v0 must be a function: fun x1 … xn → e

2. for v1, … vn, substitute vi for xi in e, yielding new expression e’

3. evaluate e’ ==> v

4. result is v

Given a well-typed expression involving anonymous functions, state the value to which it reduces and explain how it reduces to that value using the dynamic semantics; and, state the type of the expression, and explain why it has that type using the static semantics.

1. let add = fun x y -> x + y in add 3 4

(Basics 3)

Dynamic Semantics:

1. The anonymous function fun x y -> x + y is defined and bound to add.

2. When calling add 3 4, the arguments 3 and 4 are bound to x and y, respectively.

3. The body of the function, x + y, evaluates to 3 + 4, which results in 7.

• Type Inference: The type of the function add can be inferred as int -> int -> int, meaning it takes two int arguments and returns an int.

• Since 3 and 4 are both int, they conform to the expected type, making the overall expression type-checked successfully.

Explain in your own words why "method" is incorrect vocabulary for OCaml functions.

(Basics 3)

functions are first-class citizens and do not belong to objects or classes, which is what ‘methods’ are in different programming languages.

Explain in your own words what "syntactic sugar" means.

(Basics 3)

"Syntactic sugar" refers to syntax within a programming language that is designed to make code easier to read and write, without adding any new functionality. It provides a more convenient or expressive way to achieve something that could be done with more complex or verbose syntax.

Given a function definition let f = fun x1 .. xn -> e restate it without an anonymous function.

(Basics 3)

Answer: [let f x1 .. xn = e]. Or vice versa.

Given a [let] expression restate it as an anonymous function application. Or vice versa.

1. let f x1 ... xn = e
2. let x = 5 in x + 2

(Basics 3)

1. let f = fun x1 ... xn = e
2. (fun x = x + 2) 5 
(* don't exactly need let x anymore *)

tips: always use the fun keyword

When asked to write a recursive function, correctly insert the [rec] keyword in the appropriate place.

(Basics 3)

i mean… it’s between let and the name of the function

Given a function type [t1 -> ... tn -> u], identify what the type of each argument is, and what the type of the output is.

1. int -> float -> string

(Basics 3)

the last type is always the output. we can have as many inputs as we want.

1. the two inputs are int and float, and the output is a string

Given a well-typed expression involving function applications, and all other language features learned so far, state the value to which it reduces, and explain how it reduces to that value using the dynamic semantics; and, state the type of the expression, and explain why it has that type using the static semantics. Or, given an ill-typed expression, explain using the static semantics why it does not type check.

1. let add = fun x y -> x + y in add 3 4

2. let f = fun x -> x + 1 in f "Hello"

(Basics 3)

usually for the type checking, i can just say the type result for the function and i think i should be all set.

example 1:

let add = fun x 

Dynamic Semantics:

1. The anonymous function fun x y -> x + y is defined and bound to add.

2. When add 3 4 is called, 3 is bound to x and 4 is bound to y.

3. The body of the function, x + y, evaluates to 3 + 4, which results in 7.

Final Value:

• The entire expression evaluates to 7.

Static Semantics:

• Type Inference: The type of add can be inferred as int -> int -> int, indicating that it takes two int arguments and returns an int.

• The argument types 3 and 4 are both int, matching the expected types of the function parameters. Thus, the expression is well-typed.

example 2:

let f = fun x -> x + 1 in f "hello"

Static Semantics Explanation:

1. The function f is defined to take an argument x and return x + 1. This indicates that x must be of type int since + is used, which requires numeric operands.

2. However, in the expression f "Hello", the argument is a string ("Hello"), which does not match the expected type of int for x.

3. Therefore, the static semantics of the language will raise a type error because f is being applied to an argument of the wrong type.

Given a function of multiple arguments, state the type of the function after being partially applied to fewer arguments.

1. let add = fun x y -> x + y
   add 3

(Basics 3)

1. The original type for add is `int → int → int

2. the partial application is add 3 so that is int - > int . the function has to take one more int and returns an int.

Given a multiple-argument anonymous function, state the desugaring of it to single-argument anonymous functions.

1. fun x y -> x + y

(Basics 3)

1.
fun x-> fun y -> x + y
(* breakdown from left to right *)

Given a function type with multiple arrows, fully parenthesize it.

1. [int -> int -> int].

2. ['a -> 'b -> 'c -> 'd]

Answer:

1. [int -> (int -> int)].

2. ‘a → (‘b → (‘c → ‘d))

Tip: function types are right associative.

(Basics 3)

Given a function application with multiple arguments, fully parenthesize it.

Example:

1. [f x y z].

2. max 3 5 7

(Basics 3)

Answer:

1. [((f x) y) z].

2. [(max 3) 5) 7]

Tip: function application is left associative.

Given a function, state a polymorphic type for it.

Examples:

1. [let id x = x].

2. [let f x y = x].

(Basics 3)

1. ['a -> 'a].

2. ['a -> 'b -> 'a] or ['b -> 'a -> 'b].

just for clarification:

A polymorphic type means that a function or expression can work with arguments of many different types rather than being restricted to a single type. In OCaml, polymorphism is often represented by type variables, which are usually written as 'a, 'b, 'c, etc.

Given an expression that uses an infix operator, rewrite it to make the operator a prefix function. Or vice versa.

Example:

1. [x + y].

2. ( * ) x y

(Basics 3)

Answer:

1. [( + ) x y]

2. [x*y]

Given an expression that applies a function to an operator, rewrite it to use the pipeline (aka reverse application) operator.

Example:

1. [f x].

2. sqrt 16

3. 
let f x = x + 2
let g x = x * 3
let h x = x - 1
(* use pipeline for *)
h (g (f 5))

4. 
let square x = x * x
let double x = x * 2
let increment x = x + 1
let halve x = x / 2
let negate x = -x
(* use pipeline for *)
negate (halve (square (double (increment 3))))

5.
let negate x = -x
let increment x = x + 1
let multiply x y = x * y
(* use pipeline for *)
negate (increment (multiply 5 6))

(Basics 3)

Answer:

1. [x |> f].

2. [16 |> sqrt].

3. 5 |> f |> g |> h
4. 3 |> increment |> double |> square |> halve |> negate

tips:

you kind work left to right (innermost to outermost) for the order for the pipeline operations.

for multiple arguments, we can use tuples to hold arguments. for complex multi-argument functions, we can use tuples or fun to define a quick anonymous function for transforming your data between steps.

(5, 6) |> (fun (x,y) -> multiply x y) 
|> increment |> negate

Explain in your own words why the call stack can overflow because of recursion. Explain in your own words why tail recursion solves this problem.

(Basics 3)

basically each time you make recursive call, program creates a new frame on the call stack. this frame just holds information. when there’s alot of frames, so the recursion becomes deep, it can lead to stack overflow.

tail recursion makes recursive the last operation. there is no other work to do after the recursive call returns. then, ocalm optimizes by reusing the current frame, instead of creating a new frame. This is called tail call optimization (TCO).

Given a recursive function, state whether it is tail recursive or not.

1. let rec factorial_tail n acc =
  if n = 0 then acc
  else factorial_tail (n - 1) (n * acc)
2. let rec sum n =
  if n = 0 then 0
  else n + sum (n - 1)

(Basics 3)

basically, if the last operation is a recursive call, and nothing else

1. yes

2. no

Given a recursive function that is not tail recursive, rewrite it to be tail recursive by adding an accumulator argument.

let rec fib n =
  if n <= 1 then n
  else fib (n - 1) + fib (n - 2)

(Basics 3)

usually when you define the recursive function, also add an additional argument acc

the base case and other branches usually change. it important to figure out what acc will be when you call the recursion.

in this case, our accumulator is a.

let rec fib n a b = 
 if n = 0 then a
 else fib (n-1) b (a+b)
	

Given a tuple type, write a tuple value that has that type. Or, vice versa, given a tuple value, state its type.

1. string * int

2. (true, [1;2;3])

(Data and Types 1)

1. (“hi”, 1)

2. bool * (int list)

State from memory the dynamic and static semantics of tuples.

(Data and Types 1)

Dynamic Semantics (Runtime behavior):

if ei ==> vi then (e1, …, en) ==> (v1, … , vn)

Static Semantics (Type checking):

• if ei : ti then (e1, … , en) : t1 * … * tn

For example, in the expression (1, true, "example"), the types of the components are int, bool, and string, so the type of the entire tuple is int * bool * string.

Given a function that takes a pair as input, use [fst] and [snd] to access the components of that pair.

let pair_example (x,y) = 

(Data and Types 1)

let pair_example (x,y) = 
 let first = fst (x,y) in
 let second = snd (x,y) in
 (first, second)

pair_example (5, "hello")  (* Output: (5, "hello") *)

state from memory the types of [fst] and [snd].

(Data and Types 1)

fst: ‘a * ‘b → ‘a

snd: ‘a * ‘b → ‘b

Given a list type such as [int list], write a list value that has that type. Or, vice versa, given such a list value, state its type.

1. int list

2. ["apple"; "banana"; "cherry"]

(Data and Types 1)

basically ready right to left

1. [2; 3; 5']

2. string list

State the syntax for nil and cons.

(Data and Types 1)

nil: []

cons: ::

Given a list and a value, write an expression with cons to prepend that value onto the list.

(Data and Types 1)

val :: lst

Given a list written in square-bracket notation, transform it to use nil and cons.

Example:

1. [1; 2; 3].

(Data and Types 1)

Answer: 1 :: 2 :: 3 :: []. Or vice versa.

i mean this isnt that bad, just always go from left to right

Given a list value, circle which part is the head and which part is the tail.

1 :: 2 :: 3 :: []

(Data and Types 1)

head is always the first element

tail is always the rest (AS A LIST)

head: 1

tail: [2;3]

Given a list type, state what the type of its head would be. Also state what the type of its tail would. Explain in your own words why those types must be different.

(Data and Types 1)

head: ‘a

tail: ‘a list

they are different because tail is the rest of the list, so the type must be a list, while the head is only one element within the list, so it matches the element type of the list.

State from memory the dynamic and static semantics of nil and cons.

(Data and Types 1)

static semantics:

nil:

[] : ‘a list

cons:

if e1 : t and e2 : (t list)

then (e1 :: e2) : (t list)

Given a nested list type such as [int list list], write a list value that has that type. Or, vice versa, given such a list value, state its type.

(Data and Types 1)

[[1;2;3;]; [2;4]]

just read from right to left to the list type, and for the list itself, inner out

Given a specification for a function that takes a list as input, write a recursive implementation that uses pattern matching to handle the base case and recursive case. The function might be one you have seen before, or a new function.

Examples: sum, product, concat.

(Data and Types 1)

let rec sum = function
  | [] -> 0
  | h :: t -> h + sum t

let rec product = function
 | [] -> 1
 | h :: t -> h * product t

let rec concat = function
 | [] -> ""
 | h :: t -> h ^ concat t 

Given an OCamldoc comment involving lists, identify which uses of square brackets indicate lists vs. typesetting of code. Example: Raises [Failure "hd"] if [lst = []].

(Data and Types 1)

Answer: only the [] is a list; the other brackets indicate to OCamldoc to typeset as code in HTML.

Given a [match] expression, circle which branch will be chosen. If the pattern for that branch has identifiers, state the values to which those identifiers will be bound in the branch.

let result = match [1; 2; 3] with
  | [] -> "empty"
  | x :: y :: z :: [] -> "three elements"
  | _ -> "default"

let result = match [[1]; [2; 3]; []] with
  | [] -> "empty list"
  | [x] :: [y; z] :: [] -> "oh"
  | [x] :: rest -> "no"
  | _ -> "default case"

let result = match (1, [2; 3; 4]) with
  | (x, []) -> "yessss"
  | (x, y :: z :: rest) -> "oh"
  | (x, _ :: y) -> "hey"
  | _ -> "default case"

(Data and Types 2)

1. in this example, there are three elements in the lst, so we pick the 2nd branch.

in the exam, probably should be careful of top branches that take up all the possibilities

let result = match [[1]; [2; 3]; []] with
  | [] -> "empty list"
  | [x] :: [y; z] :: [] -> "nested list with one element in first and two in second"
  | [x] :: rest -> "first has one element, binding rest"
  | _ -> "default case"

the [x] :: rest branch will be executed, because there is one element, and everything else is binded to rest.

the [x] :: [y; z] :: [] branch doesn’t work because there are three elements in the list, and only two are given.

let result = match (1, [2; 3; 4]) with
  | (x, []) -> "tuple with an empty list"
  | (x, y :: z :: rest) -> "tuple with a list of at least two elements"
  | (x, _ :: y) -> "tuple with a non-empty list"
  | _ -> "default case"

• (x, y :: z :: rest): This branch matches if the list contains at least two elements, with y bound to the first element, z bound to the second, and rest bound to the remaining list (if any). This pattern matches the input:

  • x = 1

  • y = 2

  • z = 3

  • rest = [4]

Thus, the second branch is chosen with x = 1, y = 2, z = 3, and rest = [4].

Given an English description of a desired pattern, write the OCaml code for that pattern. You might need to use deep pattern matching.

Examples: "a pattern that matches lists with exactly three elements", "a pattern that matches any triple and binds only its third component", "a pattern that matches the empty list", "a pattern that matches exactly the integer 42", "a pattern that matches everything".

(Data and Types 2)

1.
let rec match_three = function
| a :: b :: c :: [] -> "good"
| _ -> "bad"

2.
let rec match_triple = function
| (_,_,a) -> a

3. let rec match_empty = function
 | [] -> "yes"
 | _ -> "noooo"

4. let rec match_42 = function
 | 42 -> "yes" 
 | _ -> "no" 

5. let rec match_everything = function
 | _ -> "yes"

Given a pattern match that binds identifiers in some patterns, rewrite the patterns to eliminate any unnecessary bindings and replace them with wildcard.

Example: [let rec length lst = match lst with [] -> 0 | h :: t -> 1 + length t].

let rec length lst =
  match lst with 
  | [] -> 0
  | h :: t -> 1 + length t 

(Data and Types 2)

Answer:

let rec length = function | [] -> 0 | _ :: t -> 1 + legth t

We can replace h with a wildcard _ because the value of the head is irrelevant to the computation.

Given a function that uses pattern matching, rewrite it to eliminate the [match] keyword and replace it with the [function] keyword. Or vice versa.

let rec length lst = match lst with
  | [] -> 0
  | _ :: t -> 1 + length t

(Data and Types 2)

let rec length = function
  ... the same 

• basically you can replace match with function if the last argument provided for the function is the one you will be matching

State from memory the dynamic and static semantics of [match].

(Data and Types 2)

static semantics:

• if e : ta

• and for all i it holds that (the matched branch i)

  • pi : ta

  • ei : tb

• then

(match e with 
 | p1 -> e1
 | ...
 | pn -> en): tb

dynamic semantics:

image from presentation

Given an expression using the [@] operator, state the value to which it evaluates.

Example: [[1; 2] @ [3; 4]].

(Data and Types 2)

Answer: [[1; 2; 3; 4]].

The @ operator concatenates two lists, producing a new list by appending the second list to the first.

Implement the append operator yourself as a recursive function.

(Data and Types 2)

let append lst1 lst2 = match lst1 with

 | [] -> lst2
 | h :: t -> h :: (append t lst)

The append function recursively prepends the head (h) of lst1 to the result of appending the tail (t) of lst1 to lst2. The base case is when lst1 is empty ([]), in which case it returns lst2

State from memory the types of [::] vs [@]. Use those types to explain whether an expression involving those operators is well-typed, or what its type is.

(Data and Types 2)

:: : `a → `a list → `a list

so :: for uno elemento

@ : `a list` → `a list` → `a list`

Explain in your own words what two extended static checks the compiler does for [match] expressions.

(Data and Types 2)

Answer: would involve exhaustiveness and unused branches.

The compiler checks whether all possible cases for the value being matched are covered. If any cases are missing, the compiler will issue a warning about non-exhaustive pattern matching.

The compiler checks for patterns that are never matched because previous patterns already cover all the possible cases. These unused patterns are considered redundant, and the compiler issues a warning.

Given a [match] expression that is not exhaustive, but without seeing the compiler warning/error, improve it to be exhaustive without using the wildcard pattern. Or, give an example of a value that would trigger an exception because of the inexhaustiveness.

let describe_option opt = match opt with
  | Some x -> "Has value"

(Data and Types 2)

let describe_option opt = match opt with
  | Some x -> "Has value"
  | None -> "lol"

Given a [match] expression that has unused branches, but without seeing the compiler warning/error, improve it to have no unused branches.

(Data and Types 2)

let describe_list lst = match lst with
  | [x] -> "Single element"

Value: An empty list [] would trigger a Match_failure exception because the pattern [x] only matches lists with exactly one element, and no pattern is provided for the empty list ([]).

to fix it, just add another branch for _ → “blah”

Use a pattern match to access the components of a tuple and bind some or all of them to names.

Examples: extract only the second component of a triple, extract both components of a pair.

(Data and Types 2)

1. 
let (_, y, _) = (1, 2, 3)

2. 
let (x, y) = (10, 20)

Given a statement of what information a record needs to contain, write a record type definition.

Example: define a record type for students who have names and class years.

(Data and Types 3)

records need to store fields and use keyword type .each field is separated by a comma.

type student = {
  name : string;
  class_year: int;
}

Given a record type definition, write an expression that has that type.

type student = {
  name : string;
  class_year: int;
}

(Data and Types 3)

we can create a student called taylor swift

let taylor = { name = "Taylor Swift"; class_year = 2027}

State from memory the dynamic and static semantics of record expressions.

(Data and Types 3)

static semantics:

{f1 : t1; ... ; fn : tn}
if for all i in 1...n
 - ei : ti
and if  t is defined to be {f1 : t1; ... fn : tn}
then {f1 = e1; ...' fn = en} : t

for a specific record element
if e:t1 and if t1 := {...; f : t2; ...}, then e.f : t2

the order of the fi:ti is irrelevant.

dynamic semantics:

if for all i in 1...n, it holds that ei ==> vi, then
{f1 = e1; ...; fn = en} ==> {f1 = v1; ...; fn = vn}

if e ==> {...; f = v; ...} then e.f ==> v

Given a record, use dot notation to access a field. Or, use pattern matching to access some or all of the fields.

type student = {
  name : string;
  class_year: int;
}

let taylor = { name = "Taylor Swift"; class_year = 2027}

(Data and Types 3)

let name = taylor.name
let year = talor.class_year

you can also use pattern matching

let { name = student_name; class_year = year } = taylor

(* this will spit out:
val student_name : string = "taylor swift"
val year : int = 2027
*)
(* its reversed in my thinking so be careful *)

Given a record, use record copy syntax to create a copy of the record with some of the fields changed. Or, given an expression that uses record copy, state the value of the expression.

type student = {
  name : string;
  class_year: int;
}

let taylor = { name = "Taylor Swift"; class_year = 2027}

(Data and Types 3)

let taylor2 = {taylor with name = "taylor johnson"}

>>> val taylor2 : student = {name = "taylor johnson"; class_year = 2027}

Given a description of some information a program needs to store, choose which of these is most appropriate and state why: list, tuple, record. Or state the tradeoffs that would be involved between them.

Example:

• Scenario: You need to store a student’s name, class year, and GPA.

• Scenario: You need to store a point in 2D space, with an x and y coordinate.

• Scenario: You need to store a list of prices of items in a shopping cart.

Tradeoffs: ?

(Data and Types 3)

1. I would use a record because every student need these fields. you also want to name eeach field to make it clear which piece of data corresponds to each field.

2. I would use a tuple because it will always store exactly two elements. The size and type of tuples are fixed, which makes it efficient and concise for such structured, fixed-size data.

3. I would use a list because you have multiple items (where the number of items could be unknown), with the same type (most likely float). Dynamic collection with homogenous types are for lists 🔥

Tradeoffs:

• List: Lists are for homogeneous collections of elements of the same type. Since the data about a student involves different types (name as string, year as int, GPA as float), a list would not work well here.

• Tuple: Tuples can store values of different types, but they do not provide names for the fields, making the code harder to understand and maintain. You would have to remember the order of the elements.

• Record: Records are most appropriate because they allow for heterogeneous data and meaningful field names, improving clarity and readability.

Given a recursive function on lists, state whether it is tail recursive or not.

let rec sum lst = match lst with
  | [] -> 0
  | h :: t -> h + sum t

(Data and Types 3)

1. not tail recursive, because you are adding a h D:

Transform a non-tail recursive function on lists into a tail recursive function by adding an accumulator argument.

let rec sum lst = match lst with
  | [] -> 0
  | h :: t -> h + sum t

reversing a list:

let rec reverse lst =
  match lst with
  | [] -> []
  | h :: t -> reverse t @ [h]

flatten a nested list:

let rec flatten lst =
  match lst with
  | [] -> []
  | h :: t -> h @ flatten t

fibonacci numbers

let rec fib n =
  if n <= 1 then n
  else fib (n - 1) + fib (n - 2)

computer the power of a number

let rec pow x n =
  if n = 0 then 1
  else x * pow x (n - 1)

(Data and Types 3)

let rec sum lst acc = match lst with
| [] -> acc
| h :: t -> sum t (acc+h) 

(* the initial call will be sum lst 0)

reversing a list

let rec reverse lst acc =
  match lst with
  | [] -> acc
  | h :: t -> reverse t (h :: acc)

(*the initial  call will be reverse lst [] *)

flatten a nested list

Consider a list of lists. You want to flatten this list into a single list.

let rec flatten lst acc =
  match lst with
  | [] -> acc
  | h :: t -> flatten t (acc @ h)
(* acc @ h not h @ acc or else ya gonna reverse it lol *)

fibonacci numbers

let rec fib n a b =
  if n = 0 then a
  else fib (n-1) b (a+b)

(*initial call is fib n 1 1. there are
2 accumulators *)

computing the power of a number

let rec pow x n acc =
  if n = 0 then acc
  else pow x (n-1) (acc*x)

(*initial call is pow x n 1 *)

In your own words, explain what a type synonym is.

(Data and Types 3)

a type synonym is another name for an existing type. can make it more simpler or more understandable. you dont make a new type.

Use a type synonym to give a simpler name to a longer type. Examples: point, vector, matrix.

(Data and Types 3)

let point = float * float
let vector = float list
let matrix = float list list 

Given a variant type definition, circle which constructors are constant and which are non-constant.

type shape =
  | Circle
  | Square of float
  | Rectangle of float * float

(Data and Types 3)

• constant constructor are Circle because it doesn’t carry any additional data.

• non-const constructors are Square Rectangle . they carry data (float, float*float)

Given a variant type definition, write variant expressions to provide an example value for each constructor.

type shape =
  | Circle
  | Square of float
  | Rectangle of float * float

(Data and Types 3)

let c = Circle
let s = Square 2.0
let r = Rectangle (3.0, 4.0)

>>> ---
val c : shape = Circle
val s : shape = Square 2.
val r : shape = Rectangle (3., 4.)

State from memory the dynamic and state semantics of variant expressions.

(Data and Types 3)

static semantics:

• for constant variant C

  if t = … | C | ..

  then C : t

  C - a pattern

• for non-constant variant expressions C e

  if t = …. | C of t’ | …

  and e : t’

  then C e : t

dynamic semantics

• for constant variant C

  already a value

• for non-constant variant expressions C e

  if e ==> v then C e ==> C v

Given some information that needs to be represented in a program, design a variant type to do so.

Examples: colors (need all colors of da rainbow)

shapes, coins, employees.

(Data and Types 3)

type colors = | Red | Green | Blue  

type shape = 
| Circle 
| Square of float
| Rectangle of float*float

type Coin = | Penny | Nickel | Dime | Quarter

type employee = {
	name : string;
 	age : int;
	occupation : string;
	salary : float;
}

Given a variant type definition and a specification of a function that takes that type as input, implement the function using pattern matching. The implementation may include extracting data from inside a constructor. The constructor might carry data that involves tuples or records or other data types.

Example:

1. determine the center point of a shape, convert a color from RGB to HSV (given appropriate formulas),

2. determine the most frequent coin in a purse

3. determine the aggregate salary of a list of employees.

1. colors 
type color = 
  | Red
  | Green
  | Blue
  | Rgb of int * int * int

2. freq coin
type Coin = | Penny | Nickel | Dime | Quarter

3.
type employee = { 
  name : string; 
  age : int; 
  salary : float 
}

(Data and Types 3)

let rgb_to_hsv color = 
match color with
  | Red -> (0, 100, 100)   (* Example values for hue, saturation, and value *)
  | Green -> (120, 100, 100)
  | Blue -> (240, 100, 100)
  | Rgb (r g, b) ->
  	(* do some awesome, math *)
    let h = 5 in
    let s = 6 in
    let v = 7 in
    (h,s,v)

for types with extra fields, we can treated them like normal tuples

let totalsalary lst acc = 
  match lst with
  | [] -> acc
  | { salary; _} :: rest -> totalsalary rest (acc +. employee.salary)

type employee_list = employee list

In your own words, distinguish one-of types from each-of types. Give examples of both.

(Data and Types 3)

one-of-types: one variant at a type (so circle, square, triangle)

each-of-types: multiple pieces of data are grouped together, like student’s gpa, name, year.

Given a few types that need to be stored in a list, design a variant type that simulates a "heterogeneous" list containing mixed types. Write expressions that create lists of that type.

(Data and Types 3)

we use a type variant

type Num =
| Int of int
| Float of float 

let mixed_list = [Int 1; Float 2.5; Int 3; Float 4.1]

Given a function specification, implement a function that processes lists of that type. Example: the list needs to contain both floats and ints; write a function that sums all the numbers as floats.

type Num =
| Int of int
| Float of float 

let mixed_list = [Int 1; Float 2.5; Int 3; Float 4.1]

(Data and Types 3)

let rec aggregate lst acc = match lst with
  | [] -> acc
  | Int n :: rest -> aggregate rest (acc +. float_of_int n) 
  | Float f :: rest -> aggregate rest (acc +. f)
  

Explain in your own words what "algebraic data types" are. State the two different terms that ADT abbreviates.

(Data and Types 3)

Algebraic Data Types (ADT) are types constructed from sum types (variant types) and product types (record/tuple types), so you can provide flexible data modeling by combining different types.

Answer: the other is "abstract data type".

Explain in your own words why options are safer than [null].

Lecture 8 (Data and Types 4)

null will cause runtime error and null pointer exception, while options allow your code to still run logically. Some(value) or None is a type, so developers have to handle it, so it prevents runtime and null references.

State from memory the variant type definition of [option].

Lecture 8 (Data and Types 4)

type 'a option = None | Some of 'a 

Given an option value, use pattern matching to extract and return the value from inside it, or to return a default value if there is nothing inside the option.

example 1: return the max of a lst. if it is empty then return None. otherwise return Some number

Lecture 8 (Data and Types 4)

usually it’s in this format:

let extract_or_default opt default =
  match opt with
  | Some value -> value  (* Extract the value if present *)
  | None -> default       (* Return default if None *)

Given a specification for a partial function, implement it using options such that it returns [None] when there is no meaningful output it can produce. Examples:

• the maximum value of a potentially empty list

• the first character of a possibly empty string,

• the result of dividing two possibly-zero integers.

Lecture 8 (Data and Types 4)

let max_of_list lst =
  match lst iwth
  | [] -> None
  | h :: t ->
     let rec list_max current_max = function
	| [] -> current_amx
	| h :: t -> list_max (Stdlib.max x h) t
     in list_max h t

(if you want pattern matching in a pattern matching, create another let definition)

let first_element word = function
  | "" -> None
  | c -> Some (List.nth c 0)

let divide num1 num2 = if num2 = 0 then None else (num1 / num2)

State from memory the type definition of OCaml's [list].

Lecture 8 (Data and Types 4)

type 'a list = [] | ( :: ) of 'a * 'a list 

- list is a type constructor parameterized on 'a
- :: is a (value) constructor, not a function 

Given a specification for a list operation, write the implementation of that operation. The specification might or might not be for an operation we have studied.

Examples: length, append, reverse, last, max of list, etc.

This flashcard will have: reverse, last, max of list

Lecture 8 (Data and Types 4)

let rec reverse lst acc = match lst with
 | [] -> acc
 | h :: t -> reverse t (h :: acc)

let rec last = function
| [] -> []
| h :: [] -> h
| h :: t -> last t

let max_of_list lst acc = match lst with
| [] -> acc
| h :: t -> max_of_list t (max h acc)

Given an implementation of a list operation, state its asymptotic time and/or space complexity (i.e. running time and/or space in Big Oh notation).

let rec length lst =
  match lst with
  | [] -> 0                      (* Base case: empty list has length 0 *)
  | _ :: tail -> 1 + length tail (* Count the head and recursively count the tail *)

let length lst =
  let rec aux lst acc =
    match lst with
    | [] -> acc
    | _ :: tail -> aux tail (acc + 1)
  in
  aux lst 0

let rec reverse lst = 
  match lst with
  | [] -> []
  | head :: tail -> reverse tail @ [head]

let reverse lst =
  let rec aux lst acc =
    match lst with
    | [] -> acc
    | head :: tail -> aux tail (head :: acc)
  in
  aux lst []

Lecture 8 (Data and Types 4)

• The time complexity of the length function is O(n), where n is the number of elements in the list. This is because the function needs to traverse the entire list to count its length.

• The space complexity of length function is O(n), because the function is not tail recursive, we use up space on the call stack proportional to the number of students

second example:

• O(n) time complexity. same reasoning

• space O(1), because we are using the call stack using tail recursion.

third example:

• Time: O(n^2) – Each call to reverse takes O(n) time to append the single element to the end of the reversed list.

• Space: O(n) – The space used is proportional to the size of the list.

• example: [1 2 3 4 5]

  • reverse [2 3 4 5] @ [1]

  • reverse [3 4 5] @ [2]

  • reverse [4 5] @ 3

  • reverse [5] @ 4

  • reverse [ ] @ 5

  • [ ]

  • each @ will traverse through the list to put the head element at the end

fourth example (tail recursion):

Time Complexity: O(n) – Now the function only traverses the list once. Space Complexity: O(n) – The function uses space proportional to the size of the list for the accumulator.

Some general tips:

Analyzing time and space complexity for list operations in OCaml generally follows these patterns:

• Traversing the entire list means O(n) time complexity.

• Recursive functions on lists are often O(n) in space if not tail-recursive, while tail-recursive functions can have O(1) space complexity.

• Operations that involve creating new lists (like map, append, or filter) tend to have O(n) space complexity because a new list of the same size is created.

Given a variation on OCaml's [list] type definition, perform either of the above tasks with it (i.e., implement an operation, state complexity.)

1. custom list that tracks if list is empty, contains one element, or has multiple elements. implement an operation that compute the length of the custom_list

type 'a custom_list = 
  | Empty 
  | Single of 'a 
  | Cons of 'a * 'a custom_list

Lecture 8 (Data and Types 4)

let rec length = function
| Empty -> 0
| Single _ -> 1
| Cons (_,t) -> 1 + length t

This will be O(n) time complexity and O(n) space. If needed, we could use tail recursion and make it O(1) space.

Given a key type and a value type, state the association-list type that would bind such keys to such values.

1. key type: string, value type: int

Lecture 8 (Data and Types 4)

the typical syntax is:

type ('k, 'v) assoc_list = ('k * 'v) list

1. (string * int) list

Given a specification of the association list lookup, insert, or remove operation, write the implementation of that operation. The specification might be the same as we've studied, might be the same as OCaml's [List] module, or might be a variation on those.

Note: when did we ever do this lecture? why do i remember nothing from this??

1. (** [lookup k lst] is [Some v] if association list [lst] binds key [k] to
    value [v]; and is [None] if [lst] does not bind [k]. *)

2. (** [insert k v lst] is an association list that binds key [k] to value [v]
    and otherwise is the same as [lst] *)

3. A key of type 'k that you want to remove from the association list.
An association list (which is a list of key-value pairs) of type ('k * 'v) list. A new association list where the first occurrence of the specified key has been removed. If the key does not exist in the list, the original association list should be returned unchanged.

Lecture 8 (Data and Types 4)

1.
let lookup k list = match lst with
| [] -> None
| (k', v) :: t -> if k = k' then Some v else lookup k t
(* remember we can access the pair with just a tuple D: *)

2. 
let insert k v lst = (k,v) :: lst

3.
let remove k lst =
  let rec aux lst =
    match lst with
    | [] -> [] 
    | (k', v) :: t -> 
        if k' = k 
        then t (* Skip the current pair and return the rest of the list *)
        else (k', v) :: aux t 
  in
  aux lst

(* usually don't use @ unless you have to cuz its qutie inefficient *)

Given an implementation of an association list operation, state its asymptotic time and/or space complexity.

let rec assoc_lookup key lst =
  match lst with
  | [] -> None
  | (k, v) :: tail -> if k = key then Some v else assoc_lookup key tail

Lecture 8 (Data and Types 4)

O(n) time but O(1) space since it is tail recursive

State a type definition for a binary tree type in which nodes store values and leaves do not. Or, state a definition that is a variation on that in which values might be stored at nodes and/or leaves. Or, state a definition for a general (non-binary) tree in which each node may have any number of children. Given a specification, write an operation on that type, and state its asymptotic time and/or space complexity.

1. for a binary tree, write ethe type definition and then write an operation to calculate the depth of the tree

2. a general tree with any number of children, write the type definition

Lecture 8 (Data and Types 4)

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

In this tree:

• Leaf represents a leaf with no value.

• Node(value, left, right) represents a node that stores a value and has two child nodes (left and right).

let rec tree_depth tree =
  match tree with
  | Leaf -> 0
  | Node (_, left, right) -> 1 + max (tree_depth left) (tree_depth right)

time complexiity: O(n)
space complexity: O(n) 

type general_tree = 
| Leaf
| Node of 'a * ( 'a general_tree list ) 

let rec depth tree =
  match tree with
  | Leaf -> 0  (* A leaf has a depth of 0 *)
  | Node (_, children) ->
      1 + (List.fold_left (fun acc subtree -> max acc (depth subtree)) 0 children)

(* without high-order programming *)
let rec depth tree =
  match tree with
  | Leaf -> 0  (* A leaf has a depth of 0 *)
  | Node (_, children) ->
      let rec max_depth_of_children children =
        match children with
        | [] -> 0  (* No children, so the max depth is 0 *)
        | first_child :: rest ->
            let first_child_depth = depth first_child in
            let rest_max_depth = max_depth_of_children rest in
            max first_child_depth rest_max_depth
      in
      1 + max_depth_of_children children

Given a description of a desired new variant type, write the OCaml type definition for it. The definition might require type parameterization or type recursion.

Examples:

• a type for natural numbers in unary or binary,

• a type for a standard 52-card deck,

• a type for propositions (as in "propositional logic" from CS 2800).

• Given a specification, write an operation on that type, and state its asymptotic time and/or space complexity.

  • Write pseudocode for a function [eval : prop -> string list -> bool] such that [eval p vs] evaluates proposition [p] under the assumption that all the propositional variables named in [vs] are true and all other propositional variables are false.

more information for the propositions:

An atom aka a propositional variable is a propositional expression.

If e1 and e2 are propositional expressions, then:

NOT(e1) is a propositional expression, usually written ¬e1.

AND(e1, e2) is a propositional expression, usually written e1 ∧ e2.

OR(e1, e2) is a propositional expression, usually written e1 ∨ e2.

IMPLIES(e1, e2) is a propositional expression, usually written e1 ⇒ e2.

For example, IMPLIES(AND(p, q), OR(p, q)) is a propositional expression in which p and q are propositional variables. Usually it would be written p ∧ q ⇒ p ∨ q.

Design an OCaml type named [prop] to represent propositional expressions. Assume that propositional variables are represented as strings.

Lecture 8 (Data and Types 4)

1. natural numbers in unary or binary (i litearlly dunno what this means LMAO)

type nat = 
  | Zero
  | Succ of nat

(* convert a unary natrual number to an int *)
let rec nat_to_int n =
 match n with
 | Zero -> 0
 | Succ x -> 1 + nat_to_int n

O(1) time 
O(1) space 

2. a type for a standard 52 card deck

type suit = Hearts | Diamonds | Clubs | Spades
type rank = type rank = Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten | Jack | Queen | King | Ace

(* nice to just combine them with a tuple *)
type card = rank * suit
type deck = card list 

3. for proposition you can

   • an atom

   • a proposition

   • compound propositions

type prop =
| Atom of string (* base case *)
| “NOT’ of prop
| “AND” of prop * prop
| “OR” of prop * prop
| “IMPLIES” of prop * prop

(*since its base case string, use string, or something idk *)

(*
Write pseudocode for a function [eval : prop -> string list -> bool] such that [eval p vs] evaluates proposition [p] under the assumption that all the propositional variables named in [vs] are true and all other propositional variables are false. *)

let eval prop vs = match prop with
| Atom x -> (let rec within props = match props with | [] -> false | h :: t -> if h = x then true else within t)
| Not p -> <> eval p
| And (p, p') -> eval p && eval p'
| Or (p, p1) -> eval p || eval p1
| Implies(q,r) -> (eval Or(Not(q), r))

Explain in your own words why "catch all" cases are problematic.

Lecture 8 (Data and Types 4)

usually with _ wildcard. it can hide potential issues, missed paterns, hides logic errors, and no type safety, and can lead to errors.

Given a match expression that uses a catch-all case, rewrite the expression to eliminate the catch-all case and still be exhaustive.

type coin = | Penny | Nickel | Dime | Quarter

let describe_coin coin =
  match coin with
  | Penny -> "Penny"
  | Nickel -> "Nickel"
  | _ -> "Unknown coin"

Lecture 8 (Data and Types 4)

let describe_coin coin =
  match coin with
  | Penny -> "Penny"
  | Nickel -> "Nickel"
  | Dime -> "Dime"
  | Quarter -> "Quarter"

Given a name and the data it should carry, declare a new exception.

1. make one called InsufficientFunds that takes in a float of data

Lecture 8 (Data and Types 4)

exception InsufficientFunds of float

exception InsufficientFunds of float