itero recursive algorithm for signly linked list, fibonnaci, depth first and bread first search

itero-recursive.js

    function fibs(n) {
      let [last, curr] = [0, 1];
      for (let i = 0; i < n; i++) {
        [last, curr] = [curr, last + curr];
      }
      return last; // think: why isn't this `curr`?
   }
// fibs(3)
// 0 1 3 4 7
// 0 1 1 2 3 5


interface ITree<x> {
  value: x;
  children: Array<ITree<x>>;
}

function traversedfs<x>(tree: ITree<x>, visit: (arg: ITree<x>) => void) {
  visit(tree);
  for (const subtree of tree.children) {
    traverse(subtree, visit);
  }
}

function traversebda<x>(tree: ITree<x>, visit: (arg: ITree<x>) => void) {
  const queue: Array<ITree<x>> = [tree];
  while (queue.length > 0) {
    const subtree = queue.shift();
    if (visit(subtree)) {
      return { type: 'found', value: subtree };
    }
    // otherwise
    for (const child of subtree.children) {
      queue.push(child);
    }
  }
  return { type: 'not found' };
}

/* First example: Fibonacci numbers. If you wrote out an iterative algorithm it would look like:
 *
 *     function fibs(n) {
 *       let [last, curr] = [0, 1];
 *       for (let i = 0; i < n; i++) {
 *         [last, curr] = [curr, last + curr];
 *       }
 *       return last; // think: why isn't this `curr`?
 *     }
 *
 * Here is the iterorecursive translation of that:
 */
function fibs(n: number, i = 0, last = 0, curr = 1): number {
  if (i >= n) {
    return last; // because fibs(0) == 0
  }
  return fibs(n, i + 1, curr, last + curr);
}

// Second example: reversing a singly linked list. First let's write out the definition:
interface ICons<x> {
  first: x;
  rest: SLL<x>;
}
type SLL<x> = ICons<x> | null;

/* Here the iterative algorithm looks something like,
 *
 *     function reverse(list) {
 *       let todo = list;
 *       let reversed = null;
 *       while (todo !== null) {
 *         const { first, rest } = todo;
 *         reversed = { first, rest: reversed };
 *       }
 *       return reversed;
 *     }
 *
 * So you would have:
 */
function reverse<x>(todo: SLL<x>, reversed = null as SLL<x>): SLL<x> {
  if (todo === null) {
    return reversed; // because reverse(null) = null
  }
  const { first, rest } = todo;
  return reverse(rest, { first, rest: reversed });
}

/* As an example where you might need more structure, consider how you might concatenate two 
 * singly-linked lists; one approach might be:
 * 
 *     function concat(list1, list2) {
 *       // we need to tack last element of list1 onto the front of list2, so let's reverse it
 *       let todo = reverse(list1);
 *       let done = list2;
 *       while (todo !== null) {
 *         const { first, rest } = todo;
 *         todo = rest;
 *         done = { first, rest: done };
 *       }
 *       return done;
 *     }
 *
 * Preprocessing the input is the sort of sitch where you want to define an inner function:
 */
function concat<x>(list1: SLL<x>, list2: SLL<x>): SLL<x> {
  function go(todo: SLL<x>, done: SLL<x>): SLL<x> {
    if (todo === null) {
      return done;
    }
    const { first, rest } = todo;
    return go(rest, { first, rest: done });
  }
  return go(reverse(list1), list2);
}

/* Final example, building on the other two, is the one from description.md: you are doing a 
 * breadth-first search with some predicate on a rose tree. Again we can start with the data 
 * structures. The simplest purely functional queue is two singly-linked lists, the "front" is
 * stored in the normal order and the "back" is stored in reverse order, so that you can add to the
 * back of the queue instantaneously. You cannot pick up from the front instantaneously, but it is
 * usually not a horrible cost either: if the front is empty and the back contains N elements then
 * it will take N steps to reverse the back into a new front, but then you don't have to do this
 * again for N more steps. 
 */
interface IQueue<x> {
  front: SLL<x>;
  back: SLL<x>;
}
function emptyQueue<x>(): IQueue<x> {
  return { front: null, back: null };
}
function singletonQueue<x>(x: x): IQueue<x> {
  return { front: { first: x, rest: null }, back: null };
}
function addToQueue({ front, back }: IQueue<x>, elements: SLL<x>): IQueue<x> {
  return { front, back: concat(reverse(elements), back) };
}

type Maybe<x> = null | { just: x };

function popQueue<x>({ front, back }: IQueue<x>): Maybe<[x, IQueue<x>]> {
  if (front === null) {
    const reversed = reverse(back);
    return reversed === null
      ? null
      : { just: [reversed.first, { front: reversed.rest, back: null }] };
  }
  return { just: [front.first, { front: front.rest, back }] };
}

// we also need a type of trees; let's suppose it looks like so:
interface ITree<x> {
  value: x;
  children: SLL<ITree<x>>;
}

/* Then if you had these you could pretty easily come up with an iterative algorithm, like maybe:
 *
 *     function bfs(root, predicate) {
 *       let popped = {just: [root, emptyQueue()]};
 *       while (popped !== null) {
 *         const [node, queue] = popped.just;
 *         if (predicate(node)) {
 *           return {just: node};
 *         }
 *         popped = popQueue(addToQueue(queue, node.children))
 *       }
 *       return null;
 *    }
 *
 * And we can translate this directly:
 */
function bfs<x>(root: ITree<x>, predicate: (tree: ITree<x>) => boolean): Maybe<ITree<x>> {
  function go(popped: Maybe<[ITree<x>, IQueue<ITree<x>>]>): Maybe<ITree<x>> {
    if (popped === null) {
      return null;
    }
    const [node, queue] = popped.just;
    if (predicate(node)) {
      return { just: node };
    }
    return go(popQueue(addToQueue(queue, node.children)));
  }
  return go({ just: [root, emptyQueue()] });
}