OCAML Final

A value is an expression (values are a subset of expressions).

True

In OCaml, functions taking a string as an argument always produce a string as the result.

False

In OCaml, floats are represented as the ratio of two integers.

False

Structurally recursive functions may diverge on some inputs.

False

An expression is

a computation that evaluates to a value.

A list value in OCaml can be any of the following (select all that apply):

-a cons cell containing a data element and the rest of the list. -the empty list -a cons cell containing a data element and the rest of the list.

In OCaml, floats have infinite precision.

False

if 0 then "a" else "b"

is not well-typed.

Which of the following are values (select all that apply)?

17 false "hello world"

OCaml evaluates a function call by evaluating the function's body after substituting the values of the arguments for the function's formal parameters.

True

How many distinct values? type typeA = | ACon1 | ACon2 of bool * bool

5

Let A and B be sets defined by A = {0, 1}, B = {0, 2}. Then, the cartesian product A × B =

{(0, 0), (0, 2), (1, 0), (1, 2)}

Lists in OCaml are mutable.

False

Let A and B be sets defined by A = {0, 1}, B = {0, 2}. Then, the disjoint union (as defined in class) A ∪⁺ B is:

{(0, 0), (0, 1), (1, 0), (1, 2)}

A function f : A → B is surjective iff

∀ y ∈ B, ∃ x ∈ A, f(x) = y

How many distinct values? type typeC = | CCon of bool * typeC

0

Let A and B be sets defined by A = {0, 1}, B = {0, 2}. Then, the intersection A ∩ B =

{0}

A function f : A → B is injective iff

∀ x y ∈ A, f(x) = f(y) ⇒ x = y

The following OCaml type has how many distinct values? type typeB = | BCon1 of bool | BCon2 of bool * typeB

∞

Let A and B be sets defined by A = {0, 1}, B = {0, 2}. Then, the union A ∪ B =

{0, 1, 2}

Lists in OCaml can only contain elements of type int or string.

False

'fold_right' (right-associative fold) on lists can be implemented using only 'map' (i.e., 'map' is more general than 'fold_right').

False

The 'map' operation on lists can be implementing with 'fold_right' (right-associative fold) (i.e., 'fold_right' is more general than 'map').

True

((A * B) → C) ∼ (A → (B → C)) for all types A, B, and C (where '∼' denotes type equivalence)

True

(A * (B → C)) ∼ (A → (B → C)) for all types A, B, and C (where '∼' denotes type equivalence)

False

In OCaml, functions can be compared for structural equality by reference.

False

let rec filter f lst = match lst with | [ ] -> [ ] | x :: r -> if f x then x :: filter f r else filter f r What is the output of filter when "f x" is false for every x in the input list?

the empty list

Identify the correct structural and physical equality operators.

structural equality = structural inequality <> physical equality == physical inequality !=

let rec size x = match x with | [] -> 0 | h :: t -> 1 + (size t)

False

let rec list_gen i j acc = if i > j then acc else list_gen i (j-1) (j :: acc)

True

let rec list_gen i j acc = if i > j then acc else list_gen i (j-1) (j :: acc) ;; list_gen 1 6 [ ]

[1; 2; 3; 4; 5; 6]

Monads provide an abstraction of effects, and help to make sure that effects happen in a controlled order.

True

The name “monad” comes from the mathematical field of category theory, which studies abstractions of mathematical structures.

True

A promise is a mechanism for lazy evaluation.

False

Valid States of a Promise

Resolved Rejected Pending

Regardless of whether a promise was rejected, a promise can be resolved once and only once.

True MAYBE (False because if it is rejected it cannot be resolved).

The fundamental operations of an OCaml monad are:

Return and Bind

An OCaml sequence is a data structure that can contain an infinite amount of elements regardless the amount of memory available on a computer.

True

It is possible for recursive functions to diverge (loop forever).

True

Functions cannot be compared for structural equality.

True

Functions cannot be compared for physical equality.

False

In OCaml, all the elements of a list must have the same type.

True

Memoization

optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Sequence

Mathematically is an infinite list.

Lazy Evaluation

Do not compute until specifically demanded.

Interleaving

rapidly switch back and forth between computations.

Parallelism

use hardware that is capable of performing two or more computations literally at the same time.

nondeterministic

the order in which operations occur cannot necessarily be known ahead of time. Purely functional programs make nondeterminism easier to reason about, because evaluation of an expression always returns the same value no matter what.