Computer Science from Scratch

Let's take Brown University's cs19 Accelerated Introduction to Computer Science which is 2+ semesters condensed into one semester. If you only have access to a tablet or phone you can complete this entire course as there's nothing to install.

The professor teaching the course has a unique lecture style and specializes in research driven curriculum. See his talk here about curriculum design as an engineering problem and the failure of knowledge transfer defined to mean a skill learned in one context is used successfully in another. "Even the students who have taken theory of computation (decidability) can't recognize the unsolvable problem (in another course)". He has a 2019 talk here on teaching computer science given at an acm conference on intro to programming books and the problems they have when students escape the subset of the language the book is trying to use like generating confusing error messages. He has tried to fix this in the course we are about to take.

There is a heavy focus you will notice as we go through the course labs on higher-order functions, you will have to rewrite map/filter/fold for lists, trees, streams and your own MapReduce. As this is research driven curriculum, understanding the input/output behavior of these functions was found to help students later understand gigantic system APIs and industry software libraries.

In other words every aspect of introductory CS has been carefully considered with feedback on what actually works to teach this material, instead of opinion based curriculums which is what you find everywhere else.

There is a book The Computational Beauty of Nature where recursion, parallelism, iteration and other computational properties are all exampled with nature:

Collections, Multiplicity, and Parallelism Complex systems with emergent properties are often highly parallel collections of similar units. Ant colonies owe much of their sophistication to the fact that they consist of many ants. This is obvious, but consider the implications. A parallel system is inherently more efficient than a sequential system, since tasks can be performed simultaneously and more readily via specialization. Parallel systems that are redundant have fault tolerance. If some ants die, a task still has a good chance of being finished since similar ants can substitute for the missing ones. As an added bonus, subtle variation among the units of a parallel system allows for multiple problem solutions to be attempted simultaneously. For example, gazelles as a species actively seek a solution to the problem of avoiding lions. Some gazelles may be fast, others may be more wary and timid, while others may be more aggressive and protective of their young. A single gazelle cannot exploit all of the posed solutions to the problem of avoiding lions simultaneously, but the species as a whole can. The gazelle with the better solution stands a better chance of living to reproduce. In such a case, the species as a whole can be thought of as having found a better solution through natural selection.

This course has a placement which is reading from HtDP however the book we read for the class DCIC (or if you are using the 2020 PAPL book) will cover everything you need.

Watch the cs19 lecture titled Wed 9-5-18. Go to code.pyret.org (referred to as CPO) and click open editor as you follow along the lecture. The book will cover everything he's doing like what a list is, what a function is, this is just a demonstration of the online interpreter. You can run Pyret offline too.

Watch the Mon9/10/18 second lecture. The very first task, just imagine it in your head you don't have to actually write a program. Interesting lecture about the rainfall problem and the benefits of writing a lot of examples in order to understand badly defined problems. Data science/machine learning is brought up, as examples of dirty data. Higher-order functions are talked about, like filter and map which are in the Pyret documentation and we will learn in depth later. A filter goes through each element of the list and returns a new one based on some boolean you give it, and map applies a function to every link in the list returning a new list.

What to get out of this lecture "Data is noisy, produced by flaky hardware and buggy programs and you will have no choice but to clean the data". There's a video from the 'Advanced R' book author at the end, which is here and the gist of that talk is reducing things based on what is similar so you can generalize. We haven't done map/filter etc., but will quickly catch up by lecture 4. Reminder we skipped the placement where some of this was introduced.

In this example len1 calls len2 who calls len3 then repeats until the input is empty returning 0 which stops the ping-pong back and forth computation. If you remove the numbers from lenX and write a recursive function where len calls itself, conceptually this is still the same as calling multiple similar functions.

# Silly recursion simulator

fun len3(input):
  cases (List) input:
    | empty => 0
    | link(f, r) => 1 + len1(r)
  end
end

fun len2(input):
  cases (List) input:
    | empty => 0
    | link(f, r) => 1 + len3(r)
  end
end

fun len1(input):
  cases (List) input:
    | empty => 0
    | link(f, r) => 1 + len2(r)
  end
end

check "Recursion simulator":
  a = [list: 1, 2, 3]
  len1(a) is 3
end

Hand step that program using cut + paste substitution:

• len1([list: 1, 2, 3])
• 1 + len2([list: 2, 3])
• 1 + (1 + len3([list: 3]))
• 1 + (1 + (1 + len1(empty)))
• 1 + (1 + (1 + 0))

Rewrite it so len calls itself:

• len([list: 1, 2, 3])
• 1 + len([list: 2, 3])
• 1 + (1 + len([list: 3]))
• 1 + (1 + (1 + len(empty)))
• 1 + (1 + (1 + 0))

A lot of the intro courses make the concept of self-reference way more difficult than it actually is. The first course I took I was completely confused how the state worked since the function was being called again, not realizing it is a totally new and different copy of the function. This confusion is common.

Instead of using a delayed computation where you wait for all the calls to len to return, try a recursive function that doesn't use 're-entrancy' meaning the computation finishes before calling itself again, there doesn't need to be re-entrancy of concurrent calls sharing the same function (and in turn generating many stack frames, something we will also learn later) in order for a computation to be recursive.

fun len(input, accumulator):
  cases (List) input:
    | empty => accumulator
    | link(f, r) => len(r, 1 + accumulator)
  end
where:
  b = [list: 1, 2, 3]
  len(b, 0) is 3
end

Hand step:

• len([list: 1, 2, 3], 0)
• len([list: 2, 3], 1)
• len([list: 3], 2)
• len(empty, 3)
• 3

In the book SICP when you learn this, they point out the difference in shapes between recursive re-entrant code growing bigger and the shape of an iterative or accumulator implementation. My implementation requires annoying parameters like initializing the accumulator to zero, which can be hidden from the end user by use of a helper function, this is often in intro books called a trampoline you eval the code by going to the bottom of the function then jumping back into the body:

fun list-length(input):

  fun helper(i, acc):
    cases (List) i:
      | empty => acc
      | link(f, r) => helper(r, 1 + acc)
    end
  end

  helper(input, 0) #internal init of accumulator 
where:
  c = [list: 1, 2, 3]
  list-length(c) is 3 #nicer interface, single list parameter
end

Same function with optional type annotations, type 'A' and 'B' you will read soon are type variables, allowing this len function to consume bools, numbers, strings yet still be type checked in Pyret.

fun len<A>(input :: List<A>) -> Number:

  fun helper<B>(i :: List<B>, acc :: Number) -> Number:
    cases (List) i:
      | empty => acc
      | link(f, r) => helper(r, 1 + acc)
    end
  end

  helper(input, 0)
where:
  c = [list: 1, 2, 3]
  d = [list: "a", "b", "c"]
  e = [list: true, false]
  len(c) is 3
  len(d) is 3
  len(e) is 2
end

We're watching Wed9/12/18 lecture on sorting. We have almost caught up to the class now.

He walks through exactly what a template is and how to extract data to make a template, and spends the rest of the class writing insertion sort using only what we know so far. You have to hand step through it a little to understand what insertion sort is doing. Function sort is calling insert with insert(f, sort(r)) it isn't calling insert(f, r). This means insert f to sort(r), which is the sorted rest of the list.

This is the code on the board which you should have typed into CPO yourself:

fun insert(n :: Number, l :: List<Number>) -> List<Number>:
  cases (List) l:
    | empty => [list: n]
    | link(f, r) => if n <= f:
        link(n, l)
      else:
        link(f, insert(n, r))
      end
  end
where:
  # student given examples:
  insert(2,  [list: 3,4,5])   is [list: 2,3,4,5]
  insert(1,  [list: 0,1,1,2]) is [list: 0,1,1,1,2]
  insert(-1, [list: -2,0,3])  is [list: -2,-1,0,3]
  insert(3,  [list: ])        is [list: 3]
  insert(4,  [list: 1,2,3])   is [list: 1,2,3,4]
end

fun sort(l :: List<Number>) -> List<Number>:
  cases (List) l:
    | empty => empty
    | link(f, r) => insert(f, sort(r))
  end
where:
  sort([list: 3,2,1])        is [list: 1,2,3]
  sort([list: 1,2,3])        is [list: 1,2,3] 
  sort([list: 4,1,-1])       is [list: -1, 1, 4]
  sort([list: 0.1, 0, 0.11]) is [list: 0, 0.1, 0.11]
end

