# Review 003

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

## 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

## Questions for Office Hour

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 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?

Table of Content