Review 003

Link to the Exam

Here

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

• Question 1 (08:40): type stuff

• Question 2 (09:22):

• Question 3 (10:04): search question in continuation, exception..

• Question 4 (10:46): proof (easier)

• Question 5 (11:28): require thoughts

• 12 pages

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

• raise handle: same type in 2+ places

• write down type to merge(WHAT IS THE WORD FOR MERGE?)

• raise does not propagate into function

• raise expect 1 argument of type exn

• remember transcription type reference with dot

• even with transparent transcription, REPL prefer structure.type instead of built-in

• structures don't have type

• (See Q2.30)

• remember to write the function name for detypify

Modules

• pay attention to ascription when using a function

• spend time to check function type-check, or else you receive 0 points

Lazy

• not to do something is easy, just add a layer

Imperative

• you can store (change) thing in variable, as well as function by staging

Work & Span

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

• Number of levels: log n

• Number of nodes at level i: 2^i

• Work per node at level i: c

• sum_{i=0}^{log n} c2^i

• 2^{log n} = n

If containing n

• replace n with n/[number_of_nodes_at_level_i=2^i_include_untravel]

Math

• log(a/b) = log a - log b

• TODO: calculous sum over i

CPS

• remember to call k after you done calculating

• remember edit predicate function

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

Question 2.30

How do you properly address the value of a function

Question 2.30

things even with transparent transcription can't access

• datatype if only type defined in signature

• things not declared in signature

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?