Let's step the evaluation by hand with [list: 0, 1, 3, 2] being input to sort(). Reaching the cases we have f = 0, r = [list: 1, 3, 2]. We call insert on f to sort(r) but computation is delayed as we have to wait for the calls to sort(r) to complete since everytime we enter the cases with a non empty list to sort, it calls itself with the rest of the list. We end up with this delayed computation:

• insert(0, (insert(1, (insert(3, (insert(2, empty)))))))

Evaluation starts at the most nested bracket, which is insert(2, empty):

• insert(2, [list: empty])
  • n = 2, l = empty
  • is list empty? yes so return [list: 2]
• insert(3, [list: 2])
  • n = 3, f = 2, r = [list: empty]
  • is 3 < 2?
  • no so link(2, insert(3, [list: empty])
  • return [list: 2, 3]
• insert(1, [list: 2, 3])
  • n = 1, f = 2, r = [list: 3]
  • is 1 < 2?
  • then it must the smallest in the entire list:
    • link(1, [list: 2, 3])
    • return [list: 1, 2, 3]
• insert(0, [list: 1, 2, 3])
  • is 0 < 1?
  • link(0, [list: 1, 2, 3])
  • return [list: 0, 1, 2, 3]
• no more delayed computations

The returns to sort():

• insert(0,(insert(1,(insert(3, [list: 2])))))
• insert(0,(insert(1, [list: 2, 3])))
• insert(0, [list: 1, 2, 3])

Everytime a list is returned, the next call to insert can happen because it is complete with insert(n, list).

The same algorithm is covered in this lecture at around 33:11 note where he shows the 3D diagram that we are calculating an angle to determine the distance between words (strings) in a document.

This assignment writeup seems purposely difficult to get us to write examples to help understand what the assignment wants. The dot product algebraic definition, look at the example for [1,3,-5] x [4,-2,-1]. Each index in the first list is multiplied by it's corresponding index in the second list, then those results are added together. To read the sigma notation, a*b = the sum of \(a_ib_i\) starting at index 1 (first element of the list) up to the length of the list (n). If a = [1₁ ,3₂, -5₃] and b = [4₁, -2₂, -1₃]:

\(a*b = \sum_{i=1}^3 a_ib_i\) = (\(1_{a1} * 4_{b1})+(3_{a2} * -2_{b2})+(-5_{a3} * -1_{b3})\)

Example vectors:

You may want to read the Pyret style guide you can also go through the Pyret github code, looking at how they write functions.

Stages of the Design Recipe

Try the design recipe for this assignment. Recall Prof K's paper where he tells us exactly how to start these assignments: write 'interesting examples' prior to any implementation. Interesting means an assertion that probes our understanding of the problem.

First step, analyze the values the program is working with, both input and output. The input is two lists of strings, who's case we ignore, and the output will be a value with square roots involved (irrational numbers), so we are dealing with Roughnums. Write the purpose and stub of the function:

fun overlap(doc1 :: List<String>, doc2 :: List<String>) -> Number:
  doc: "Consumes 2 documents, returns their overlap"
  ...
where:
end

Step 2 Understand the data definition. We need a distinct combined list of both documents, that ignores case, that is sorted, to represent the word freq count of each document.

Handwritten examples to figure out the data definition

Example input to overap:
doc-1 = [list: "a", "B", "c"]
doc-2 = [list: "d", "d", "D", "b"]

Distinct/lowercase and sorted combination of doc-1/doc-2
doc-1 + doc-2 [list: "a", "b", "c", "d"]

Vector of both against [list: "a", "b", "c", "d"]
doc-1-vec = [list: 1, 1, 1, 0] # 1a, 1b, 1c, 0d
doc-2-vec = [list: 0, 1, 0, 3] # 0a, 1b, 0c, 3d

Step 3 Write examples of calling the function (tests). From the 2015 chapter on examples: "Examples should cover at least all the different cases mentioned in the data definition, and also to test common extremes and base cases."

fun overlap(doc1 :: List<String>, doc2 :: List<String>) -> Number:
...
where:
  #vector [list: 1, 1, 0] and [list: 0, 0, 1]
  overlap([list: "a", "b"], [list: "c"]) is 0

  # vector [list: 1]
  overlap([list: "a"], [list: "a"]) is
  1 / num-max(num-sqr(num-sqrt(1)), num-sqr(num-sqrt(1)))

  # cover the upper/lower case: 
  # vector [list: 1, 1, 1, 0] and [list: 0, 1, 0, 3] 
  epsilon = 0.000000000000001
  num-abs(((overlap([list: "a", "B", "c"], [list: "d", "d", "d", "b"])) 
      - (1 / num-max(num-sqr(num-sqrt(3)), num-sqr(num-sqrt(10)))))) < epsilon is true
end

In these examples I calculated the dot product by hand and input them in the tests:

dot-product example

Both:
[list: 1,  1,  1,  0]
[list: 0,  1,  0,  3]
--------------------
       0 + 1 + 0 + 0 = 1

Itself:       
[list: 0,  1,  0,  3]
[list: 0,  1,  0,  3]
---------------------
       0 + 1 + 0 + 9 = 10
       
Itself:
[list: 1,  1,  1,  0]
[list: 1,  1,  1,  0]
---------------------
       1 + 1 + 1 + 0 = 3

If you have two different documents, like [list: "a"] and [list: "b"], then their vectors are [list: 1, 0] and [list: 0, 1] representing [list: a, b] the distinct list of both inputs. The dot-product = (1*0) + (0*1) or 0, and 0 divided by anything is 0. If the lists are both the same, like [list: 1] and [list: 1] then dot-product = 1 and our overlap equation is 1/1 or 1 .

The last test uses an epsilon displacement check which for the purposes of this assignment is any arbitrarily tiny displacement to use for equality checking. We take the output of overlap, subtract it from the output of the manual test, convert it to an absolute value which just means remove any negative signs and return a positive number, and see if this is less than our epsilon. Cut and paste the hand made test and run it, you'll see the output is ~0.099999.. a Roughnum we can't compare for equality with standard equals. There is a built-in 'is-roughly' to use in a test block instead of 'is' but the assignment wants us to write our own.

Write more tests, such as an epsilon displacement test for 2 bigger documents that are the same, since the output will be a Roughnum like ~0.999999 you can't directly compare to 1.

Step 4 Write the function. The tests we wrote gave us our overlap equation:

# import the list library
import lists as L

fun overlap(doc1 :: List<String>, doc2 :: List<String>) -> Number:
  doc: "Consumes 2 documents, returns their overlap"

  # you write these 
  doc-1-lowercase = ???
  doc-2-lowercase = ???

  # .sort() is a method on any list, try it yourself enter [list: 2, 1, 3].sort()
  # as per documentation '+' appends two lists together
  distinct-sorted  = L.distinct(doc-1-lowercase + doc-2-lowercase).sort()

  # you write these
  vec-1 = create-vector(???)
  vec-2 = create-vector(???)
  
  dot-product(vec-1, vec-2) /
  num-max(num-sqr(num-sqrt(dot-product(vec-1, vec-1)), 
      num-sqr(num-sqrt(dot-product(vec-2, vec-2)))))
where:
... tests using an epsilon displacement 
end

Now you use the exact same method to write dot-product, and create-vector. You can test properties of create-vector(doc-1) for example the vector output, if you add up every element in the list it should equal the length of doc-1-lowercase. You could then bombard create-vec with random inputs instead of testing for specific edge cases/values.

#The folded sum of [list: 1, 1, 1, 0] is 3 and [list: "a", "b", "c"].length() is 3

create-vector([list: "a", "b", "c", "d"], [list: "a", "b", "c"])
   .foldl(lam(acc, x): x + acc end,0) is [list: "a", "b", "c"].length()

The output of create-vector is a list, so create-vector(params) becomes [list: ] after evaluation, you can then do all kinds of list operations on the results like [list-output].foldl() and I put .foldl() on a seperate line for readability. We learn what foldr and foldl are in the next chapter but you can rewrite .foldl in this test to a simple cases on (List) adding up each f in the vector link and returning the sum.

Let's do the lab on functions as data, and write our own map, filter and fold.

fun fun-plus-one(num :: Number, func :: (Number -> Number)) -> Number:
  func(num) + 1
end

>>fun-plus-one(16, num-sqrt)
>>5
>>fun-plus-one(3, num-sqr)
>>10

Try entering various built-ins, or one you wrote yourself, as the second parameter to fun-plus-one. In case you get hung up on syntax 'func' parameter can by anything, and try manipulating the (Number -> Number) annotation to ( -> Number) or remove the annotation completely to (num, f) and the function still works.

Map

We're given test cases and asked to implement f-to-c and goldilocks, and given the formula for f to c temperature unit conversion.

fun f-to-c(f-lst :: List<Number>) -> List<Number>:
  cases (List) f-lst:
    | empty => empty
    | link(f, r) => 
      link((f - 32) * (5/9), f-to-c(r))
  end
end

fun goldilocks(f-lst :: List<Number>) -> List<String>:
  cases (List) f-lst:
    | empty => empty
    | link(f, r) =>
      if f > 90:
        link("too hot", goldilocks(r))
      else if f < 70:
        link("too cold", goldilocks(r))
      else:
        link("just right", goldilocks(r))
      end
  end
end
check:
  f-to-c([list: 131, 77, 68]) is [list: 55, 25, 20]
  goldilocks([list: 131, 77, 68]) is [list: "too hot", "just right", "too cold"]
end

map(lam(x): x + 1 end, f-lst) the 'x' input is the element in each link in the list f-list, you are mapping over the whole list one element at a time, applying the lambda function to each element and returning a new list. We are asked to implement goldilocks using map:

# lambda notation
fun goldilocks(f-lst :: List< Number>) -> List<String>:
  f-lst.map(lam(x): if x > 90: "too hot" else if x < 70: "too cold" else: "just right" end end)
end
check:
  goldilocks([list: 131, 77, 68]) is [list: "too hot", "just right", "too cold"]
end

# shorthand syntax for lambdas from lab documentation 
fun goldilocks2(f-lst :: List< Number>) -> List<String>:
  f-lst.map({(x): if x > 90: "too hot" else if x < 70: "too cold" else: "just right" end})
end
check:
  goldilocks2([list: 131, 77, 68]) is [list: "too hot", "just right", "too cold"]
end

.map() is a built-in list method, where f-lst.map(…) means we are mapping over f-lst. We could have also rewritten it like the following example where we consume a function of type A (number) that produces a different type B (string, boolean):

fun goldilocks(x :: Number) -> String:
  if x > 90:
    "too hot"
  else if x < 70:
    "too cold"
  else:
    "just right"
  end
end

fun goldbool(x :: Number) -> Boolean:
  if (x > 90) or (x < 70):
    false
  else:
    true
  end
end


fun generic-map<A,B>(f :: (A -> B), f-lst :: List<A>) -> List<B>:
  map(f, f-lst)
end
check:
  generic-map(goldilocks, [list: 131, 77, 68]) is [list: "too hot", "just right", "too cold"]
  generic-map(goldbool, [list: 131, 77, 68]) is [list: false, true, false]
end

Write your own version of map. I used the documentation examples for map as check tests. Remember map consumes a function and a list, applies the function to each entry in the list returning a new list.

fun my-map<A,B>(func :: (A -> B), l :: List<A>) -> List<B>:
  cases (List) l:
  | empty => 
  | link(f, r) => 
  ... my-map(func, r)
check:
  my-map(num-to-string, [list: 1, 2]) is [list: "1", "2"]
  my-map(lam(x): x + 1 end, [list: 1, 2]) is [list: 2, 3]
  my-map(lam(x): true end, [list: "test", "test2"]) is [list: true, true]
end

Filter

First two assignments are straight forward to get you to used to using filter, except you have to use string-to-code-points() instead of any built-in string functions.

fun tl-dr(lol :: List<String>, length-thresh :: Number) -> List<String>:
  filter(lam(element): string-to-code-points(element).length() <= length-thresh end, lol)
end
check:
  tl-dr([list: "dkfjdkj", "hi", "dkfjk"], 2) is [list: "hi"]
  tl-dr([list: "corner", "case", ""], 2) is [list: ""]
  tl-dr([list: "a", "b", "c"], 0) is empty
end

fun eliminate-e(words :: List<String>) -> List<String>:
  doc: "I got 101 and 69 from string-to-code-points(e) and (E)"
  filter(lam(x): not((string-to-code-points(x).member(101)) or 
      (string-to-code-points(x).member(69))) end, words)
end
check:
  eliminate-e([list: "e"]) is empty
  eliminate-e([list: "there's", "no", "letter", "e", "here"]) is [list: "no"]
  eliminate-e([list: "hEy", "101e"]) is empty
end

Lambda parameters can be a single letter: filter(lam(x): x > 1 end) as it's immediately evident what that parameter is and it's scope is limited though you can add annotations like lam(x :: Number). You can also ignore the parameter if you don't plan on using it replacing x with underscore. Task: implement our own version of filter, which is similar to what we did for map:

fun my-filter<T>(func :: ( T -> Boolean), l :: List<T>)-> List<T>:
  cases (List) l:
    | empty => empty
    | link(f, r) =>
      ...   
  end
end
check:
  fun length-is-one(s :: String) -> Boolean:
    string-length(s) == 1
  end
  my-filter(length-is-one, [list: "ab", "a", "", "c"]) is [list: "a", "c"]
  my-filter(is-link, [list: empty, link(1, empty), empty]) is [list: link(1, empty)]
  my-filter(lam(x): x > 0 end, [list: 0, 1, -1]) is [list: 1]
end

Fold

Try the two tasks: list-product and list-max:

fun list-product(lon :: List<Number>) -> Number:
  fold(lam(acc, n): acc * n end, 1, lon)
end
check:
  list-product([list: 2, 2, 2]) is 8
  list-product([list: 0, 1, 2]) is 0
  list-product([list: -1, -1]) is 1
end

There's a bug in list-max to fix, try all negative examples Found by https://github.com/rand-anon-007

fun list-max(lon :: List<Number>) -> Number:
  fold(lam(acc, n): if n > acc: n else: acc end end, 0, lon)
end
check:
  list-max([list: -1, 1, 2]) is 2
  list-max([list: 0, -100, 1]) is 1
  list-max([list: 1/2, 3/4]) is 3/4
end

The problem is the accumulator needs to be initialized with the first value of the list not 0:

fun list-max(lon :: List<Number>) -> Number:
  fold(lam(acc, n): if n > acc: n else: acc end end, lon.get(0), lon)
where:
  list-max([list: -1, 1, 2]) is 2
  list-max([list: 0, -100, 1]) is 1
  list-max([list: 1/2, 3/4]) is 3/4
  list-max([list: -1, -2, -3]) is -1
  list-max([list: 0]) is 0
# list-max(empty) what about this case? what's the max of empty?
end

If the list is empty then long.get(0) raises an error:

fun list-max(lon :: List<Number>) -> Number:
  if lon == empty:
    0 # is this correct?
  else:
    fold(lam(acc, n): if n > acc: n else: acc end end, lon.get(0), lon)
  end
where:
  list-max([list: -1, 1, 2]) is 2
  list-max([list: 0, -100, 1]) is 1
  list-max([list: 1/2, 3/4]) is 3/4
  list-max([list: -1, -2, -3])  is -1
  list-max(empty) is 0
end

Now we have to make design decisions, should it eval to 0 for empty since the max of an empty list is nothing or should it raise an error that we can handle?

fun list-max(lon :: List<Number>) -> Number:
  if lon == empty:
    raise("List can't be empty")
  else:
    fold(lam(acc, n): if n > acc: n else: acc end end, lon.get(0), lon)
  end
where:
  list-max([list: -1, 1, 2]) is 2
  list-max([list: 0, -100, 1]) is 1
  list-max([list: 1/2, 3/4]) is 3/4
  list-max([list: -1, -2, -3])  is -1
  list-max(empty) raises "List can't be empty"
end

Write your own fold:

fun my-fold<A,B>(func :: (B, A -> B), acc :: B, l :: List<A>) -> B:
  cases (List) l:
    | empty => acc
    | link(f, r) =>
      my-fold(func, func(acc, f), r)
  end
end
check:
  my-fold((lam(acc, elt): acc + elt end), 0, [list: 3, 2, 1]) is 6
  # set accumulator to something not 0
  my-fold((lam(acc, elt): acc + elt end), 10, [list: 3, 2, 1]) is 16

  fun combine(acc, elt) -> String:
    tostring(elt) + " - " + acc
  end

  my-fold(combine, "END", [list: 3, 2, 1]) is "1 - 2 - 3 - END"
  my-fold(combine, "END", empty) is "END"
end

That type signature func :: (B, A -> B) means the function you are taking as input has 2 parameters, since fold has an accumulator.

Map2

Try the task for implementing who-passed, the second task we're asked to write map2 ourselves:

# link(ff, rr) and link(f, r) can be called anything:
# ie: link(head-first, tail-first) or link(head-second, tail-second)

fun my-map2<A,B>(func :: (A, A -> B), list1 :: List<A>, list2 :: List<A>) -> List<B>:
  cases (List) list1:
    | empty => empty
    | link(f, r) =>
      cases (List) list2:
        | empty => empty
        | link(ff, rr) =>
          ... what goes here?
      end
  end
end
check:
  my-map2(string-append, [list: "mis", "mal"], [list: "fortune", "practice"])
    is [list: "misfortune", "malpractice"]
  my-map2(_ + _, [list: "mis", "mal"], [list: "fortune", "practice"])
    is [list: "misfortune", "malpractice"]
  my-map2(string-append, [list: "mis", "mal"], [list: "fortune"])
    is [list: "misfortune"]
  my-map2(string-append, [list: "mis", "mal"], empty)
    is empty
  # test type signature
  my-map2(lam(x, y): if (x > 0) and (y > 0): true else: false end end, [list: 0, 1], [list: 2, 3]) 
    is [list: false, true] 
end

The last task, best-price, look on youtube what a basic demand function is. Here's an example:

fun demand(price-increase :: Number) -> Number:
 doc: "1000 is approx demand of product at a fixed price"
  1000 - (60 * price-increase)
end

This means as the price increases, the quantity demanded will decrease by 60 units times the price increase, so if the price increase is 1, the demand is 1000 - 60.

Map vs Filter vs Foldl vs Foldr

map and filter only consider one element in a list at a time whereas fold can consider the entire list. You can implement both map and filter with fold (try it). If you've noticed in the Pyret documentation there is foldl and foldr:

import lists as L

L.foldl(lam(acc, x): acc + x end, 0, [list: 1, 2, 3])
# (((0 + 1)+ 2)+ 3)
# eval nested brackets first, left to right

L.foldr(lam(acc, x): acc + x end, 0, [list: 1, 2, 3])
# (1 +(2 +(3 + 0)))
# eval nested brackets right to left

Here's an example of why you'd want to use foldr, making your own map function:

import lists as L

fun my-map<A,B>(func :: (A -> B), list1 :: List<A>) -> List<B>:
  L.foldr(lam(acc, x): link(func(x), acc) end, empty, list1)
where:
  my-map(num-to-string, [list: 1, 2]) is [list: "1", "2"]
  my-map(lam(x): x + 1 end, [list: 1, 2]) is [list: 2, 3]
  my-map(lam(x): true end, [list: "test", "test2"]) is [list: true, true]
end

After this assignment we are caught up to where students are currently at in the lectures. Here we are restricted from using list built-ins, so member, append, or distinct you'll have to write these yourself. The instructor considers rewriting library functions as drill exercises since programming is learn by doing. We need to fill in recommend and popular-pairs according to the spec we're given. Don't use their 2018 starter template, there's some kind of bug where accessing the content of a recommendation doesn't work. Write your own or use this:

provide *
provide-types *

data Recommendation<A>:
  | recommendation(count :: Number, content :: List<A>)
end

data File:
  | file(name :: String, content :: String)
end

fun recommend(title :: String, book-records :: List<File>) -> Recommendation:
  doc: ```Takes in the title of a book and a list of files,
       and returns a recommendation of book(s) to be paired with title
       based on the files in book-records.```
  recommendation(0, empty)
end

fun popular-pairs(records :: List<File>) -> Recommendation:
  doc: ```Takes in a list of files and returns a recommendation of
       the most popular pair(s) of books in records.```
  recommendation(0, empty)
end

Examples to help understand what the assignment is asking for, you can run this to see if the tests are at least well formed:

fun recommend(title :: String, book-records :: List<File>) -> Recommendation:
  doc: ```Takes in the title of a book and a list of files,
       and returns a recommendation of book(s) to be paired with title
      based on the files in book-records.```
  recommendation(0, empty)
where:
  r1 = file("a", "1984\nCrime and Punishment\nHeaps are Lame\nLord of the Flies")
  r2 = file("b", "1984\nHeaps are Lame\nLord of the Flies")
  r3 = file("c", "1984\nCrime and Punishment\nHeaps are Lame\nCalculus")
  r4 = file("d", "Crime and Punishment\n1984\nLord of the Flies")
  input = [list: r1, r2, r3, r4]

  recommend("1984", input) is recommendation(3, [list: "Heaps are Lame", "Crime and Punishment", "Lord of the Flies"])
  recommend("Heaps are Lame", input) is recommendation(3, [list: "Crime and Punishment", "1984", "Lord of the Flies"])
  recommend("War", [list: file("q", "War\nPeace")]) is recommendation(1, [list: "Peace"])
  recommend("PAPL", input) is  recommendation(0, empty)
 

  # These are their tests from 2016 Nile writeup:
  f1=file("alist.txt","1984\nAnimal Farm\nHigurashi\nLife of Pi")
  f2=file("blist.txt","Animal Farm\nHigurashi\nLife of Pi")
  f3=file("clist.txt","1984\nHeart of Darkness")
  input2 = [list: f1, f2, f3]

  recommend("1925", input2) is recommendation(0,[list: ])
  recommend("1984", input2) is recommendation(1,[list: "Animal Farm","Higurashi","Life of Pi","Heart of Darkness"])
end

One property to test would be to reverse the procedure. Given a list of titles, produce a file.content string and then compare it to your function that produces titles from a file. You solve this assignment the same way we did DocDiff going through the design recipe.

We caught up to the class, you can compare dates of lectures with dates of due assignments. Watching the Fri 9/14/18 lecture on performance. The setup in the beginning of the lecture is to distinguish the notation in O(n) as being a function that maps from n -> steps to complete computation. Another explanation is here in ambiguities in mathematics.

The constant mentioned at the end of the lecture in the formal notation is further exampled here. It's an estimation constant that bounds f, so no matter what input to f(k), a constant c times g(k) will be bigger or equal to it. What times g(k) is bigger or equal to f(k) -> 5k + 4:

• f(k) -> 5k + 4:
  • f(1) -> 5(1) + 4 = 9
  • f(2) -> 5(2) + 4 = 14
  • f(3) -> 5(3) + 4 = 19
  • f(10) -> 5(10) + 4 = 54
• g(k) -> k:
  • g(1) = 1
  • g(2) = 2
  • g(3) = 3

The constant c, try 10 as suggested in the lecture for f([k -> 5k + 4]) is \(\le\) (10 * g([k -> k])):

• f(1) is 9
• g(1) -> 10 * 1
  • f < g
• f(2) is 14
• g(2) -> 10 * 2
  • f < g
• f(10) is 54
• g(10) -> 10 * 10
  • f < g

Big O notation is here to act as a suppression of information, you don't care about the constants and almost never say exactly what they are, or even the value of f(n) or g(n) they both stand for a quantity that isn't explicity known so just placeholders where you imagine inputs to the maximum of the computational model's resources so very large but usually not infinitely large. Big-O can also be thought of a set of functions of order n, for example O(n) is the set of functions who's growth rate is linear, hence why a specific function like f(n) is said to be 'in O(n)', the set of linear functions. You can also think of it as a type, the type of function(s) who's growth rate is O(n).

To recap this lecture: we need a model of computation in order to begin to do analysis of algorithms, a simple one that hands out +1 cost for every operation in the syntax (not the real underlying operations happening in the interpreter/compiler) is crude but since we can ignore constant factors it's fine for worst case estimation, we use Big-O because it abstracts across multiple machines with different hardware, it has familiar and convenient arithmetic like O(n) + O(m) is O(n + m) but still O(n) or O(n) * O(n) is O(n * n) or O(n²).

We're watching the Mon9/17/18 lecture. The first 30mins or so of the recording doesn't have video, but you can pause the video around 30:14 in, open the video again to hear the audio, and see everything on the board they are working on (sort and insert). He starts out talking about the invariant of insert, that it's length should always be k+1 because it is inserting a new value. The second topic is about how the size argument of a list doesn't help you with incorrect types, if you have [list: [list: empty]], that's still size = 1 even though it's empty.

The if-statement you take the worst complexity branch, assuming worse-case analysis. The actual cost analysis of insert() starts around 20mins in because you want to resolve the dependencies of sort() by figuring out the complexity class of insert() first. A link operation link(f, r) takes a constant amount of time regardless of the size of the input list, because it doesn't make a copy of the list. The if statement is 1 + (worst case branch).

On the right hand of the board:

• Tinsert(0) = \(c_0\) (constant steps for empty, or base case)
• Tinsert(k) = c + Tinsert(k - 1)
• = c + c + c + … \(c_0\)
• = T(k) = kc + \(c_0\).

Remember we're calling insert(f, sort(r)) on the rest of the list, so it's k - 1.

• Tsort(0) = \(c_0\) or a constant amount of steps
• Tsort(k) = Tsort(k - 1) + Tinsert(k - 1)c + \(c_0\)
• = Tsort(k - 1) + kc
• We've seen this already, T(k - 1) + k is the series 1 + 2 + 3 + 4+…+(k - 1) + k or n(n + 1)/2 or \(O(n^2)\)
• Insertion Sort is \(O(n^2)\) worst case, and O(n) + O(1) in the best case because you still have to call sort(r) and do linear work exploding that n sized list out before you can do the O(1) operation by insert that appends to the beginning of the list and returns.

We're watching the lecture titled Wed9/19/18. Reminder these lectures can be viewed or downloaded in 1920x1080 size so you can zoom with whatever video player if needed but seeing the fine details isn't important he is showcasing the structure of linear [k -> k] vs quadratic [k -> \(k^2\)].

He remarks that their quicksort implementation is really a filter, and we should try quicksort using a filter:

fun combine(lt, p, gt):
  lt.append([list: p]).append(gt)
end

fun qsort(l):
  cases (List) l:
    | empty => empty
    | link(pivot, r) =>
      combine(
        qsort(r.filter(lam(n): n < pivot end)),
        pivot,
        qsort(r.filter(lam(n): n >= pivot end)))
  end
end
check:
  qsort([list: 2, 1, 3, 4, 5]) is [list: 1, 2, 3, 4, 5]
  qsort([list: 100, 0, 1, 343]) is [list: 0, 1, 100, 343]
  qsort([list: 0, -1, 100]) is [list: -1, 0, 100]
  qsort([list: ]) is ([list: ])
  qsort([list: 8, 1, 1, 9, -1]) is [list: -1, 1, 1, 8, 9]
end

He ends the lecture trying to convey a bigger idea: use the structure of the data to come up with a simple solution, confirm the inefficient solution is correct, optimize it according to the bound you want.

This assignment we're building a testing oracle.

First function is generate-input(n :: Number) -> List<Person>, it consumes a number, and produces a list of length n of type Person. Since this function is going to generate random person.name strings we can't directly match the output in a test case, but we can still confirm it has the correct properties of [list: person(name, number)]:

data Person:
  | person(name :: String, age :: Number)
end

fun generate-input(n :: Number) -> List<Person>:
  doc:"Generate random n size list of person(name, age), name is length 4, age is 1 - 100"
  ...
where:
  # confirm size
  L.length(generate-input(5)) is L.length([list: 1, 2, 3, 4, 5])
  map(lam(x): (string-length(x.name) > 0) is true end, generate-input(5))  

  # make sure the age > 0
  map(lam(x): x.age > 0 is true end, generate-input(5))
 
 # confirm name is ASCII code points from 97 - 122 
 # string-to-code-points() returns a list, so nested map
  map(lam(x): map(lam(y): ((y >= 97) and (y <= 122)) is true end, string-to-code-points(x.name)) end, generate-input(3)) 
end

Pyret has a built-in function for generating a list repeat() which we will need to write ourselves since this assignment doesn't allow using built-ins outside of the higher order functions and sort() or sort-by() though I used some other list built-ins here and in the test cases since we already rewrote them in the Nile assignment. One way we could architect this is recursing on n, linking a list together. So num-random() gives us something resembling a random name, see this article, code points I guess could be between 97 and 122 or 'a' and 'z' though you could just leave this random and fuzzy test with all unicode code points since our sorters could hold foreign unicode names or symbols or anything:

import lists as L

data Person:
  | person(name :: String, age :: Number)
end

fun generate-input(n :: Number) -> List<Person>:
  doc:"Generate random n size list of person(name, age)"

  fun random-name(s :: Number, name-string :: String) -> String:
    doc: "Generate a random string between ASCII 97 - 122 of length s"
    if s < 1:
      name-string
    else:
      single = num-random(33) + 90
      if (single >= 97) and (single <= 122):
        random-name(s - 1, string-from-code-point(single) + name-string)
      else:
        random-name(s, name-string)
      end
    end
  where:
    string-length(random-name(5, "")) is 5
    string-length(random-name(1, "")) is 1
  end

  fun helper<T>(num :: Number, acc :: List<Person>) -> List<Person>:
    doc: "Consumes n, init acc and returns [list: person(name, age)] n times"    
    if num < 1:
      acc
    else: 
      name-length = num-random(25) + 1
      helper(num - 1, link(person(random-name(name-length, ""), num-random(100) + 1), acc))
      # acc on first call is a placeholder here for empty
      # this will return ...link(item, link(item, orig-acc)) 
    end
  end

  # preconditions
  if n < 1:
    raise("Input must be greater than 0")
  else:
    helper(n, empty)
  end
where:
  # confirm size
  L.length(generate-input(5)) is L.length([list: 1, 2, 3, 4, 5])
  map(lam(x :: Person): (string-length(x.name) > 0) is true end, generate-input(2))  

  # make sure the age is within 1 - 100
  map(lam(x :: Person): x.age > 0 is true end, generate-input(2))
  # confirm name is ASCII code points from 97 - 122 
  map(lam(x :: Person): map(lam(y): ((y >= 97) and (y <= 122)) is true end, string-to-code-points(x.name)) end, generate-input(2)) 

  # confirm input is > 0
  generate-input(0) raises "Input must be greater than 0"
end

>>> generate-input(2)
[list: person("vwqukq", 3), person("rljhrsijqcwyuglwjtnhc", 48)]

Next is a sort validation function that consumes two sorted lists of type Person, and compares if they are both the same returning a boolean true or false. To compare if the first sorted input list is equal to the correct sorted list, we could map2 over both lists to do equality tests, then fold over the list map2 returns comparing each entry with 'true'.

Note this is inefficient as a cases on List can break on the first instance of false instead of continuing through the entire linear list:

fun is-valid(test-input :: List<Person>, correct-input :: List<Person>) -> Boolean:
  doc: "Consumes test-input and compares to correct-input a correct-sorter() list"

  fun length-test(test-input-a :: List<Person>, correct-input-a :: List<Person>) -> Boolean:
    doc: "Test if both lists are the same length"
    (L.length(test-input-a)) == (L.length(correct-input-a))
  end

  fun name-test(test-input-b :: List<Person>, correct-input-b :: List<Person>) -> Boolean:
    doc: "Test if any names have been altered"
    correct-sorted-names = correct-sorter(test-input-b)
    names = map2(lam(n1 :: Person, n2 :: Person): (n1.name == n2.name) end, correct-sorted-names, correct-input-b)
    L.foldl(lam(a :: Boolean, b :: Boolean): a and b end, true, names)
  end

  fun age-sort-test(test-input-c :: List<Person>, correct-input-c :: List<Person>) -> Boolean:
    doc: "Test if sorted by age correctly"
    age-test = map2(lam(n3 :: Person, n4 :: Person): (n3.age == n4.age) end, test-input-c, correct-input-c)
    L.foldl(lam(c :: Boolean, d :: Boolean): c and d end, true, age-test)
  end

  fun age-and-name-sort-test(test-input-d :: List<Person>, correct-input-d :: List<Person>) -> Boolean:
    doc: "See if the names and ages match, this will fail occasionally for qsort on duplicate ages"
    both-test = map2(lam(n5 :: Person, n6 :: Person): (n5.name == n6.name) and (n5.age == n6.age) end, test-input-d, correct-input-d)
    L.foldl(lam(e :: Boolean, f :: Boolean): e and f end, true, both-test)
  end

  # return the results
  if length-test(test-input, correct-input)
    and
    name-test(test-input, correct-input)
    and
    age-sort-test(test-input, correct-input)
    and
    age-and-name-sort-test(test-input, correct-input):
    true
  else:
    false  
  end
where:
  # some corner cases, omitted many tests
  is-valid(empty, empty) is true
  is-valid([list: person("a", 31)], empty) is false
  is-valid([list: person("", 31)], [list: person("a", 31)]) is false 
end

Now we go about writing multiple buggy implementations of sorting algorithms and test these functions with oracle :: (List<Person> -> List<Person>) -> Boolean ie: oracle(insertion-sort)) or oracle(quick-sort):

