SICPJS 第一章：用函数构建抽象

function fib(n){
  function fib_iter(a, b, count){
    return count === 0
           ? b
           : fib_iter(a + b, a, count - 1);
  };
  return fib_iter(1, 0, n);
}

// problem: given 100 or n, count the ways of splitting it in
// 50, 25, 10, 5, and 1

// method2: dp dp[n,m] = Sum(dp[n][m-1] + dp[n-c[m]][m]) dp[1] = 1
// dp是有序的，是上一个状态推出下一个状态。而给的钱是无序的，需要一个维度来记录彼此的联系
// dp[n,m]与dp[n,m-1]使用c[m]面值的钱与不用的时候的次数 dp[n,m] = dp[n,m-1] + dp[n-c[m]][m]
// dp[n] = Sum(dp[n-c[i]])把c认为是有顺序的，从0～i转移，错误
// dp[n-c[m]][m]假设使用了第m种硬币的人， 因为你使用了这种硬币，所以至少使用了一次，减掉这一次，剩下的
// 无论使用过没有都算，这里有点难理解
  0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
5 1 1 1 1 1 2 2
function count_change(n) {
     const c = [1, 5, 10, 25, 50]
  const dp = new Array(c.length+1)

  for(let i = 0; i < c.length+1; i++) {
    dp[i] = new Array(n+1).fill(0)
  }
  for(let i = 1; i < c.length+1; i++) {
    dp[i][0] = 1
  }
console.log(dp)
  for(let i = 1;i <= c.length; i++) {
    for(let j = 1; j <= n;j++) {
        dp[i][j] = dp[i - 1][j]
        const index = j - c[i-1]
        console.log(index)
        if(index >= 0) dp[i][j] += dp[i][index]
        console.log(i,j,dp[i][j])
    }
  }
  return dp[c.length-1][n]
}

// recursive
function f(n) {
  return n < 3
    ? n
    : f(n - 1) + 2 * f(n - 2) + 3 * f(n - 3)
}
// iterative
function c_f(n) {
  function f_iter(f1, f2, f3, count) {
     return count === n
        ? f3
        : f_iter(f1 + 2 * f2 + 3 * f3, f1, f2, count + 1)
  }
  return f_iter(2, 1, 0, 0)
}

// consider p[i][j]
// recursive
function p_recursive(i, j) {
  return i === 1
    ? 1
    : j === 1
    ? 1
    : p_recursive(i - 1, j) + p_recursive(i, j - 1)
}

// iterative (dp)
function p(i, j) {
  if(i < 1 || j < 1) throw new Error('number invalid')
  if(i === 1 || j === 1) return 1
  // create i + 1 row * j + 1 col array, init value = 0
  const dp = new Array(i + 1).fill().map(item => new Array(j + 1).fill(0))
  for(let k = 0; k < i + 1; k++) {
    dp[k][1] = 1
  }
  for(let k = 0; k < j + 1; k++) {
    dp[1][k] = 1
  }
  for(let k = 2; k < i + 1; k++) {
    for(let g = 2; g < j + 1; g++) {
      dp[k][g] = dp[k - 1][g] + dp[k][g - 1]
    }
  }
  return dp[i][j]
}

// the author's solution use row, index to repesent the item, it's the same as mine

// fast expt: given b and n, calculate b^n
// naive: b^n = b * b * ..... * b (n time) or = b * b^n-1
// recursive time o(n) store o(n)
function expt(b, n) {
  return n === 1
    ? b
    : b * expt(b, n - 1)
}

// iterative store o(1)
function expt(b, n) {
  function expt_iter(a, count) {
    return count === n
      ? a
      : expt_iter(a * b, count + 1)
  }
  return expt_iter(b, 1)
}

