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
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!)
*+-: int or real /: real div: int mod: int binding: [1/a]
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
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
pay attention to ascription when using a function
spend time to check function type-check, or else you receive 0 points
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
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
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
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?
How do you properly address the value of a function
things even with transparent transcription can't access
datatype if only type defined in signature
things not declared in signature
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