fun combine(lt, p, gt):
  doc: "Used by incorrect-quicksort"
  lt.append([list: p]).append(gt)
end

fun qsort(l :: List<Person>) -> List<Person>:
  doc: "Quicksort from lectures"
  cases (List) l:
    | empty => empty
    | link(pivot, r) =>
      combine(
        qsort(r.filter(lam(n): n.age < pivot.age end)),
        pivot,
        qsort(r.filter(lam(n): n.age >= pivot.age end)))
  end
end

fun incorrect-qsort(l :: List<Person>) -> List<Person>:
  doc: "Sabotaged quicksort"
  cases (List) l:
    | empty => empty
    | link(pivot, r) =>
      combine(
        incorrect-qsort(r.filter(lam(n): n.age < pivot.age end)),
        pivot,
        incorrect-qsort(r.filter(lam(n): n.age > pivot.age end)))
  end
end

# empty case test
fun empty-sort(p :: List<Person>) -> List<Person>: 
  empty 
end

# deletes the names
fun name-screwed(w :: List<Person>) -> List<Person>:
  correct = L.sort-by(w,
    lam(p1, p2): p1.age < p2.age end,
    lam(p1, p2): p1.age == p2.age end)
  (map(lam(x): person("", x.age) end, correct))
end

fun oracle(f :: (List<Person> -> List<Person>))-> Boolean:
  doc: "Testing oracle for sorting lists of type Person"

  random-input = generate-input(num-random(30) + 5)
  is-valid(f(random-input), correct-sorter(random-input))