// mid: fast_expt: every step is the same, we can take a bigger step,
// b^n = (b^n/2)^2 n is even
// b^n = b * b^n-1 n is odd
// O(log n) store O(log n)
function is_even(n) {
  return n % 2 === 0
}
function fast_expt(b, n) {
  return n === 1
          ? b
          : is_even(n)
          ? fast_expt(fast_expt(b, n / 2), 2) // wrong! use fast_expt(b, n / 2) * fast_expt(b, n / 2) instead this will overflow bcz (b, 2)
        // still need to call fast_expt to solve
          : b * fast_expt(b, n - 1)
}

// iterative
function fast_expt(b, n) {
  function fast_expt_iter(a, count) {
    return count === n // can use n to 0 method too
            ? a
            : count * 2 <= n
            ? fast_expt_iter(a * a, count * 2)
            : fast_expt_iter(a * b, count + 1)
  }
  return fast_expt_iter(b, 1)
}

// use bit shift, avoid use / instead use >> will be even more faster
function fast_expt(b, n) {
  if(n === 0) return 1
  let a = 1
  while(n) {
    if(n % 2 === 0) {
      // b^n = (b^2)^n/2
      n = n >> 1
    } else {
      n = n >> 1
      a = a * b
    }
    b = b * b
  }
  return a
}
// 5 101

// GCD(a, b) = GCD(a, r) r = a % b
function gcd(a, b) {
  return b === 0
         ? a
         : gcd(b, a % b)
}
// 这个函数本身就是迭代的，从上往下不代表一定就是递归，只是思考的方式而已。更像与dp的区别
// 在其他语言，这个就是递归的，可以用for循环写迭代的。在js，有tail_recursive尾递归，这个就是
// for循环的语法糖 空间O(1)

function is_prime(n) {
  function divisor(a, b) {
    return a % b === 0
  }
  function square(a) {
    return a * a
  }
  function divisor_test(r, n) {
    return square(r) > n
           ? true
           : divisor(n, r)
           ? false
           : divisor_test(r + 1, n)
  }
  return divisor_test(2, n)
}
// Exercise 1.23
// improve: if n can't be divided by 2, then all the even number can divide too
function *divisor_generator() {
  let i = 2
  yield i
  i += 1
  while(1) {
    yield i
    i = i + 2
  }
}
/*
divisor.next()
{value: 2, done: false}
divisor.next()
{value: 3, done: false}
divisor.next()
{value: 5, done: false}
divisor.next()
{value: 7, done: false}
divisor.next()
{value: 9, done: false}
*/

// if n is prime, then a^n mod n = a mod n, if 0 < a < n. O(time*logn)
function is_prime(n) {
  function is_even(a) {
    return a % 2 === 0
  }
  function square(a) {
    return a * a
  }
  function random_int_less_than(a) {
    return Math.floor(Math.random() * (a - 1)) + 1
  }
  function fast_expt_mod(a, n, m) {
      return n === 0
             ? 1
             : is_even(n)
             ? square(fast_expt_mod(a, n / 2, m)) % m // js uses 64bit represent number, take remainder each step for perventing overflow
             : (a * fast_expt_mod(a, n - 1, m)) % m
    }
  function fermat_test(a, n) {
    return fast_expt_mod (a, n, n) === a % n
  }
  function fermat_test_time(a, n, time) {
    return time === 0
           ? true
           : fermat_test(a, n)
           ? fermat_test_time(random_int_less_than(n), n, time - 1)
           : false
  }
  return fermat_test_time(random_int_less_than(n), n, 10)
}

// for testing the time cost of the function, we make a high order function
// to wrap those function, record the start time and end time
function time_spend_of_fn(fn) {
  return function(...args) {
    const startTime = new Date()
    const res = fn.call(this, ...args)
    const endTime = new Date()
    console.log(`spend: ${endTime - startTime}`)
    return res
  }
}

function sum_integers(a, b) {
    return a > b
           ? 0
           : a + sum_integers(a + 1, b);
}
function sum_cubes(a, b) {
    return a > b
           ? 0
           : cube(a) + sum_cubes(a + 1, b);
}
function pi_sum(a, b) {
    return a > b
           ? 0
           : 1 / (a * (a + 2)) + pi_sum(a + 4, b);
}
// whats common partern they have? whats the difference?
// remember the thought: putting some ideas together, look and solve them once
// function is a combination of some expression, so those functions' parts are
// the same majorily, which the different is after ':' and the next() function

function summate(a, b, f, next) {
  return a > b
         ? 0
         : f(a) + summate(next(a), b, f, next)
}
function simpson_integrate(a, b, f, n) {
  const h = (b - a) / n
  function get_y(k) {
    return f(a + k * h)
  }
  function next(a) {
    return a + 1
  }
  function is_even(a) {
    return a % 2 === 0
  }
  function term(p) {
    return p === 0
           ? get_y(p)
           : p === n
           ? get_y(p)
           : is_even(p)
           ? 2 * get_y(p)
           : 4 * get_y(p)
  }
  return h / 3 * summate(0, n, term, next)
}

// iterative
function summate(a, b, f, next, res) {
  return a > b
         ? res
         : summate(next(a), b, f, res + f(a))
}

function product(a, b, f, next) {
  return a > b
         ? 1
         : f(a) * product(next(a), b, f, next)
}
function factorial(n) {
  function inc(a) {
    return a + 1
  }
  return product(1, n, a => a, inc)
}
function pi(n) {
  function is_even(a) {
    return a % 2 === 0
  }
  let i = 0
  function numerator_next(a) {
    i += 1
    console.log(i)
    return is_even(i)
           ? a
           : 2 + a
  }
  let j = 0
  function denominator_next(a) {
    j += 1
    return is_even(j)
           ? 2 + a
           : a
  }
  return 4 * product(2, n, a => a, numerator_next)
         / product(3, n, a => a, denominator_next)
}
// iterative
function product(a, b, f, next) {
  function product_iter(a, res){
    return a > b
           ? res
           : product_iter(next(a), res * f(a))
  }
  return product_iter(a, 1)
}

// use same thought to extract common partern of summate and product function
function summate(a, b, f, next) {
  return a > b
         ? 0
         : f(a) + summate(next(a), b, f, next)
}
function product(a, b, f, next) {
  return a > b
         ? 1
         : f(a) * product(next(a), b, f, next)
}
// what's the difference? what's the commons?
function accumulate(a, b, f, next, combine, null_value) {
  return a > b
         ? null_value
         : combine(f(a),accumulate(next(a), b, f, next, combine, null_value))
}

// 函数就是一个操作的抽象，普通函数可以抽象某个对data的操作，
// 而高阶函数把函数当作参数传入，则可以抽象某个对操作的操作，把某些操作的
// 相同部分抽离出来复用，也就是在两个ideas中找共同点
// 抽象的部分是相同的，而根据传来的参数的不同做特别的操作和结果

// iterative
function accumulate(a, b, f, next, combine, null_value) {
  function accumulate_iter(a, res) {
    return a > b
           ? res
           : accumulate_iter(next(a),combine(res,f(a)))
  }
  return accumulate_iter(a, null_value)
}

