---
# System prepended metadata

title: CS1101S Studio 4

---

# CS1101S Studio 4
@jiachen247 2<sub>nd</sub> September 2019

## Recap
1. =>
2. Scoping
3. HOF
4. CC

### Question 1 : Pascal's Triangle Part 1

1. The following pattern of numbers is called Pascal’s triangle.
    1
   1 1
  1 2 1 
 1 3 3 1
1 4 6 4 1

The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it.

Write a function pascal that computes elements of Pascal’s triangle by means of a recursive process, i.e. the function should take two arguments, row (counted from the top, starting with 1), and position (counted from the left, starting with 1), and return the element for the specified row and position. Note that only one element must be returned and NOT the entire row. E.g. calling the method with row = 3 and position = 2 should return 2.
Likewise calling the method with row = 5 and position = 3 should return 6.

```javascript
function pascal(row, col){
    return (row === col || col === 1)
        ? 1
        : pascal(row - 1, col - 1) + pascal(row - 1, col);
}
```

### Question 2 : Pascal's Triangle Part 2

Similar to the tree for fib(5) in section 1.2.2 and the tree for cc(11, 5) in the solution for exercise 1.14, draw the tree illustrating the process generated by pascal(5, 4) to compute
the value in Pascal’s triangle in row 5 and position 4. Does your function pascal give rise to a recursive or an iterative process?

Answer:
This is a recursive process as there are defered operations!

### Question 3 HOF

The type of thrice is of the form (T' → T') (where T' happens to equal (T → T)), so we can legitimately use thrice as an input to thrice!

For what value of n will ((thrice(thrice))(f))(0) return the same value1 as (repeated(f, n))(0)?

See if you can now predict what will happen when the following statements are evaluated.

Briefly explain what goes on in each case.
Note: Function square and add1 are defined as follows:

const square = x => x * x;
const add1 = x => x + 1;

(a) ((thrice(thrice))(add1))(6);

Output: 

= f<sup>27</sup>(add1)(6)

= add1<sup>27</sup>(6) = 33


(b) ((thrice(thrice))(x => x))(compose);
Output: 

compose(compose(thrice, thrice). thrice) ()
= compose(x => t(t(x)), t) ()
= f<sup>27</sup>(x => x) (compose)
= compose

(c) ((thrice(thrice))(square))(1);
Output: 
= f<sup>27</sup>(square)(1)
= x => square(square(square(...square(x))))
= 1


#### (d) ((thrice(thrice))(square))(2);
Output: 
= f<sup>27</sup>(square)(2)
= x => square(square(square(...square(2))))
= 2<sup>2^27</sup>