where:
  oracle(qsort) is true
  oracle(incorrect-qsort) is false
  oracle(name-screwed) is false
  oracle(empty-sort) is false
end

These tests won't always pass, because sometimes incorrect-qsort() will produce the correct output, it's only on edge cases with duplicate ages that it won't pass our oracle test case. Quicksort will also sometimes produce a different sort sequence for multiple same ages or similar names with different ages that were correctly but differently sorted than the sequence correct-sorter() uses. This is a poor solution where our oracle just fails without any information, but I considered it good enough for the purposes of this assignment since we aren't being graded.

This assignment is yet more practice that mirrors what a typical developer would have to do unravelling data out of nested structures and writing quick basic tasks.

We're watchin Fri9/21/18 lecture on 2D tree shaped data w/guest lecturer Tim Nelson who is an expert in software verification. An interesting paper from his page authored with Prof K you should read is The Human in Formal Methods. In it they write about porting the method of example writing we've been doing to this domain. A common learning mistake that students make is talked about, in that they write programs before they have understood the problem, as a result they 'solve' the wrong problem, which misdirected from the learning goals. If you read the paper linked in the first DocDiff assignment you already know this, that you should never jump into writing the solution first or else you are wasting your time.

The mutual recursive datatypes, to understand them write out your own tree:

       a 
      /  \   
    b    none     
   /  \
  c    none
   \ 
    none