function find_root(f, r, a, b) {
  const middle = (a + b) / 2
  return b - a < r || f(middle) === 0
         ? middle
         : f(a) * f(middle) < 0
         ? find_root(f, r, a, middle)
         : find_root(f, r, middle, b)
}
// add: consider root don't sit between a and b
function find_root(f, r, a, b) {
  const middle = (a + b) / 2
  if(b - a < r || f(middle) === 0) return middle
  if(f(middle) * f(a) < 0) {
    return find_root(f, r, a, middle)
  }
  if(f(middle) * f(b) < 0) {
    return find_root(f, r, middle, b)
  }
  return new Error('root don't exist at a, b')
}
// normal half-interval, find if n locate in sorted arr, which
// boundary is 0, arr.length - 1
function binary_search(n, arr, a, b) {
  const middle = Math.floor((b + a) / 2)
  return n === arr[middle]
         ? middle
         : arr[middle] > n
         ? binary_search(n, arr, a, middle - 1)
         : binary_search(n, arr, middle + 1, b)
}
// high-order function of binary_search and find_root
// what is the common part and what is the difference?
// the flow is: first find a index(in this case middle)
// then use this index to judge what part the res will sit
// and then narrow the problem's size and recursive
function half_interval(range, find_index, judge_index, new_range) {
  const index = find_index(range)
  const judgement = judge_index(index)
  // agreement: judgement === 0: index is res, judgement === something else,
  // start a new function call
  return judgement === 0
         ? index
         : half_interval(new_range(range, index, judgement),find_index, judge_index, new_range)
}

// binary_search use half_interval
function binary_search(n, arr, a, b) {
  const range = {a, b}
  const find_index = (range) => {
    return Math.floor((range.a + range.b) / 2)
  }
  const judge_index = (index) => {
    return arr[index] === n
           ? 0
           : arr[index] > n
           ? -1
           : 1
  }
  const new_range = (range, index, judgement) => {
    return judgement === 1
           ? {...range, a: index + 1}
           : {...range, b: index - 1}
  }
  return half_interval(range, find_index, judge_index, new_range)
}
// not neccessary at most of the time, we write
// more code seem this two functions have little
// same partern😂 just to train the mind of putting two
// ideas together and see common

// example 1: make a damp to a function for instance x -> x * x

function square(x) {
  return x * x
}

function average(x, y) {
  return (x + y) / 2
}

function square_damp(x) {
  return average(x, square(x))
}

// now we have another function need damping, for instance x -> x * x * x

function cube(x) {
  return x * x * x
}

function cube_damp(x) {
  return average(x, cube(x))
}

// now you can see that most of the process that damp take is the same but
// only the second paramater of average have difference process
// you can pass this process as paramater to make it more generate

function damp(x, f) {
  return average(x, f(x))
}

damp(x, square)

function sqrt(x) {
  return fixed_point(x => damp(x, y => x / y), 1)
}

// we can make the damp function generate new function rather than just
// return a value

function average_damp(f) {
  return x => average(x, f(x))
}

function sqrt(x) {
  return fixed_point(average_damp(y => x / y), 1)
}

// deriv is a new function base on g(x), so we can use fn as return value to
// express this idea
const dx = 0.000001
function deriv(g) {
  return x => (g(x + dx) - g(x)) / dx
}

// given param, generate a function
function cubic(a, b, c) {
  return x => cube(x) + a * square(x) + b * x + c
}

function double(f) {
  return x => f(f(x))
}

double(double(double))(inc)(5);

// double make the original function do twice, so double(double) is 4 times

double(double): x => (f => (x => f(f(f(f(x))))))

// double(double(double)) is 16 times

// abstraction of compose
function compose(x, f, g) {
  return f(g(x))
}

compose(x, square, inc)

function compose(f, g) {
  return x => f(g(x))
}

compose(square, inc)(x)

// what's the difference?
// former only create an abstraction of compose function,
// return fn as value also create an abstraction of `create an abstraction of compose function`
// or the abstraction of modifing function

// given a function and n times, modify the function to repeat itself n times
function repeated(f, times) {
  return function rp(x) {
    if(times === 0){
      return x
    }
    times--;
    return rp(f(x))
  }
}

// smoothing function,  times
function smooth_n_fold(f, times) {
  const dx = 0.00001
  function smooth(f) {
    return x => (f(x - dx) + f(x) + f(x + dx)) / 3
  }
  return repeated(smooth, times)(f)
}

// smooth() is the abstraction of process f()
// while the repeated() is the abstraction of process smooth()
// with high-order function, every process can be abstract

function iterative_improve(improve, is_good_enough) {
  return function repeat(x) {
    return is_good_enough(x)
           ? x
           : repeat(improve(x))
  }
}