23 Reading SICP - the pair and tree data structure and their common operations in functional programming

sicp01.js

// ------ data structure: pair ------ //

// constructor for compound data structure: pair
function cons(a, b) {
  var pair = []
  pair[0] = a
  pair[1] = b
  return pair
}

// fetch the former element in a pair
function car(pair) {
  return pair[0]
}

// fetch the latter element in a pair
function cdr(pair) {
  return pair[1]
}

// ------ data structure: list ------ //

// init a list which is a linked list composed with pairs
function listInit(list) {
  if (list.length == 0) {
    return cons(null, null)
  } else if (list.length == 1) {
    return cons(list[0], null)
  } else {
    var argv1 = list.shift()
    return cons(argv1, listInit(list))
  }
}

// init a list with numerical literals as its elements between low and high value
function enumerateInterval(low, high) {
  if (low > high) {
    return null
  } else {
    return cons(low, enumerateInterval(low + 1, high))
  }
}

// fetch the nth element in a list
function ref(list, n) {
  if (n == 0) {
    return car(list)
  } else {
    return ref(cdr(list), n - 1)
  }
}

// determine if a list is null
function isNull(list) {
  if (list == null) {
    return true
  } else if (!isPair(list)) {
    return false
  } else {
    return car(list) == null
  }
  // if (!isPair(list)) {
  //   return false
  // } else {
  //   return list == null || car(list) == null
  // }
}

// get the length of a list
function length(list) {
  if (isNull(list)) {
    return 0
  } else {
    return 1 + length(cdr(list))
  }
}

// print out every elements in a list to console
function print(list) {
  var s = ''
  function _print(l, str) {
    if (!isNull(l)) {
      str += car(l)
      str += ' '
      _print(cdr(l), str)
    } else {
      console.log(str)
    }
  }
  _print(list, s)
}

// append (concat) one list to another
function append(list1, list2) {
  if (isNull(list1)) {
    return list2
  } else {
    return cons(car(list1), append(cdr(list1), list2))
  }
}

// map action: applying procedure to each element of the list and return a new list
function map(list, proc){
  if (isNull(list)) {
    return null
  } else {
    return cons(proc(car(list)), map(cdr(list), proc))
  }
}

// filter action: applying predicate to each element of the list
// and return a new list containing elements that passes the test
function filter(list, pred) {
  if (isNull(list)) {
    return null
  } else if (pred(car(list))) {
    return cons(car(list), filter(cdr(list), pred))
  } else {
    return filter(cdr(list), pred)
  }
}

// remove the specified element in a list
function remove(list, item) {
  return filter(list, (i) => i != item)
}

// accumulate action: applying one operation iteratively, each time using the next element in the list
function accumulate(list, op, initial) {
  if (isNull(list)) {
    return initial
  } else {
    var a = car(list)
    var b = accumulate(cdr(list), op, initial)
    return op(a, b)
  }
}

// some tests
var l1 = listInit([1, 2, 3, 4 ,5])
var l2 = listInit([6, 7, 8, 9, 10])
var l3 = append(l1, l2)
var l3 = cons(0, l3)
var l4 = map(l3, (x) => 2 * x)
var l5 = filter(l4, (x) => x % 3 == 0)
print(l5)

// ------ data structure: tree ------ //

// determine if the argument is a pair data structure
function isPair(n) {
  return Array.isArray(n)
}

// count the length of leaf nodes in the tree
function countLeaves(tree) {
  if (isNull(tree)) {
    return 0
  } else if (!isPair(tree)) {
    return 1
  } else {
    return countLeaves(car(tree)) + countLeaves(cdr(tree))
  }
}

// flatten the tree into a list
function flatten(tree) {
  if (isNull(tree)) {
    return null
  } else if (!isPair(tree)) {
    return listInit([tree])
  } else {
    var a = flatten(car(tree))
    var b = flatten(cdr(tree))
    var result = append(a, b)
    return result
  }
}

// map operation on a tree
function mapTree(tree, proc) {
  if (isNull(tree)) {
    return null
  } else if (!isPair(tree)) {
    return proc(tree)
  } else {
    var a = mapTree(car(tree), proc)
    var b = mapTree(cdr(tree), proc)
    return cons(a, b)
  }
}

// filter a tree by examing all of its leaf nodes
// this is done by a combination of flatten and filter
function filterTree(tree, proc) {
  return filter(flatten(tree), proc)
}

// like map, but will flat result when the proc produces hierarchical data
function flatMap(list, proc) {
  return accumulate(map(list, proc), append, null)
}

// an example of flatMap with recursion: finding all permutations of a list
function permute(list) {
  if (length(list) == 1){
    return listInit([list])
  } else {
    var f = (head) => {
      var tail = remove(list, head)
      var permutations = permute(tail)
      var results = map(permutations, (permutation) => {
        return cons(head, permutation)
      })
      return results
    }
    return flatMap(list, f)
  }
}

// some tests
var a = listInit([2, 3, 4])
var b = permute(a)
var c = flatten(b)
console.log(ref(b, 5))
console.log(JSON.stringify(b))
console.log(JSON.stringify(c))