a has child b and none
b has child c and none
c has none

• start with a:
• person("a", No-children)
• add in b:
• person("a", child(person("b", No-children), No-children))
• add in c:
• person("a", child(person("b", child(person("c", No-children), No-children)), No-children))

We're watching Mon9/24/18 lecture on sets. This is a design lecture, given something that has no notion of order, how do you design it's data structure representation.

When he shortens insert() to equal link, try it in the pyret repl. The end of this lecture discussing the big-O complexity of both representations he points out the inefficient representation is better depending on what you care about, like appending a log you often don't look at.

Let's build a testing oracle. There's a starter template we need to access the function they give us matchmaker() and is-hire()

# CSCI0190 (Fall 2018)
provide *
provide-types *

import shared-gdrive("oracle-support.arr",
  "11JjbUnU58ZJCXSphUEyIODD1YaDLAPLm") as O

##### PUT IMPORTS BELOW HERE ############


##### PUT IMPORTS ABOVE HERE ############

type Hire = O.Hire
hire = O.hire
is-hire = O.is-hire
matchmaker = O.matchmaker

# DO NOT CHANGE ANYTHING ABOVE THIS LINE

fun generate-input(num :: Number) -> List<List<Number>>:
  doc: 
  ```
  generates a list of candidates or companies for a group of size num
  ```
  empty
where:
  generate-input(0) is empty
end

fun is-valid(
    companies :: List<List<Number>>,
    candidates :: List<List<Number>>,
    hires :: Set<Hire>)
  -> Boolean:
  doc: 
  ```
  Tells if the set of hires is a good match for the given
  company and candidate preferences.
  ```
  true
where:
  is-valid(empty, empty, empty-set) is true
end

fun oracle(a-matchmaker :: (List<List<Number>>, List<List<Number>> 
      -> Set<Hire>))
  -> Boolean:
  doc: 
  ```
  Takes a purported matchmaking algorithm as input and outputs whether or
  not it always returns the correct response
  ```
  true
where:
  oracle(matchmaker) is true
end

Run the template then try to give matchmaker some inputs to see what it does:

companies =  [list: [list: 1, 0, 2], [list: 0, 2, 1], [list: 0, 2, 1]]
candidates = [list: [list: 1, 0, 2], [list: 1, 2, 0], [list: 0, 1, 2]]
# Note matchmaker writeup: it is 0 to n-1 indexed, so 3 lists means 0 - 2 

matchmaker(companies, candidates)
>>[list-set: hire(2, 1), hire(1, 0), hire(0, 2)]

First Let's understand the matching algorithm, we don't have to write one ourselves. Let's look at the actual paper. Scroll down to Theorem 1: There always exists a stable set of marriages and look at the proof for the algorithm:

• First round:
• Companies all select their first preferred candidate
• Candidates accept provisionally, if a more preferred offer is presented in next rounds they will reject this one
  • Rejected companies are put into a pool
• Second round:
• Companies in the pool with no matching then all select their second preferred candidate
• Candidates accept or reject upon preferences
• X rounds:
• Repeat, noting that no company can offer more than once to a candidate

The 2019 assignment writeup contains a few hints, such as 'be cautious about using the provided matchmaker function in your oracle as this assumes that there is only one right answer to a given instance of the stable hiring problem'. I translate this to mean there could be many permutations of the stable-hiring problem which are still correct, however the Gale-Shipley algorithm produces the exact same matching everytime if the company is making offers, and candidates rejecting. What if the roles are reversed, if it is candidate making offers and company rejecting? We have 2 inputs into matchmaker but it doesn't say which one is actually making the offers and which input is rejecting. We should try altering the inputs and see what happens:

companies =  [list: [list: 1, 0, 2], [list: 0, 2, 1], [list: 0, 2, 1]]
candidates = [list: [list: 1, 0, 2], [list: 1, 2, 0], [list: 0, 1, 2]]

>>matchmaker(candidates, companies)
[list-set: hire(2,2), hire(1,0), hire(0,1)]

>>matchmaker(companies, candidates)
[list-set: hire(2,1), hire(1,0), hire(0,2)]

They're different, so there is indeed more than one solution to the problem depending on if the bias is towards candidates or companies. So how are we going to test the property for any stable matching. I find an old book, entirely on the Stable Marriage problem here and on page 8 Stability Checking we are given a stability checking algorithm and on page 7 this is more clearly defined: For each company C, look at their preferences and check that each candidate they prefer is not matched to somebody else if candidate also prefers company C.

• Some tests to implement:
  • check the hire pairs are bounded with the input
    • no hire(7,1) if input is only 3 companies
  • check n companies and n candidates are in n pairs
  • check for duplicate matchings
  • check they are stable as per the algorithm in that book

This was my good enough generate-input function for test inputs < num = 25, more than that and needs optimization, like using a dictionary datastructure or keep a sorted accumulator to check for dupes, or using filter:

fun generate-input(num :: Number) -> List<List<Number>>:
  doc: 'generates a list of candidates or companies for a group of size num'
  fun test-for-dupes(input :: List<Number>) -> List<Number>:
    doc: 'Checks for duplicate prefs in the list'
    distinct-input = L.distinct(input)
    if (L.length(distinct-input) < num):
      test-for-dupes(distinct-input
          + map(lam(x): num-random(num) end, repeat(num - distinct-input.length(), 0)))
    else:
      input
    end
  end

  fun create-list(n :: Number) -> List<Number>:
    doc: 'Assembles list of distinct prefs'
    randomized = map(lam(x): num-random(n) end, repeat(n, 1))
    test-for-dupes(randomized)
  end

  if (num <= 0):
    # If empty, return empty
    empty
  else if num == 1: 
    # If n, return n - 1 
    [list: [list: 0]]
  else:
    # repeat gives a skeleton list to map over of size num
    map(lam(x): create-list(num) end, repeat(num, 1)) 
  end
where:
  generate-input(0) is empty
  generate-input(-1) is empty
  generate-input(1) is [list: [list: 0]]
  L.length(generate-input(3)) is 3
  # omitted a bunch of tests here
end

