Skip to content

Instantly share code, notes, and snippets.

@dc-mak
Created July 7, 2018 19:24
Show Gist options
  • Save dc-mak/2f87838118a056a8588659a1ce006727 to your computer and use it in GitHub Desktop.
Save dc-mak/2f87838118a056a8588659a1ce006727 to your computer and use it in GitHub Desktop.
Recursive Functions and Debugging (Solving Problems in Computer Science, ATypical CompSci)
let directSumFrom1To = (n: int): int => n * (n + 1) / 2;
let directSumFrom1To: int => int = n => n * (n + 1) / 2;
let directSumFrom1To = n => n * (n + 1) / 2;
/* Step 1 */
/*
* let choose_from = (k, n) =>
* choose_from(k - 1, n - 1) + choose_from(k, n - 1);
*/
/* Step 2 */
let rec choose_from = (k, n) =>
choose_from(k - 1, n - 1) + choose_from(k, n - 1);
/* Step 3 */
let rec choose_from = (k, n) =>
if (k == 0 || k == n) {
1;
} else {
choose_from(k - 1, n - 1) + choose_from(k, n - 1);
};
/* More concisely */
let rec choose_from = (k, n) =>
k == 0 || k == n ? 1 : choose_from(k - 1, n - 1) + choose_from(k, n - 1);
/* To see code working in action */
let generate = (f, n) => {
let rec loop = k => k == n ? [] : [f(k), ...loop(k + 1)];
loop(0);
};
let row = n => generate(x => (x, n), n + 1);
let pascalUptoRow = n =>
generate(n => List.map(((x, y)) => choose_from(x, y), row(n)), n + 1);
/* Debugging 1 */
let rec choose_debug = (k, n) => {
Printf.printf("(%d,%d)\n", k, n);
choose_debug(k - 1, n - 1) + choose_debug(k, n - 1);
};
/* Debugging 2 */
let rec choose_debug = (k, n) => {
let result = choose_debug(k - 1, n - 1) + choose_debug(k, n - 1);
Printf.printf("(%d,%d)\n", k, n);
result;
};
/* Debugging 3 */
let untied_choose = (recurse_on, k, n) =>
k == 0 || k == n ? 1 : recurse_on(k - 1, n - 1) + recurse_on(k, n - 1);
/* Debugging 4 */
let rec choose_from = (k, n) => untied_choose(choose_from, k, n);
let rec choose_debug = (k, n) => {
Printf.printf("(%d,%d)\n", k, n);
untied_choose(choose_debug, k, n);
};
/* Less useful... */
let rec choose_debug2 = (k, n) => {
let result = untied_choose(choose_debug2, k, n);
Printf.printf("(%d,%d)\n", k, n);
result;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment