Review 003

Link to the Exam

Here

don't try the last question if not finished. (170min, 5 + 42min/Q)

Built-in

O(1)<O(log(log(n)))<O(log(n))<O(log(n)^2)<O(n)<O(n*log(n))<O(n^2)<O(2^n)<O(n!)

Simple

*+-: int or real /: real div: int mod: int binding: [1/a]

Hard

o : (’b -> ’c) * (’a -> ’b ) -> (’a -> ’c) map : ('a -> 'b) -> 'a list -> 'b list map map : ('a -> 'b) list -> ('a list -> 'b list) list fn L = > body List.filter : (’a -> bool) -> ’a list -> ’a list foldr : (’a * ’b -> ’b) -> ’b -> ’a list -> ’b foldl : (’a * ’b -> ’b) -> ’b -> ’a list -> ’b

foldr (op ::) [] == id foldl (op ::) [] == rev

List.concat zip: (‘a list * ‘b list) -> (‘a * ‘b) list filter: ('a -> bool) -> 'a list -> 'a list inord: turn tree into list Fn.id

Password: Reps&Specs

Notes

Typing

Modules

Lazy

Imperative

Work & Span

When you have c+2W(n/2)

If containing n

Math

CPS

TODO: review problem 3, 4, 8, 10.2, 12 TODO: write down O(x) < O(x) stuff

TODO: read email

Questions for Office Hour

Task 3.1 ~ Task 3.3

Solution 1. This implementation is unsafe because it is transparently ascribing to the SET signature. There- fore, the type t is revealed to the user, meaning that they can construct whatever kind of tree they want. Notably, this menas they could construct a tree that does not obey the ordering property of the implementation, which could cause undefined behavior, such as being able to look-up elements that you did not insert into the “set”. This can be fixed by making TreeSet opaquely ascribe to SET.

Solution 3. This implementation is unsafe because the functor LenSet is transparently ascribing to the signature LENSET. While we cannot freely create values of type Nat . t and Set . t (which remain abstract), since we know that type t = Nat . t * Set . t, we can create two dif- ferent sets (with different values of Nat . t and mix and match their lengths and sets, creating sets whose lengths do not match the actual length of the set. This breaks our invariant. This can be fixed by making LenSet opaquely ascribe to LENSET.

Question: why does 3.3 says we can't freely create value of type Nat.t and Set.t, aren't we input these when we create the structure by functor? If we are only given function, then how can we modify in Task 3.1?

Question in Lecture

Why is this parameter, why not abstract

Why is this parameter, why not abstract

Question 2.30

How do you properly address the value of a function

Question 2.30

things even with transparent transcription can't access

TODO

review: n-Queens (important, with exceptions control flow, with continuation, with option at 44min) write lambda expression as value, instead of writing body functors and structure in test continuation review review stream of sieve (prime), memorizing stream red-black tree (unlikely) does short circuit also short circuit side effect, example?

Table of Content