We're watching lecture Wed/9/26/18. This is a light lecture just explaining the intuition behind logarithmic complexity to set up balanced binary search trees. At 7:10 he explains logarithms: "A (base-10) logarithm of a number is essentially how many digits a number has. That's it". He then explains in terms of virtual machine costs, if you have a logarithmic algorithm and there is a million new runs of that algorithm you are only paying 6x the cost.

This is lecture Fri/9/28/18. We discover the entire last lecture was just trolling and would not give us logarithmic time in terms of successfully being able to throw away half the data because the tree isn't balanced. This whole lecture is understanding how you can balance a tree.

I interpret the assignment to mean this directory tree/model:

# this is missing from my template:
type Path = List<String>

# you can omit size field, so c = file("name", "content") and c.size will return size of the content field text.  
filesystem = (dir("TS", [list:
        dir("Text", empty, [list: file("part1", 99, "content"), file("part2", 52, "content"), file("part3", 17, "content")]),   
        dir("Libs", [list: 
            dir("Code", empty, [list: file("hang", 8, "content"), file("draw", 2, "content")]), 
            dir("Docs", empty, [list: file("read!", 19, "content")])], empty)],
      [list: file("read!", 10, "content")]))

Pyret allows you to write methods for datatype, here's an example for du-dir() where I wrote a .size() method:

provide *
provide-types *

data File:
  | file(name :: String, size :: Number, content :: String)
end

data Dir:
  | dir(name :: String, ds :: List<Dir>, fs :: List<File>) with:
    method size(self :: Dir) -> Number:
      doc: "Returns combined file size, file count, and sub directory count of a Dir"
      size(self)
    end
end

fun size(d :: Dir) -> Number:
  doc: "Method .size()"

  fun fsize(fd :: Dir) -> Number:
    doc: "Returns file size, and number of files in a Dir"
    fd.fs.foldl(lam(f :: File, acc :: Number): 1 + f.size + acc end, 0)
  end

  fsize(d)
    + map(lam(x :: Dir): 1 + size(x) end, d.ds).foldl(lam(elt, acc): elt + acc end, 0)
end
check:
  a = dir("TS", [list:
      dir("Text", empty, [list: file("part1", 1, "content")])], empty)

  b = dir("Libs", [list: 
      dir("Code", empty, [list: file("hang", 1, "content"), file("draw", 1, "content")]), 
      dir("Docs", empty, [list: file("read!", 1, "content")])], empty)

  c = dir("TS", [list:
      dir("Text", empty, [list: file("part1", 1, "content"), file("part2", 1, "content"), file("part3", 1, "content")]),   
      dir("Libs", [list: 
          dir("Code", empty, [list: file("hang", 1, "content"), file("draw", 2, "content")]), 
          dir("Docs", empty, [list: file("read!", 1, "content")])], empty)],
    [list: file("read!", 1, "content")])

  d = dir("TS", [list:
      dir("Text", empty, [list: file("part1", 99, "content"), file("part2", 52, "content"), file("part3", 17, "content")]),   
      dir("Libs", [list: 
          dir("Code", empty, [list: file("hang", 8, "content"), file("draw", 2, "content")]), 
          dir("Docs", empty, [list: file("read!", 19, "content")])], empty)],
    [list: file("read!", 10, "content")])

  e = dir("TS", empty, [list: file("", 1, "")])

  a.size() is 3
  b.size() is 8
  c.size() is 19
  d.size() is 218
  e.size() is 2
end

This is all in the Pyret documentation, and I looked at the Pyret source on github to see how to chain multiple methods:

data Dir:
  | dir(name :: String, ds :: List<Dir>, fs :: List<File>) with:
    method size(self :: Dir) -> Number:
      doc: "Returns the size of all sub directories"
      size(self)
    end,
    method path(self :: Dir, s :: String) -> List<Path>:
      doc: "Takes a Dir, and a search string, returns the path"
      path(self, s)
    end
end

The path method there's numerous ways you could architect this to be better. Advice: I do these exercises on a phone whenever I have spare time (commuting, lunch break, randomly get an idea somewhere) and often repeated the same annoying mistake using [list: ] instead of 'empty' which seems to break everything in Pyret test cases.

Reading the assignment for updater, the Cursor datatype can also contain another cursor which points to the node above:

data Cursor<A>:
  | mt-cursor
  | cursor(above :: Cursor<A>, index :: List<Number>, point :: Tree<A>)
end

The index represents the pointed to cursor's position in the child list, ie: [list: 0]. This means you can fold through all the cursor.above indexes to make a string of .get() or .set()::

import lists as L

data Tree<A>:
  | mt
  | node(value :: A, children :: List<Tree>)
end

data Cursor<A>:
  | mt-cursor
  | cursor(above :: Cursor<A>, index :: List<Number>, point :: Tree<A>)
end

# test tree:
#        1
#       / \
#      2   5
#     / \   \
#    4   3   6 
#         \   \
#         3.5  7

test-tree = 
  node(1, [list:
      node(2, 
        [list: node(4, empty), node(3, [list: node(3.5, empty)])]),
      node(5, 
        [list: node(6, [list: node(7, empty)])])])

# left side
test-tree.children.get(0)

# right side
test-tree.children.get(1)

# get node 3.5
test-tree.children.get(0).children.get(1).children.get(0)

# produces a list of indices from root to cur.point ex: [list: 0,1,0] 
fun get-index(cur :: Cursor):
  L.foldl(lam(_, x): get-index(cur.above) + [list: x] end, empty, cur.index)
end

# produces tree.children.get(n).tree.children.get(n)..
fun get-nodes(tree, l):
  L.fold(lam(t, x): t.children.get(x) end, tree, l)
end

check "map n produces [list: 0, 1]":
  get-nodes(test-tree, map_n(lam(n, _): n end, 0, test-tree.children)) 
    is node(3, [list: node(3.5, empty)])
end

Check the top node, if a match then cursor(mt, empty, entire-tree) otherwise send the children list of the root node into a helper function that keeps track of the parent node. When pred(f.value) is true, find the position in the parent list of your cursor point, extract this number as an index, build the cursor with:

cursor(find-cursor(entire-tree, lam(x): x == parent-node.value end)),
  index-of-point-node, point-node)

The index can also just be a number you test to see if it's 0, meaning trying to move left should raise an error as per assignment. The depth-first search requirements you'll have to figure out a scheme to return the leftmost or topmost node for multiple matches you can get-index all the matching cursors if you want or design find-cursor to only search as per requirements. This program has multiple different ways you can implement I came up with a few before trying to figure out the most efficient way.

get-node-val returns type option (this is also in PAPL under Chapter 12/Sets) an option will wrap the response in some(v) or read the documentation for cases on (Option) with some(a) => syntax. Including an underscore in cases means you don't plan on using that field

# this returns some(v) which you extract with some.value
fun get-node-val<A>(cur :: Cursor<A>) -> Option<A>: 
  cases(Cursor) cur:
    | cursor(_,_, point) => some(point.value) 
    | mt-cursor => none
  end
end

Watching lecture titled Mon/10/01/18. In the examples of ones, everytime you invoke 'ones' you get lzlink(1, <thunk>) which is one, plus a way to get more ones if called again. We're asked to write our own map, you could also try it with cases:

fun maps<A, B>(f :: (A -> B), s :: Lz<A>) -> Lz<B>:
  cases (Lz<A>) s:
    | lzlink(e, r) => lzlink(f(e), {(): maps(f, rst(s))}) 
  end
end

fun maps2<A, B, C>(f :: (A, B -> C), s1 :: Lz<A>, s2 :: Lz<B>) -> Lz<C>:
  cases (Lz<A>) s1:
    | lzlink(e, r) => 
      cases (Lz<B>) s2:
        | lzlink(ee, rr) => lzlink(f(e, ee), {(): maps2(f, rst(s1), rst(s2))})
      end
  end
end

>>s2 = maps(lam(x): x - 1 end, nats)
>>take(s2, 5)
[list: -1, 0, 1, 2, 3]

>>s3 = maps2(lam(x, y): x + y end, nats, nats)
>>take(s3, 5)
[list: 0, 2, 4, 6, 8]

The type variables annotation he used maps<A,B,C>(f :: (A -> B),..)-> Stream<C>: is in the streams chapter of the text and in Chapter 27.

You don't need the template for the assignment only the following:

# CSCI0190 (Fall 2018)
provide *
provide-types *

data Stream<T>:
  | lz-link(first :: T, rest :: (-> Stream<T>))
end

# These are in PAPL chapter on streams:
fun lz-first<T>(s :: Stream<T>) -> T: s.first end
fun lz-rest<T>(s :: Stream<T>) -> T: s.rest() end

# Something for an mt-stream
rec mt-stream = lz-link(none, {(): mt-stream}) 

## Part 1: Streams

# cf-phi :: Stream<Number> = 
# cf-e :: Stream<Number> = 

fun take<A>(s :: Stream<A>, n :: Number) -> List<A>:
  ...
end

fun repeating-stream(numbers :: List<Number>) -> Stream<Number>:
  doc: ""
  ...
end

fun threshold(approximations :: Stream<Number>, thresh :: Number)-> Number:
  doc: ""
  ...
end

fun fraction-stream(coefficients :: Stream<Number>) -> Stream<Number>:
  doc: ""
  ...
end


## Part 2: Options and Terminating Streams

# cf-phi-opt :: Stream<Option<Number>> = 
# cf-e-opt :: Stream<Option<Number>> = 
# cf-pi-opt :: Stream<Option<Number>> = 

fun terminating-stream(numbers :: List<Number>) -> Stream<Option<Number>>:
  doc: ""
  ...
end

fun repeating-stream-opt(numbers :: List<Number>) -> Stream<Option<Number>>:
  doc: ""
  ...
end

fun threshold-opt(approximations :: Stream<Option<Number>>,
    thresh :: Number) -> Number:
  doc: ""
  ...
end

fun fraction-stream-opt(coefficients :: Stream<Option<Number>>)
  -> Stream<Option<Number>>:
  doc: ""
  ...
end

You only have to use repeating-stream for phi and e, though I wrote a decimal to continued fraction algorithm I got from from here on page 13 and my own inefficient e generator anyway. When you write your repeating-stream function for e it has to be property-based tested since it's a stream you can only take x amount of values at a time.

fun c-frac(n :: Number) -> Stream<Option<Number>>:
  doc: "Consumes decimal, returns some(fraction integral) stream"
  integral = num-truncate(n)
  decimal = n - integral
  ask:
    | decimal > 0 then:
      new-decimal = 1 / decimal
      lz-link(some(integral), {(): c-frac(new-decimal)})
    | otherwise:
      lz-link(some(integral), {(): mt-stream})
  end
where:
  cf-e :: Stream<Number> = c-frac(generate-e(30))
  cf-phi :: Stream<Number> = c-frac((1 + num-sqrt(5)) / 2)

  take(cf-e, 6) is [list: some(2), some(1), some(2), some(1), some(1), some(4)]
  take(cf-phi, 3) is take(repeating-stream([list: some(1)]), 3)
  take(c-frac(2.875), 4) is [list: some(2), some(1), some(7), none]
  take(c-frac(PI), 5) is [list: some(3), some(7), some(15), some(1), some(292)]
end

# see wikipedia it is the sum of 1/k! where k starts at 0 and keeps going
# 1/0! + 1/1 + 1/(1*2) + 1/(1*2*3) ... where 1/0! is 1.
fun generate-e(n :: Number) -> Number:
  doc:"Generates e (inefficiently) to n decimal places"

  fun e-helper(current-count):
    factorial = take(nats-from(1), current-count)
      .foldr(lam(acc, x): x * acc end, 1)
    lz-link(1 / factorial, {(): e-helper(current-count + 1)})
  end

  take(e-helper(1), n).foldl(lam(acc,x): acc + x end, 1)
where:
  epsilon = 0.0000001
  num-abs((generate-e(10) - 2.7182818)) < epsilon is true

  wikipedia-value = 2.71828182845904523536028747135266249775724709369995
  silly-epsilon = 0.00000000000000000000000000000000000000001
  num-abs(generate-e(60) - wikipedia-value) < silly-epsilon is true
end

check "property-based-test-e":  
  # Property-based testing
  # Any frac stream of e, if integral > 1 it should be even:
  # ie [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1...]

  fun e-test(e-value, size-of-approx):
    take(c-frac(e-value), size-of-approx)
      .map(lam(x): if x.value > 1: num-modulo(x.value, 2) == 0 else: 0 end end)
      .filter(lam(y): not(y == 0) end)
      .foldl(lam(z, acc): z and acc end, true)
  end

  e-test(generate-e(10), 10) is true
  e-test(generate-e(20), 20) is true
  e-test(generate-e(30), 30) is true
  # This is false because we need a bigger e generated
  e-test(generate-e(20), 30) is false
end

The ask check decimal > 0 was to avoid division by zero, and to terminate finite rational streams with none. PI is a Pyret built-in constant. Everything you need for this assignment is in the book like the nats-from() function I used.

The goal of this assignment is to produce a program that can make refined approximations:

# First attempt without Options

fun c-approx(c-list :: List<Number>) -> Number:
  doc: "Consumes list of continued fractions, returns rational approximation"

  cases (List) c-list.rest
      | empty => c-list.first
      | link(f, r) => (1 / c-approx(c-list.rest)) + c-list.first
    end
where: 
  # phi test of approximations
  cf-phi :: Stream<Number> = c-frac((1 + num-sqrt(5)) / 2)

  c-approx(take(cf-phi, 3)) is 3/2
  c-approx(take(cf-phi, 4)) is 5/3
  c-approx(take(cf-phi, 5)) is 8/5
  c-approx(take(cf-phi, 6)) is 13/8

  # PI test of approximations
  c-approx(take(c-frac(PI), 1)) is 3
  c-approx(take(c-frac(PI), 2)) is 22/7
  c-approx(take(c-frac(PI), 3)) is 333/106
  c-approx(take(c-frac(PI), 4)) is 355/113 
end

The algorithm for this is just hand stepping the examples in the assignment writeup:

• c-approx([list: 3, 7, 15])
  • (1 / c-approx([list: 7, 15]) + 3
  • (1 / (1 / c-approx([list: 15]) + 7) + 3
  • (1 / ((1 / 15) + 7)) + 3
  • (1 / (106/15)) + 3
  • (15/106) + 3
  • 333/106

There is many other stream functions left for you to write like fraction-stream which takes a stream as a parameter, so you can use take() inside the body of fraction-stream to keep grabbing more input:

# you can use a map over a stream here too

fun fraction-stream(n :: Stream<Number>) -> Stream<Number>:
  doc: "Consumes stream of continued fraction integrals, returns stream of rationals"

  fun helper(integrals, take-ctr):
    next-approx = take(integrals, take-ctr)
    lz-link(c-approx(next-approx), {(): helper(n, take-ctr + 1)})
  end
  helper(n, 1)
where:
  take(fraction-stream(repeating-stream([list: 1])), 3) is [list: 1, 2, 3/2]
end

The assignment has you redoing everything for option types, meaning doing cases on Options to safeguard against division by zero and many other problems the writeup notes. The big-O complexity assignment asks what are the meaningful parameters for the analysis, this doesn't mean the parameters of the functions but the statistics definition of parameters like what is the worst case, ie: no threshold is found for your approximations since we are dealing with streams and not n-sized lists anymore.

This is lecture Wed10/3/18. You can't see the entire whiteboard in the beginning but it doesn't matter, this is a lecture about seperation of concerns when building large systems, how to embody the essence of a system into a model that is common to all parts of the system.

Lecture Fri10/05/18. Using same reactor model to make a point about differential systems. Interesting examples about PID controllers/reactive systems, event loops, checkpoints of the state of the system.

Lecture Wed10/10/18. A great lecture about memory aliasing, introduces directed acyclic graphs, acyclic meaning it doesn't cycle and has one direction. The reading uses memory location examples to make this concept of more clear

TODO

Lecture Fri10/12/18. They had some homework/quiz to write examples to check the size of a DAG that we don't have access to, however you can read chapter 20 Sharing and Equality from PAPL and follow along with the examples. If a branch is the same construction (recall identical from previous lectures/the book) then you don't count it's size twice.

check "size of A node":
 A = node(1, leaf, leaf)
 size(node(2, A, A)) is 2
 size(node(1, A, A)) is 2

There's only 2 distinct nodes in each, node A and another wrapped around it. Check blocks can have strings, so when you run a test you know which one failed. The rest of this lecture is writing the DAG size function with the class because you have to carry information on which nodes you've already seen. We discover this design pattern of carrying information is called monadic programming.

The end of the lecture he walks through the code of a pyret library he wrote explaining the types and syntax, you can use this to look up the source yourself when doing assignments and read the code.

Lecture Mon10/15/18 a casual lecture introducing graphs and describing their properties. Our assignment is to read the chapter on graphs up to measuring complexity.

Lecture Wed10/17/18

Home